[Risolto] equazioni diofantee

vediamo prima il caso in cui $mcd(a, b)=1$.

Sia $S=\{c \in Z : \exists x, y \in N : c = ax+by\}$.

il problema si traduce nel trovare il max di $Z - S$.

Fatto: $A_c = \{(x, y) \in Z x Z : ax+by=c\}=\{(x+kb, y-ka) : k \in Z\} \ \forall (x, y) \in A_c$.

Dimostrazione: $mcd(a, b)=1 \Rightarrow \exists a', b' \in Z : a' a+b' b=1 \Rightarrow c a' a+c b' b=c \Rightarrow A_c \not = \phi$. E' banale osservare che $(c a'+kb,n b'-ka) \in A_n \ \forall k \in Z$. Inoltre, se $(x_1, y_1)$ e $(x_2, y_2)$ sono sono soluzioni di $a x+b y=n \Rightarrow x_1 a+y_1 b=c=x_2 a+y_2 b \Rightarrow (x_1 - x_2)a=(y_2 - y_1)b \Rightarrow a \vert (y_2 - y_1)b \Rightarrow  a \vert (y_2 - y_1)$ in quanto $mcd(a, b)=1$ e analogamente $b \vert (x_1 - x_2)$. Dunque $y_2 - y_1=k_1 a \wedge x_1 - x_2=k_2 b$ e si ha $(k_2 b)a=(k_1 a)b \Rightarrow k_1 = k_2$ che dimostra la tesi.

Fatto: $\forall c \in N, \ \exists ! (x_c, y_c) \in Z x \{0,1,...,a-1\} : a x_c + b y_c = c$.

Dimostrazione: dalla divisione euclidea sappiamo che esiste un solo $k : 0 \leq b-ka \leq a-1$.

Fatto: $c \in S \iff x_c \geq 0$

Dimostrazione: se $x_c \geq 0 $ banalmente scegliendo $(x, y) = (x_c, y_c)$ abbiamo che $c \in S$. Viceversa se $x_c < 0 \Rightarrow x_c+kb < 0 \ \forall k \leq 0 \wedge y_c - ka < 0 \ \forall k > 0$ quindi la coppia non può avere entrambe le entrate positive.

Quindi in definitiva $Z - S=\{ax+by : x<0, 0 \leq y \leq a-1\}$ il cui massimo si ottiene per $x=-1$ e $y=a-1$ e vale $ab-a-b$.

Se poi $d=mcd(a, b)>1$ allora si può riscalare l'equazione di partenza dividendo tutto per $d$ e ragionare in maniere analoga.

Se a,b ,c sono interi positivi

segue che x ed y non possono essere entrambi negativi

se ax è negativo allora ogni by>ax da un c quindi la risposta alla tua domanda è NO

se by è negativo allora ogni ax>by da un c quindi la risposta alla tua domanda è NO