CLASSI DI RESTO 2

[agata6]

SCUSATE SE VI CHEDO UNA MANO SULLO STESSO ARGOMENTO DI PRIMA.. MA NON RIESCO AD ANDARE AVANTI

TROVARE IL RESTO PER 30 DEL NUMERO 253^146

253-=13(MOD30) E DOPO ESSERMI CALCOLATA LA PHI DI EULERO SONO ARRIVATA AD UN PUNTO CRUCIALE

(13^8)^18 * 13^2 = 1^18 * 13^2

ORA IL RISULTATO DOVREBBE ESSERE 19
MA DA 13^2 COME è ARRIVATO A 19??????
PLEASEEE AIUTATEMIIIIIIIIIIIIII

[miuemia]

ma $13^2=169=19$ modulo $30$....

[agata6]

ragazzi una curiosità ma se non sono coprimi (la base e il modulo) posso applicare lo stesso fermat eulero oppure devo applicare un altro metodo??????

[TomSawyer1]

Devi arrangiarti in un altro modo, perche' la condizione necessaria e sufficiente per applicare il Teorema di Euler e' che la base e il modulo siano coprimi.

Se hai una cosa del genere $6^100 \equiv x (mod15)$, per esemopio, hai che $\gcd(6,15)>1$, quindi non potresti applicarlo, ma puoi applicare il Teorema Cinese dei Resti, dividendo la congruenza in
$6^100\equiv x (mod3)$
$6^100\equiv x (mod5)$

Dalla prima ottieni $x\equiv 0 (mod3)$ e dalla seconda $6^100\equiv (6^25)^4\equiv1\equiv x(mod5)$, quindi $x\equiv 1 (mod5)$, quindi metti a sistema le due soluzioni e ottieni $x=6+15k$.