equazioni diofantee con le congruenze

[angus89]

Credo che sia tutto giusto, in questo post descrivo un metodo per risolvere equazioni diofantee con le congruenze (idea venutami durante una noiosissima conferenza a scuola XD)

va bè...passiamo all'azione

sia data l'equazione diofantea
$ \displaystyle ax+by=c $

Ricordiamo un pò di condizioni di solubilità
ha soluzioni per $ \displaystyle c=k \cdot MCD(a,b) $
Pertanto sarà possibile mettere in evidenza $ \displaystyle MCD(a,b) $.

Fatti questi passaggi sarà possibile ricondurre ogni equazione diofantea ad una equazione del tipo
$ \displaystyle ax+by=1 $

sviluppando un pò di calcoli e messe in evidenza
$ \displaystyle y=\frac{1-ax}{b} $
Che si risolve con le congruenze facilmente ponendo
$ \displaystyle ax \equiv 1 \pmod{b} $
E di conseguenza si trova il valore di $ \displaystyle y $ che sarà necessariamente intero.

Ricapitolazione velocissima
data l'equazione diofantea
$ \displaystyle ax+by=c $

la si riconduce a
$ \displaystyle ax+by=1 $

si risolve la congruenza
$ \displaystyle ax \equiv 1 \pmod{b} $

poniamo $ \displaystyle z $ come soluzione della congruenza
tutte le soluzioni avranno la forma
$ \displaystyle z+nb;\frac{1-a(z+nb)}{b} $


Esempio veloce
sia data l'equazione
$ \displaystyle 21x+35y=14 $
dividiamo per $ \displaystyle 7 $
$ \displaystyle 3x+5y=2 $
allora risolviamo
$ \displaystyle 3x+5y=1 $
ricordandoci che dobbiamo moltiplicare il risultato per $ \displaystyle \displaystyle 2 $

risolviamo la congruenza
$ \displaystyle 3x \equiv 1 \pmod{5} $
$ \displaystyle x \equiv 2 \pmod{5} $

pertanto le soluzioni avranno la forma (ricordando quanto detto sopra)
$ \displaystyle (2+5n;-1-3n) $
ma ci ricordiamo che dobbiamo moltiplicare per $ \displaystyle \displaystyle 2 $
quindi l'equazione
$ \displaystyle 21x+35y=14 $
ha le soluzioni della forma
$ \displaystyle (4+10n;-2-6n) $
per qualsiasi $ \displaystyle \displaystyle n $ intero

Bè mi sembra un metodo veloce (paragonato a quello che usavo io)
magari non ho detto niente di utile ma mi sembrava una cosa interessante...

[Ani-sama]

Ho capito dove vuoi arrivare ma credo che dovresti specificare meglio alcuni passaggi. Per esempio, quando scrivi:

Che si risolve con le congruenze facilmente ponendo
$ \displaystyle ax \equiv 1 \pmod{b} $

chi ti dice che quella congruenza abbia soluzioni? Certo, se $ \gcd(a,b)=1 $ tutto funziona, ma per te $ a,b $ sono ancora i coefficienti dati all'inizio del problema.

Poi, perché ti riconduci a $ ax+by=1 $? Se sapresti dirmi la ragione precisa...

[EvaristeG]

Approvo gli autodidatti, ma fino a un certo punto ... se cerchi su qualunque testo/dispensa/etc. di teoria dei numeri troverai cose come il teorema di Bezout e l'algoritmo di risoluzione delle diofantee lineari ... addirittura anche in questo forum, nel glossario, si è sicuramente parlato di loro e delle sorelle, le congruenze lineari.
Comunque, non hai detto altro che questo:
le soluzioni x della diofantea
$ ax+by=c $
sono le stesse della congruenza
$ ax\equiv c\mod b $
Beh ... è un po' la definizione di congruenza, no?
$ ax\equiv c\mod b $ se e solo se esiste un intero y tale che $ ax-c=-by $ (il segno meno fa comodo ma è inutile, teoricamente) ovvero se e solo se $ ax+by=c $.
Del resto, per risolvere una congruenza con numeri molto grandi puoi solo utilizzare l'algoritmo euclideo, che è esattamente quello che si usa per risolvere le diofantee lineari ... ad esempio, come risolvi
$ 323x\equiv 1\mod 1024 $?
Devi per forza ricondurti all'eq diofantea $ 323x+1024y=1 $ e risolverla con l'algoritmo euclideo dell'MCD.

[angus89]

Approvo gli autodidatti, ma fino a un certo punto ... se cerchi su qualunque testo/dispensa/etc. di teoria dei numeri troverai cose come il teorema di Bezout e l'algoritmo di risoluzione delle diofantee lineari

Bè ma certo che conosco l'algoritmo di euclide e il teorema di Bezout...
Questa era solo un'idea...
E poi con la congruenza, almeno io mi sento più sicuro di non saltare soluzioni...
E' diventata la mia più grande fobia, saltare qualche soluzione...
Va bè...
L'osservazione voleva esser del tipo...le diofantee lineari si possono risolvere con la nozione di congruenza...

[EvaristeG]

No, non mi hai capito ... le congruenze lineari, in generale, si devono risolvere con l'algoritmo euclideo... non c'è altra strada teorica, se non il provare tutti i resti modulo m fino a trovare quelli giusti.
Quindi non guadagni nulla passando da una diofantea ad una congruenza ... ripeto l'esempio:
considera la diofantea $ 323x+1024y=1 $
con il tuo metodo dici che è come risolvere la congruenza $ 323x\equiv 1\mod 1024 $, che è vero ... ok, ora che fai? questa come la risolvi?

[angus89]

si avevo capito...
è tutto ok ora...
il mio era un ragionamento mirato a risolvere le diofantee e determinare tutte le soluzioni...e mi è venuto in mente di utilizzare le congruenze...
Son partito da: e se non conoscessi l'algoritmo di Euclide?
Per poi arrivare a dire...bisogna comunque conoscerlo...