OliForum Matematico

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

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.

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à

------

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