Pagina 1 di 1

Trovare x tale che ax - b = cy con a,b,c,x interi

Inviato: 18 set 2005, 13:43
da karotto
Mi aiutate a risolvere il problema in questione (mi hanno detto di postarlo qui). Io l'ho risolto per tentativi ma vorrei sapere se esiste un algoritmo che mi permetta di risolverlo immediatamente

Inviato: 18 set 2005, 14:11
da FrancescoVeneziano
Quello che vuoi risolvere è la congruenza
$ ax\equiv b \mod m $

Innanzitutto possiamo ridurci al caso in cui a ed m sono coprimi, infatti se chiamiamo d il massimo comun divisore tra a ed m può succedere che d non divida b, nel qual caso la congruenza è impossibile, o che d divida b, nel qual caso la congruenza è equivalente a
$ a'x\equiv b' \mod m' $
dove a'=a/d, b'=b/d, m'=m/d.

Se MCD(a,m)=1 il teorema di Bezout ci dice che esistono due interi h e k tali che ah+mk=1, cioè che la classe di resto di a è invertibile modulo m e che il suo inverso è la classe di h.
Quindi la soluzione della tua congruenza è
$ x\equiv bh \mod m $

Sul calcolo dell'inverso di a modulo m c'è già un'altra pagina del glossario, anche se non molto completa, se necessario posso espanderla.

Inviato: 18 set 2005, 15:37
da talpuz
dunque..

dati $ a,b,c $ interi vuoi trovare $ x,y $ interi tali che valga $ ax-cy=b $.

il problema ha soluzione se e solo se $ mcd(a,c)|b $, e le soluzioni si ricavano utilizzando l'algoritmo di euclide per arrivare a $ t,u $ tali che $ at-cu=(a,c) $, poi basta moltiplicare tutto per $ b/(a,c) $.

in questo modo si trova una soluzione particolare. per trovarle tutte, si aggiungono a quella particolare tutte le soluzioni dell'equazione omogenea $ ax-cy=0 $, che sono della forma $ x=ct/(a,c) $, $ y=at/(a,c) $, con $ t $ intero.

quindi tutte le solzioni dell'equazione originale, se $ x_0,y_0 $ è una soluzione particolare, sono $ x=x_0+ct/(a,c) $, $ y=y_0+at/(a,c) $, con $ t $ che varia negli interi.

ESEMPIO: (un po' stupido, in realtà)

vogliamo trovare $ x,y $ interi tali che $ 30x-12y=24 $, usando l'algoritmo.

dividiamo 30 per 12

$ 30=12*2+6 $ e l'mcd è 6, $ 6=30-12*2 $

moltiplichiamo tutto per 24/6=4, $ 24=30*4-12*8 $, quindi una soluzione particolare è x=4, y=8

le soluzioni dell'omogenea $ 30x-12y=0 $ sono $ x=12t/6=2t $, $ y=30t/6=5t $, con t intero.

quindi, tutte le soluzioni dell'equazione sono $ x=4+2t $, $ y=8+5t $ con t intero.

------

chiaro? chiedi pure se hai bisogno di chiarimenti

le cose che ho enunciato sopra puoi provare a dimostrarle, se vuoi, altrimenti chiedi anche per quelle, e qualcuno le scriverà :D

------

acc, francesco mi ha anticipato (sarà che ci ho messo mezz'ora a scrivere :?)

lascio comunque anche il mio intervento, visto che è un po' diverso