Dimostrazione congruenze
salve devo dimostrare che $ax=b (mod m)$ se e solo se $(a,m)|b$
allora chiamo $(a,m)=d$
scrivo $d=as+tm$ (per Bezout) e arrivo a questo punto: $db=a(sb) (mod m)$ ora posso semplificare dividendo per $d$? poiché ottengo numeri interi: $b=a(sb/d) (mod m)$ e quindi mi sono trovato una soluzione?
allora chiamo $(a,m)=d$
scrivo $d=as+tm$ (per Bezout) e arrivo a questo punto: $db=a(sb) (mod m)$ ora posso semplificare dividendo per $d$? poiché ottengo numeri interi: $b=a(sb/d) (mod m)$ e quindi mi sono trovato una soluzione?
Risposte
$ax-=b_(mod n) <=> d|b$, dove $d=(a,n)$.
1) $ax-=b_(mod n) => d|b$
$ax-=b_(mod n)$ significa che $n|ax-b$ ossia $EEy in ZZ$ tale che $ax-ny=b$.
Per ipotesi $d=MCD(a,n) => d|a ^^ d|n$ quindi $EEa^{\prime}, n^{\prime} in ZZ$ tali che $a=a^{\prime}*d$ e $n=n^{\prime}*d$
che sostituiti a $ax-ny=b$ diventa: $a^{\prime}dx-n^{\prime}dy=b$ e $d(a^{\prime}x-n^{\prime}y)=b$ da cui l'ipotesi che $d|b$.
2) $d|b => ax-=b_(mod n)$
Da Bèzout si ha che $EEx,y in ZZ$ tali che $ax+ny=d$; per ipotesi $d|b$ quindi $EEb^{\prime} in ZZ$ tale che $b=b^{\prime}*d$
e $d=b/b^{\prime}$, che sostituito e semplificato si ha $axb^{\prime}+nyb^{\prime}=b$ da cui l'ipotesi $ab^{\prime}x-=b_(mod nb^{\prime})$
1) $ax-=b_(mod n) => d|b$
$ax-=b_(mod n)$ significa che $n|ax-b$ ossia $EEy in ZZ$ tale che $ax-ny=b$.
Per ipotesi $d=MCD(a,n) => d|a ^^ d|n$ quindi $EEa^{\prime}, n^{\prime} in ZZ$ tali che $a=a^{\prime}*d$ e $n=n^{\prime}*d$
che sostituiti a $ax-ny=b$ diventa: $a^{\prime}dx-n^{\prime}dy=b$ e $d(a^{\prime}x-n^{\prime}y)=b$ da cui l'ipotesi che $d|b$.
2) $d|b => ax-=b_(mod n)$
Da Bèzout si ha che $EEx,y in ZZ$ tali che $ax+ny=d$; per ipotesi $d|b$ quindi $EEb^{\prime} in ZZ$ tale che $b=b^{\prime}*d$
e $d=b/b^{\prime}$, che sostituito e semplificato si ha $axb^{\prime}+nyb^{\prime}=b$ da cui l'ipotesi $ab^{\prime}x-=b_(mod nb^{\prime})$
ma nel 2) alla fine ti viene ab'x=b (modnb') invece deve essere (modn); il mio ragionamento andava bene? e la mia domanda è si può dividere db=a(sb) (modn) per d sapendo che i risultati sono numeri interi?
Nella dimostrazione dell'implicazione inversa la tesi è esattamente la stessa di quella "richiesta". Il tuo ragionamento non l'ho ben capito, potresti argomentarlo passo per passo ?
quindi dire $ab'x=b (mod n)$ (la tesi) è la stessa cosa che dire $ab'x=b (mod nb')$ con il modulo diverso? io ho fatto così l'inversa: $d=(a,m)$ e $b=b'*d$ quindi scrivo per Bézout (1)$d=as+tm$; ora moltiplico per $b$ e mi viene (2)$bd=asb+tmb$; segue (3)$bd-asb=tmb$; quindi (4)$bd=asb (mod m)$ ora la mia domanda è si può dividere per $d$ così da ottenere $b=a(sb/d) (mod m)$? oppure dovevo scrivere al passaggio (4) $bd=asb (mod mb)$ e quindi dividendo per d anche il modulo ottengo $b=a(sb/d) (mod mb')$? ma i moduli sono diversi..
Una conseguenza che $d=(a,n)$ divide $b$ è che, per definizione di massimo comune divisore stesso, puoi dividere tutti i membri dell'equazione congruenziale per $d$, arrivando ad ottenere un'equazione nella forma $ax-=b_(mod n)$ con $(a,n)=1$, che sappiamo avere soluzione.
Anche se i moduli son diversi ottieni comunque la stessa soluzione.
Anche se i moduli son diversi ottieni comunque la stessa soluzione.
"simo90":
quindi dire $ab'x=b (mod n)$ (la tesi) è la stessa cosa che dire $ab'x=b (mod nb')$ con il modulo diverso? io ho fatto così l'inversa: $d=(a,m)$ e $b=b'*d$ quindi scrivo per Bézout (1)$d=as+tm$; ora moltiplico per $b$ e mi viene (2)$bd=asb+tmb$; segue (3)$bd-asb=tmb$; quindi (4)$bd=asb (mod m)$ ora la mia domanda è si può dividere per $d$ così da ottenere $b=a(sb/d) (mod m)$? oppure dovevo scrivere al passaggio (4) $bd=asb (mod mb)$ e quindi dividendo per d anche il modulo ottengo $b=a(sb/d) (mod mb')$? ma i moduli sono diversi..
Comunque va bene anche come hai fatto tu; prova direttamente con un esempio per vedere se funziona: $3x-=9_(mod 6)$
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo