Trovare x tale che ax - b = cy con a,b,c,x interi
Trovare x tale che ax - b = cy con a,b,c,x interi
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
-
FrancescoVeneziano
- Site Admin
- Messaggi: 606
- Iscritto il: 01 gen 1970, 01:00
- Località: Genova
- Contatta:
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.
$ 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.
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
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