Calcolare se risulta $86^27$ $-=$ $13^992$ mod 6
Ciao, ho un dubbio su questo tipo di esercizio: Calcolare se risulta $86^27$ $-=$ $13^992$ mod 6 Io lo risolverei così:
Riduco le basi mod 6 $\rightarrow$ $2^27$ $-=$ 1 mod 6
Dato che il modulo non è un numero primo non posso usare il teorema di Fermat. L'MCD(2,6) =2 quindi non sono primi e non posso ridurre l'esponente del primo membro per $\phi$(6) secondo il teorema di Eulero-Fermat.
In che modo si procede quando non posso usare i due teoremi sopra citati?
Ho provato a scomporre l'esponente così: $2^27$=$2^3$x$2^24$$-=$2($2^23$) è giusto? Ma ora che ho un esponente primo come si procede?
C'è un metodo generale per risolvere questo tipo di esercizi?
Grazie a chi mi aiuterà!
Riduco le basi mod 6 $\rightarrow$ $2^27$ $-=$ 1 mod 6
Dato che il modulo non è un numero primo non posso usare il teorema di Fermat. L'MCD(2,6) =2 quindi non sono primi e non posso ridurre l'esponente del primo membro per $\phi$(6) secondo il teorema di Eulero-Fermat.
In che modo si procede quando non posso usare i due teoremi sopra citati?
Ho provato a scomporre l'esponente così: $2^27$=$2^3$x$2^24$$-=$2($2^23$) è giusto? Ma ora che ho un esponente primo come si procede?
C'è un metodo generale per risolvere questo tipo di esercizi?
Grazie a chi mi aiuterà!
Risposte
Potresti studiarti le congruenze modulo 2 e modulo 3 che risultano molto comode da fare...
Come dice Gatto89 modulo 2 e modulo 3 separatamente è buona idea.
Altrimenti, tu stesso hai visto che $2^3\equiv2$
Quindi (puoi elevare alla nona), $2^27\equiv2^9$
Già $2^9$ è ragionevole e si calcola facilmente a mano, ma se non vuoi "sporcarti" scendi ancora usando lo stesso metodo
Altrimenti, tu stesso hai visto che $2^3\equiv2$
Quindi (puoi elevare alla nona), $2^27\equiv2^9$
Già $2^9$ è ragionevole e si calcola facilmente a mano, ma se non vuoi "sporcarti" scendi ancora usando lo stesso metodo
Intanto grazie per le risposte. Seguendo il suggerimento di Steven ho ridotto l'esponente cosi: $2^27$ $-=$ $2^9$ x $2^18$ $-=$ 2($2^17$) $-=$ 2($2^9$) x $2^8$ $-=$ $2^2$ x $2^8$ $-=$ $2^10$ $-=$ $2^9$ x 2 $-=$ 4 quindi risutla 4 $-=$ 1 quindi non è verificata. Potete dirmi se ho sbagliato qualcosa?
Non ho capito invece il suggerimento di Gatto89, dovrei risolvere la congruenza una volta con il modulo 2 e una con modulo 3?
Non ho capito invece il suggerimento di Gatto89, dovrei risolvere la congruenza una volta con il modulo 2 e una con modulo 3?
Beh se devi controllare l'uguaglianza $x \equiv y (mod$ $ab)$, se e solo se $a$ e $b$ sono coprimi, ti basta mostrare che $x \equiv y (mod$ $a)$ e $x \equiv y (mod$ $b)$.
Infatti: $x \equiv y (mod$ $ab)$ $\Leftrightarrow$ $ab| (x-y)$ $\Leftrightarrow$ (e qui applichi il fatto che sono coprimi) $a|(x-y)$ e $b|(x-y)$ $\Leftrightarrow$ $x \equiv y (mod$ $a)$ e $x \equiv y (mod$ $b)$.
Ripeto, importante, che non vale se $MCD(a,b)!=1$, infatti prendendo $a=b=2$ hai che $2 \equiv 4 (mod$ $2)$ ma chiaramente $2 != 4 (mod$ $4)$...
Nel tuo caso $6 = 2\cdot3$ che sono coprimi, quindi puoi studiare le congruenze separate che sono molto semplici...
Infatti: $x \equiv y (mod$ $ab)$ $\Leftrightarrow$ $ab| (x-y)$ $\Leftrightarrow$ (e qui applichi il fatto che sono coprimi) $a|(x-y)$ e $b|(x-y)$ $\Leftrightarrow$ $x \equiv y (mod$ $a)$ e $x \equiv y (mod$ $b)$.
Ripeto, importante, che non vale se $MCD(a,b)!=1$, infatti prendendo $a=b=2$ hai che $2 \equiv 4 (mod$ $2)$ ma chiaramente $2 != 4 (mod$ $4)$...
Nel tuo caso $6 = 2\cdot3$ che sono coprimi, quindi puoi studiare le congruenze separate che sono molto semplici...
Grazie mille Gatto89 ora è tutto chiaro!
Certo, ti basta che una non sia verificata perchè non sia verificato tutto... pensa al significato di congruenza!
Prendo il tuo esempio:
$14 \equiv (78)^(129)$ $(mod $$10)$ significherebbe che $10|14-78^(129)$ ovvero che $(14-78^(129))/10$ è intero.
Il fatto che non sia verificata $14 \equiv (78)^(129)$ $(mod $$5)$ significa che $5$ non divide $14-78^(129)$, ma allora può dividerlo $10$? Ovvero, può essere intero $(14-78^(129))/10$ = $1/2(14-78^(129))/5$ se non è intero $(14-78^(129))/5$?
Edit: Non mi editare i post però sennò sembra che parlo da solo
Prendo il tuo esempio:
$14 \equiv (78)^(129)$ $(mod $$10)$ significherebbe che $10|14-78^(129)$ ovvero che $(14-78^(129))/10$ è intero.
Il fatto che non sia verificata $14 \equiv (78)^(129)$ $(mod $$5)$ significa che $5$ non divide $14-78^(129)$, ma allora può dividerlo $10$? Ovvero, può essere intero $(14-78^(129))/10$ = $1/2(14-78^(129))/5$ se non è intero $(14-78^(129))/5$?
Edit: Non mi editare i post però sennò sembra che parlo da solo
Ho letto il post e ho pensato 
mi ha letto nel pensiero.... L'ho editato perchè quando avevo capito la risposta alla mia domanda avevo già postato. Ti ringrazio ancora della tua risposta sempre più esauriente
mi ha letto nel pensiero.... L'ho editato perchè quando avevo capito la risposta alla mia domanda avevo già postato. Ti ringrazio ancora della tua risposta sempre più esauriente
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo