Semplice dim di una congruenza
Sto leggendo il libro Che cos'è la matematica, ma non studio matematica
Potete aiurarmi con la dimostraziond richiesta
Potete aiurarmi con la dimostraziond richiesta
Risposte
Se ab è congruo ad ac e a non è congruo a zero ( mod n), con n numero primo, allora b è congruo a c
Vi chiedo anche se questo sia l'unico modo di risolvere i tre esercizi finali : in ciascuno ho calcolato il prodotto, l'ho diviso per il modulo e quindi o il resto stesso della divisione, che è congruo al prodotto, è tra i numeri dati oppure faccio la prova e vedo quale tra i numeri dati dia lo stesso resto quando diviso per il modulo
Ciao!
$ab \equiv ac \mod n \iff ab - ac \equiv 0 \mod n \iff a(b-c) \equiv 0 \mod n$, continua tu. Come puoi procedere?
Puoi fare anche così per esempio:
$11 * 18 * 2322 * 13 * 19 \equiv ? mod 7$
Innanzitutto nota che $11 \equiv 4 \mod 7$, $18 \equiv 4 \mod 7$, $13 \equiv -1 \mod 7$, $19 \equiv -2 \mod 7$ infine, facendo la divisione euclidea fra $2322$ si ottiene che $2322 = 7*331 + 5$ dunque $2322 \equiv 5 \mod 7$, mettendo insieme i pezzi si ha che:
$11 * 18 * 2322 * 13 * 19 \equiv 4 * 4 * 5 * -1 * -2 \equiv -8 * 4 * 5 * -1 \equiv 8* 4* 5 \equiv 1*20 \equiv 20 \equiv -1 \equiv 6 \mod 7$
Se hai dubbi chiedi pure
"Lavinia Volpe":
Se ab è congruo ad ac e a non è congruo a zero ( mod n), con n numero primo, allora b è congruo a c
$ab \equiv ac \mod n \iff ab - ac \equiv 0 \mod n \iff a(b-c) \equiv 0 \mod n$, continua tu. Come puoi procedere?
"Lavinia Volpe":
Vi chiedo anche se questo sia l'unico modo di risolvere i tre esercizi finali : in ciascuno ho calcolato il prodotto, l'ho diviso per il modulo e quindi o il resto stesso della divisione, che è congruo al prodotto, è tra i numeri dati oppure faccio la prova e vedo quale tra i numeri dati dia lo stesso resto quando diviso per il modulo
Puoi fare anche così per esempio:
$11 * 18 * 2322 * 13 * 19 \equiv ? mod 7$
Innanzitutto nota che $11 \equiv 4 \mod 7$, $18 \equiv 4 \mod 7$, $13 \equiv -1 \mod 7$, $19 \equiv -2 \mod 7$ infine, facendo la divisione euclidea fra $2322$ si ottiene che $2322 = 7*331 + 5$ dunque $2322 \equiv 5 \mod 7$, mettendo insieme i pezzi si ha che:
$11 * 18 * 2322 * 13 * 19 \equiv 4 * 4 * 5 * -1 * -2 \equiv -8 * 4 * 5 * -1 \equiv 8* 4* 5 \equiv 1*20 \equiv 20 \equiv -1 \equiv 6 \mod 7$
Se hai dubbi chiedi pure
Grazie!
Ovviamente si procede notando che uno dei due fattofi dev'essere congruo a zero, poiché il modulo è primo, e non potendo essere a per ipotesi, lo è b-c, il che implica che b è congruo a c.
Sicuramente avrò altri dubbi presto xD
Ovviamente si procede notando che uno dei due fattofi dev'essere congruo a zero, poiché il modulo è primo, e non potendo essere a per ipotesi, lo è b-c, il che implica che b è congruo a c.
Sicuramente avrò altri dubbi presto xD
Come al solito non riesco a dimostrare
E poi non ho capito perché prima dice che e dev'essere un divisore di p-1 e poi invece mette una formula in cui la divisione di p-1 per e ha un resto, r
Pag 84 es 3
E poi non ho capito perché prima dice che e dev'essere un divisore di p-1 e poi invece mette una formula in cui la divisione di p-1 per e ha un resto, r
Pag 84 es 3
"Lavinia Volpe":
Come al solito non riesco a dimostrare
E poi non ho capito perché prima dice che e dev'essere un divisore di p-1 e poi invece mette una formula in cui la divisione di p-1 per e ha un resto, r
Pag 84 es 3
Probabilmente ho un'edizione diversa dalla tua ma comunque ti consiglio sempre di riportare il testo del problema(Se hai problemi con le formule leggi questo topic) in modo tale da aumentare la probabilità che ti aiutino(e magari evitare di essere richiamata da un moderatore).
Passando al problema, che penso sia questo:
Dimostrare il teorema generale: il più piccolo numero intero positivo $ee$ per cui $a^e \equiv 1 \mod p$ deve essere un divisore di $p-1$(Suggerimento: dividendo $p-1$ per $e$ si ha $p-1 = k*e + r$ con $ 0 <= r < e$- Sfruttare il fatto che $a^(p-1) \equiv a^e \equiv 1 \mod p$)
Noi che dobbiamo dimostrare che $e | p-1$, per cui facciamo la divisione euclidea: $p-1 = k*e + r$ con $ 0 <= r < e$, dunque bisogna dimostrare che $r = 0$. Ti faccio notare che $e$ è il più piccolo numero intero positivo per cui $a^e \equiv 1 \mod p$ e $0<= r < e$. Adesso: $a^(p-1) \equiv 1 \mod p$ per Fermat, ma $a^(p-1) = a^(k*e + r)$ dunque $a^(p-1) \equiv a^(k*e + r) \equiv a^(k*e) * a^r \equiv 1 \mod p$, da cui ...
Boh adesso non riesco, ci penso un po' :/
Es pg 87 n 1 non mi è uscito! : $ 6^2=36-= 13 (mod 23) $ . 23 è un residuo quadratico (mod 13)?
$ (13-1)/2 ((23-1)/2)=6*11=66 $ pari, quindi dovrebbe essere un residuo quadratico, ma $ 23= 13* 1 + 10 $ e 10 non è un quadrato..
Comunque vorrei fare altre domande sull'argomento, continuo qui per non aprire un nuovo post
Es pg 87 n 2 non so se è giusto: far vede che le sole congruenze tra i numeri $1^2, 2^2, 3^2,...,(p-1)^2 $ sono $ X ^2-= (p-x)^2 $
Se $ n^2 $ è congruo a $ x^2 $, allora n è congruo a x , ossia $ n/p= a+ r; x/p= b+r $, con r compreso tra 1 e (p-1)
Poiché anche x e n sono compresi tra 1 e p-1 e sono diversi, r non può che essere uguale a essi
Es pg 87 n 1 non mi è uscito! : $ 6^2=36-= 13 (mod 23) $ . 23 è un residuo quadratico (mod 13)?
$ (13-1)/2 ((23-1)/2)=6*11=66 $ pari, quindi dovrebbe essere un residuo quadratico, ma $ 23= 13* 1 + 10 $ e 10 non è un quadrato..
Comunque vorrei fare altre domande sull'argomento, continuo qui per non aprire un nuovo post
Es pg 87 n 2 non so se è giusto: far vede che le sole congruenze tra i numeri $1^2, 2^2, 3^2,...,(p-1)^2 $ sono $ X ^2-= (p-x)^2 $
Se $ n^2 $ è congruo a $ x^2 $, allora n è congruo a x , ossia $ n/p= a+ r; x/p= b+r $, con r compreso tra 1 e (p-1)
Poiché anche x e n sono compresi tra 1 e p-1 e sono diversi, r non può che essere uguale a essi
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo