Calcolo e veridicità della ax ≡n b
Buongiorno,
Sono alle prese, purtroppo in qualità di studente lavoratore, con il teorema riportato nel titolo della discussione, ovvero:
ax congruent b (mod n)
Nelle dispense dalle quali sto studiando matematica discreta trovo quanto segue (così come in altre risorse in rete):
"L’equazione ax ≡n b ammette soluzioni se e solo se il massimo comune divisore d di a e n divide b."
svolgendo alcuni esercizi per esercitarmi (generati casualmente con l'ausilio di wolfram) mi sono imbattuto in
11x congruent 20 mod 6
il quale secondo il teorema sopra citato, essendo MCD(11,20) = 1, quindi con a ed n coprimi, mi sarei aspettato che appunto non ammettesse soluzioni, eppure:
http://www.wolframalpha.com/input/?i=11x+congruent+20+mod+6
x=4
infatti
11*4 = 44 e 44 mod 6 = 2
20 mod 6 = 2
Non so pertanto come interpretare il teorema, potreste gentilmente guidarmi passo passo per cercare di capire come approcciare agli esercizi che si presentano in questa forma.
Esiste un procedimento valido per tutti i casi per risolvere queste equazioni?
Grazie anticipatamente a tutti coloro che mi daranno un aiuto anche solo parziale,
Ciao!,
Simone
Sono alle prese, purtroppo in qualità di studente lavoratore, con il teorema riportato nel titolo della discussione, ovvero:
ax congruent b (mod n)
Nelle dispense dalle quali sto studiando matematica discreta trovo quanto segue (così come in altre risorse in rete):
"L’equazione ax ≡n b ammette soluzioni se e solo se il massimo comune divisore d di a e n divide b."
svolgendo alcuni esercizi per esercitarmi (generati casualmente con l'ausilio di wolfram) mi sono imbattuto in
11x congruent 20 mod 6
il quale secondo il teorema sopra citato, essendo MCD(11,20) = 1, quindi con a ed n coprimi, mi sarei aspettato che appunto non ammettesse soluzioni, eppure:
http://www.wolframalpha.com/input/?i=11x+congruent+20+mod+6
x=4
infatti
11*4 = 44 e 44 mod 6 = 2
20 mod 6 = 2
Non so pertanto come interpretare il teorema, potreste gentilmente guidarmi passo passo per cercare di capire come approcciare agli esercizi che si presentano in questa forma.
Esiste un procedimento valido per tutti i casi per risolvere queste equazioni?
Grazie anticipatamente a tutti coloro che mi daranno un aiuto anche solo parziale,
Ciao!,
Simone
Risposte
"demu":
"L’equazione ax ≡n b ammette soluzioni se e solo se il massimo comune divisore d di a e n divide b."
Simone
"demu":
il quale secondo il teorema sopra citato, essendo MCD(11,20) = 1, quindi con a ed n coprimi, mi sarei aspettato che appunto non ammettesse soluzioni, eppure:
...appunto, $d=M.C.D.(11,20)=1$ non divide $b=6$ ?
Ciao.
11 e 20 sono coprimi e tutti I numeri in Z sono divisibili per 1, per questo motivo ho interpretato la frase come MCD diverso da 1.
Algibro ti ringrazio della risposta, ti posso gentilmente chiedere un esempio in cui il massimo comune divisore d di a e n non divide b?
Inoltre quale procedinento devo seguire per trovare x?
Algibro ti ringrazio della risposta, ti posso gentilmente chiedere un esempio in cui il massimo comune divisore d di a e n non divide b?
Inoltre quale procedinento devo seguire per trovare x?
"demu":
Algibro ti ringrazio della risposta, ti posso gentilmente chiedere un esempio in cui il massimo comune divisore d di a e n non divide b?
Ma è come dici tu, basta avere due interi il cui massimo comun divisore non divida $b$.
Ad esempio se abbiamo $4x \equiv 5 (mod 2)$ il $M.C.D.(4,2)=2$ ma $2$ non divide $5$.
"demu":
Inoltre quale procedinento devo seguire per trovare x?
Se hai $ax \equiv b (mod m)$ puoi ad esempio chiederti se $a_m$ è invertibile in $ZZ_m$, ovvero, sfruttando l'identità di Bézout ricavi il massimo comun divisore, verifichi che divida $b$ e tramite l'algoritmo di Euclide per il massimo comun divisore trovi una soluzione per $x$.
E poi, riguardando il tuo esercizio, non dovevi calcolare il massimo comun divisore di $(11,20)$ !
Allora,
$11x \equiv 20 (mod 6)$
$11x+6k=20$ (Bézout)
$M.C.D.(11,6)=1=11(-1)+6(2)$ (tramite algoritmo divisione euclidea)
Così abbiamo $11(-1 * 20)+6(2 * 20)=20$ e $x=-20 \equiv 4 (mod 6)$.
Ovviamente soddisfano l'equazione tutte le $x$ dell'insieme ${6k+4 : k \in ZZ}$.
Allora,
$11x \equiv 20 (mod 6)$
$11x+6k=20$ (Bézout)
$M.C.D.(11,6)=1=11(-1)+6(2)$ (tramite algoritmo divisione euclidea)
Così abbiamo $11(-1 * 20)+6(2 * 20)=20$ e $x=-20 \equiv 4 (mod 6)$.
Ovviamente soddisfano l'equazione tutte le $x$ dell'insieme ${6k+4 : k \in ZZ}$.
Grazie mille per il supporto, ma ho ancora qualche dubbio sul procedimento:
Effettuando il [formule]M.C.D(11,6)[/formule] tramite l'algoritmo di divisione euclidea ottengo:
[formule]11=6*1+5[/formule]
[formule]6=5*1+1[/formule]
come lo hai portato in forma 11(−1⋅20)+6(2⋅20)=20 ?
Effettuando il [formule]M.C.D(11,6)[/formule] tramite l'algoritmo di divisione euclidea ottengo:
[formule]11=6*1+5[/formule]
[formule]6=5*1+1[/formule]
come lo hai portato in forma 11(−1⋅20)+6(2⋅20)=20 ?
$11=6*1+5$
$6=5*1+1$
Andando a ritroso $1=6(1)+5(-1)$
Sostituisco $5$ con $11(1)+6(-1)$ che ricavo dalla prima, e ottengo $1=6(1)+11(-1)+6(1)=11(-1)+6(2)$
Ora, da $11(-1)+6(2)=1$ moltiplico ambo i membri per $20$ al fine di ottenere $11(-1*20)+6(2*20)=20$
$6=5*1+1$
Andando a ritroso $1=6(1)+5(-1)$
Sostituisco $5$ con $11(1)+6(-1)$ che ricavo dalla prima, e ottengo $1=6(1)+11(-1)+6(1)=11(-1)+6(2)$
Ora, da $11(-1)+6(2)=1$ moltiplico ambo i membri per $20$ al fine di ottenere $11(-1*20)+6(2*20)=20$
Grazie, Ho apprezzo molto il tuo aiuto!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo