Congruenza
ciao a tutti, qualcuno mi sa dare risposta a questa domanda?
Spiegare come mai per ogni $a$ appartenente a $Z$ vale $a^561 -= a mod 561$
grz 1000
Spiegare come mai per ogni $a$ appartenente a $Z$ vale $a^561 -= a mod 561$
grz 1000
Risposte
Applichiamo il teorema (piccolo) di Fermat, osservando che [tex]561=11\cdot 51[/tex] allora sappiamo che l'uguaglianza vale [tex]\forall a \in \mathbb N: \gcd(a,561)=1[/tex], tutto sta a verificare per i due valori [tex]11,561[/tex] (e multipli, ma per ora bastano i due):
[tex]11^{11}= 285311670611 \equiv 539 \pmod {561}[/tex]
[tex]539 \equiv -22 \pmod {561}[/tex]
[tex]11^{561}\equiv {-22}^{51}= 2^{51}\cdot 11^{51} \equiv 2^{56}\cdot 22^4 \cdot 11^7 \pmod {561}[/tex]
[tex]2^{60}\cdot 11^{11} \equiv 2^{60} \cdot (-22) \equiv -352 \equiv 209\pmod {561}[/tex]
e qui vedi che l'equivalenza non vale! Reputo che il caso con il [tex]51[/tex] sia analogo!
... Sempre che questa marea di conti sia corretta...
[tex]11^{11}= 285311670611 \equiv 539 \pmod {561}[/tex]
[tex]539 \equiv -22 \pmod {561}[/tex]
[tex]11^{561}\equiv {-22}^{51}= 2^{51}\cdot 11^{51} \equiv 2^{56}\cdot 22^4 \cdot 11^7 \pmod {561}[/tex]
[tex]2^{60}\cdot 11^{11} \equiv 2^{60} \cdot (-22) \equiv -352 \equiv 209\pmod {561}[/tex]
e qui vedi che l'equivalenza non vale! Reputo che il caso con il [tex]51[/tex] sia analogo!
... Sempre che questa marea di conti sia corretta...
@Lord K: A me viene che $11^561-=11_(mod 561)$
Penso che l'errore che hai commesso sia qui:
Penso che l'errore che hai commesso sia qui:
"Lord K":Hai dimenticato di portarti dietro il $-$
[tex]11^{561}\equiv {-22}^{51}= 2^{51}\cdot 11^{51}[/tex]
...Ecco appunto. Grazie Gi8!
Provo a dimostrare che $11^561-=11_(mod 561)$
Sappiamo che $11^11-= -22_(mod 561)=>
$11^561-=(-22)^51_(mod 561)=>
$=> 11^561=-[2^51*11^51]_(mod 561)-=-[2^51*11^44*11^7]_(mod 561)-=-[2^51*11^7*(-22)^4]_(mod 561)-=-[2^55*11^11]_(mod 561)-=-[2^55*(-22)]-=2^56*11_(mod 561)$
Quindi $11^561-=2^56*11_(mod 561)$
Ora, $2^8-=1_(mod 51)$ (infatti $255=2^8-1$ e $255$ è multiplo di $51$) e da questo si deduce che $2^56-=1_(mod 51)$ (perchè $2^56=(2^8)^7$)
Quindi $2^56*11-=11_(mod 561)=> 11^561-=11_(mod 561)$
Sappiamo che $11^11-= -22_(mod 561)=>
$11^561-=(-22)^51_(mod 561)=>
$=> 11^561=-[2^51*11^51]_(mod 561)-=-[2^51*11^44*11^7]_(mod 561)-=-[2^51*11^7*(-22)^4]_(mod 561)-=-[2^55*11^11]_(mod 561)-=-[2^55*(-22)]-=2^56*11_(mod 561)$
Quindi $11^561-=2^56*11_(mod 561)$
Ora, $2^8-=1_(mod 51)$ (infatti $255=2^8-1$ e $255$ è multiplo di $51$) e da questo si deduce che $2^56-=1_(mod 51)$ (perchè $2^56=(2^8)^7$)
Quindi $2^56*11-=11_(mod 561)=> 11^561-=11_(mod 561)$
\( a^3 \equiv a \) \( mod 3\) quindi : \( a^{561} \equiv (a^3)^{187} \equiv a^{187} \equiv (a^3)^{62}a\equiv a^{63} \equiv a^{21} \equiv a^{7}\equiv (a^3)^2a \equiv a^3 \equiv a\) \( mod 3\)
\( a^{11} \equiv a \) \( mod 11 \) quindi : \( a^{561} \equiv (a^{11})^{51} \equiv a^{51} \equiv (a^{11})^4 a^7 \equiv a^4 a^7 \equiv a^{11} \equiv a\) \( mod 11\)
\( a^{17} \equiv a \) \( mod 17\) quindi : \( a^{561} \equiv (a^{17})^{33} \equiv a^{33} \equiv a^{17} a^{16} \equiv a a^{16} \equiv a^{17} \equiv a\) \( mod 17\)
Ed essendo \( 3,1,17\) a due a due primi tra loro abbiamo:
\( a^{561} \equiv a\) \( mod \mbox{ }3\cdot 11\cdot17 = 561\)
\( a^{11} \equiv a \) \( mod 11 \) quindi : \( a^{561} \equiv (a^{11})^{51} \equiv a^{51} \equiv (a^{11})^4 a^7 \equiv a^4 a^7 \equiv a^{11} \equiv a\) \( mod 11\)
\( a^{17} \equiv a \) \( mod 17\) quindi : \( a^{561} \equiv (a^{17})^{33} \equiv a^{33} \equiv a^{17} a^{16} \equiv a a^{16} \equiv a^{17} \equiv a\) \( mod 17\)
Ed essendo \( 3,1,17\) a due a due primi tra loro abbiamo:
\( a^{561} \equiv a\) \( mod \mbox{ }3\cdot 11\cdot17 = 561\)
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo