Proprietà congruenza moduli
Ciao a tutti 
oggi sono alle prese con questo dubbio: ho un libro che, elencando le proprietà delle congruenze dei moduli, dice:
"Le congruenze si comportano bene rispetto a somma, sottrazione e prodotto. Infatti:
$a -= b , c -= d , ( mod m ) rArr a * c -= b * d ( mod m )$
inoltre, più avanti
"In una congruenza
del tipo $a * c -= b * c (mod m )$ si può semplificare per c e ottenere $a ≡ b (mod m )$ solo se
M C D(c , m ) = 1; risultato che si ottiene semplicemente moltiplicando i due membri per
l’inverso di c .In caso contrario, è comunque possibile una semplificazione, facendo attenzione a
dividere però anche il modulo:
$a * c -= b * c ( mod m * c ) rArr a -= b ( mod m )$
c'è qualcosa però che evidentemente mi sfugge, perchè se io scrivo
$ 21 -= x ( mod 6) rArr 21 * 2 -= x * 2 (mod 6) rArr 21 -= x (mod 3) rArr x = 0$, ma $21 -= 3 mod 6$..
dov'è che sbaglio?
ps ma come si inserisce uno spazio bianco in LaTex?
Grazie
oggi sono alle prese con questo dubbio: ho un libro che, elencando le proprietà delle congruenze dei moduli, dice:
"Le congruenze si comportano bene rispetto a somma, sottrazione e prodotto. Infatti:
$a -= b , c -= d , ( mod m ) rArr a * c -= b * d ( mod m )$
inoltre, più avanti
"In una congruenza
del tipo $a * c -= b * c (mod m )$ si può semplificare per c e ottenere $a ≡ b (mod m )$ solo se
M C D(c , m ) = 1; risultato che si ottiene semplicemente moltiplicando i due membri per
l’inverso di c .In caso contrario, è comunque possibile una semplificazione, facendo attenzione a
dividere però anche il modulo:
$a * c -= b * c ( mod m * c ) rArr a -= b ( mod m )$
c'è qualcosa però che evidentemente mi sfugge, perchè se io scrivo
$ 21 -= x ( mod 6) rArr 21 * 2 -= x * 2 (mod 6) rArr 21 -= x (mod 3) rArr x = 0$, ma $21 -= 3 mod 6$..
dov'è che sbaglio?
ps ma come si inserisce uno spazio bianco in LaTex?
Grazie
Risposte
l'errore è che quello che ottieni alla fine è x congruo a 0 modulo 3,che è vero
ah, certo, $ x != 0$, ma $x -= 0 \ (mod \ 3)$..
quindi se cerco di trovare il resto di una divisione di un numero N per un numero composto m, mi basta trovare la soluzione al sistema
$ { ( x -= \ N \ (mod \ p1) ),( x-=\ N\ (mod \ p2) ),( x -=\ N \ (mod \ p3) ):} $ ecc.
dove $p1*p2*p3*...*pn = m$, giusto?
però il metodo è abbastanza laborioso; non c'è niente di meglio?
per esempio, se ti trovassi a dover calcolare
$2618259\ (\ mod \ 75)$, cosa faresti?
grazie
quindi se cerco di trovare il resto di una divisione di un numero N per un numero composto m, mi basta trovare la soluzione al sistema
$ { ( x -= \ N \ (mod \ p1) ),( x-=\ N\ (mod \ p2) ),( x -=\ N \ (mod \ p3) ):} $ ecc.
dove $p1*p2*p3*...*pn = m$, giusto?
però il metodo è abbastanza laborioso; non c'è niente di meglio?
per esempio, se ti trovassi a dover calcolare
$2618259\ (\ mod \ 75)$, cosa faresti?
grazie
"ant.py":
per esempio, se ti trovassi a dover calcolare
$2618259\ (\ mod \ 75)$, cosa faresti?
grazie
Farei la divisione intera tra 2618259 e 75 e poi prenderei il resto.
$2618259: 75= 34910$ con resto $9$, quindi $2618259 -= 9\ (\ mod \ 75)$
va beh senza svolgere la divisione
per esempio, essendo $75 = 5 ^ 2 * 3$, e sapendo che $2618259 -= 0 \ (mod\ 3)$ e che $2618259 -= 9 \ (mod\ 25)$ (e ovviamente $2618259 -= 4 \ (mod \ 5)$ ), come trovare velocemente il resto di $2618259 \ (mod\ 5^2*3)$?
Va beh non c'è un modo immediato ed è comunque più conveniente la divisione farò anch'io così però pensavo potesse esserci qualcosa
per esempio, essendo $75 = 5 ^ 2 * 3$, e sapendo che $2618259 -= 0 \ (mod\ 3)$ e che $2618259 -= 9 \ (mod\ 25)$ (e ovviamente $2618259 -= 4 \ (mod \ 5)$ ), come trovare velocemente il resto di $2618259 \ (mod\ 5^2*3)$?
Va beh non c'è un modo immediato ed è comunque più conveniente la divisione farò anch'io così
però pensavo potesse esserci qualcosa
si che c'è un modo più immediato!
http://en.wikipedia.org/wiki/Chinese_remainder_theorem
in pratica questo teorema cinese del resto dice che puoi spezzare una congruenza modulo n in tante congruenze modulo le potenze dei primi che dividono n (in pratica quello che hai fatto tu) e poi ricostruire il tutto modulo n mantenendo l'unicità della soluzione. Ad esempio in questo caso devi trovare $x\equiv 2618259 \mod 75$. Spezzando il sistema ottieni
$x\equiv 9 mod 25$ e $x\equiv 0 mod 3$. Per ricostruire il sistema ci sono molte tecniche (nel link credo ne sia illustrata una) ma in questo caso il modo più veloce è questo: la soluzione finale è modulo 75 e quindi x<75, poichè x è congruo a 9 modulo 25 x può essere solo 9,34,59 e l'unico di questi divisibili per 3 è 9. Segue che x=9 e quindi $2618259\equiv 9 mod 75$
soddisfatto?
http://en.wikipedia.org/wiki/Chinese_remainder_theorem
in pratica questo teorema cinese del resto dice che puoi spezzare una congruenza modulo n in tante congruenze modulo le potenze dei primi che dividono n (in pratica quello che hai fatto tu) e poi ricostruire il tutto modulo n mantenendo l'unicità della soluzione. Ad esempio in questo caso devi trovare $x\equiv 2618259 \mod 75$. Spezzando il sistema ottieni
$x\equiv 9 mod 25$ e $x\equiv 0 mod 3$. Per ricostruire il sistema ci sono molte tecniche (nel link credo ne sia illustrata una) ma in questo caso il modo più veloce è questo: la soluzione finale è modulo 75 e quindi x<75, poichè x è congruo a 9 modulo 25 x può essere solo 9,34,59 e l'unico di questi divisibili per 3 è 9. Segue che x=9 e quindi $2618259\equiv 9 mod 75$
soddisfatto?
adesso si
quindi imposto il sistema e vedo se è veloce trovare una soluzione con il metodo che hai usato tu, altrimenti cerco qualche altro metodo algebrico
grazie, mi sono chiarito un paio di dubbi con questa discussione
quindi imposto il sistema e vedo se è veloce trovare una soluzione con il metodo che hai usato tu, altrimenti cerco qualche altro metodo algebrico
grazie, mi sono chiarito un paio di dubbi con questa discussione
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo