Diofantea lineare in [tex]\mathbb{N}[/tex]

Cosa sono il pigeonhole e l'induzione? Cosa dice il teorema di Ceva? 1 è un numero primo?
Rispondi
Gi.
Messaggi: 154
Iscritto il: 18 dic 2012, 16:45

Diofantea lineare in [tex]\mathbb{N}[/tex]

Messaggio da Gi. »

Data l' equazione lineare indeterminata

$ ax+by=n $

Vorrei stabilire una condizione di risolubilità con $ x,y \in\mathbb{N} $.
Chiaramente, n deve essere un multiplo del MCD di a e b, altrimenti l' equazione é irrisolubile.
Nell' "aritmetica superiore" di Davenport viene detto che il più grande numero per cui l' equazione non ha soluzioni é $ n=ab-a-b $. La dimostrazione data é la seguente:

Supponiamo $ MCD(a,b)=h\not=1 $, dividiamo allora tutto per h fin quando non si giunge alla situazione $ MCD(a,b)=1 $.

Se $ n=ab-a-b $, allora il numero $ n+a=b(a-1) $ é divisibile per b.

Sia $ n=ax+by $, allora $ n+a=a(x+1)+by $, poiché $b\mid n+a$ e, evidentemente, $b\mid by$ allora $b\mid a(x+1)$, essendo coprimo con $a$ allora $b\mid(x+1)$, da questo segue

$x+1\ge b $

$a(x+1)\ge ab$

$ax\ge a(b-1)$

Ovviamente, addizionando al LHS $by$ la diseguaglianza non viene modificata, per cui


$ax+by\ge a(b-1)$

L' espressione sopra é sicuramente falsa, in quanto $ax+by= a(b-1)-b < a(b-1)$
Quindi non puo' esistere un $n$ siffatto.

Potreste mostrarmi una dimostrazione che, invece, per $n\ge ab-a-b+1$ l' equazione ha soluzioni?
Quella presente sul Davenport non riesco a capirla :?
Rispondi