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

Cosa sono il pigeonhole e l'induzione? Cosa dice il teorema di Ceva? 1 è un numero primo?
Rispondi
karotto
Messaggi: 357
Iscritto il: 01 gen 1970, 01:00

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

Messaggio da karotto » 18 set 2005, 13:43

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

Avatar utente
FrancescoVeneziano
Site Admin
Messaggi: 601
Iscritto il: 01 gen 1970, 01:00
Località: Pisa
Contatta:

Messaggio da FrancescoVeneziano » 18 set 2005, 14:11

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.
Wir müssen wissen. Wir werden wissen.

Avatar utente
talpuz
Moderatore
Messaggi: 873
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da talpuz » 18 set 2005, 15:37

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

Rispondi