Matematicamente.it

Ciao,
scusatemi ma sto incontrando varie difficoltà nel capire come svolgere esercizi come: calcolare x = 13^1234 mod 105
Potreste gentilmente spiegarmi come impostare questi esercizi?
Avete qualche dispensa con esercizi di questo tipo?

Grazie

Ciao, possiamo ragionare in questo modo: \[
13^4 \mod 105 = 1
\] $1234 = 4*308 + 2$, quindi vuol dire che ci sono $308$ "pezzi" che fanno sempre $1$. Il risultato parziale è quindi $1^(308) = 1$. Rimangono fuori due pezzi da $13$, quindi il risultato finale è \[
13^2 \mod 105 = 64
\] Diciamo che quindi una buona strategia è quella di spezzare un problema grande in tanti problemi piccoli.

Ciao,
intanto grazie per la risposta.
Purtroppo non mi trovo granchè, perchè l'esercizio l'ho preso dal quaderno (purtroppo lo svolgimento è stato fatto un poco di fretta), e come risultato ho un sistema di 2 congruenze:
x congruo 1 mod 3
x congruo 4 mod 5

Su quello non so cosa dirti... Io mi sono limitato a calcolare \[
13^{1234}\mod 105 = 64
\] e confermo che il risultato è corretto: l'ho anche controllato con questo tool online.

uhm...uffa questo esercizio mi sta facendo dannare.
Grazie.

$ 13^1234 mod 105$

Dato che $105=3*5*7$, calcoliamo separatamente $ 13^1234 mod 3$, $ 13^1234 mod 5$ e $ 13^1234 mod 7$
Si ha $13^1234 -=1^1234 = 1 (mod 3)$, $13^1234 -=...= 4 (mod 5)$ e $13^(1234)-= (-1)^1234= 1 (mod 7)$.

Ora dobbiamo risolvere ${(x-=1 (mod 3)),(x -= 4 (mod 5)),(x-= 1 (mod 7)):}$
Si può fare col teorema cinese del resto, o anche in altri modi.

Ad esempio, posto $y= x-1$, si ha che $y$ è multiplo di $21$ e $y-=3 (mod 5)$
Tra $0$ e $104$ i multipli di $21$ sono solo $0, 21, 42,63,84$. Solo uno di questi è congruo a $3$ modulo $5$, cioè $63$.

Dunque $x-= 64 mod (105)$

Grazie Gi8.
Domani riproverò a risolvere l'esercizio e ti/vi farò sapere.

Scusate il ritardo.
Ho provato a completare l'esercizio ma non sono riuscito.
Sono riuscito a calcolare solo 13^1234.
Non capisco come mai quando vado a calcolare la 2a congruenza e la 3a congruenza devo operare in maniere differenti rispetto al calcolo eseguito per la prima.
Più tardi se non riesco a venirne a capo vi vorrei postare l'esercizio su carta.

Fino ad ora sono riuscito a calcolare le prime 2 congruenze.
Vi posto i fogli con i calcoli:
Pagina1
Pagina2

Ho però nette difficoltà nel capire, studiando la soluzione vista in classe, come è stata calcolata l'ultima congruenza, cioè 13^1234 mod 7, perchè viene trovato che:
13 = -1 mod 7
Non capisco quel -1 da dove esca fuori.

Ragazzi, mi potreste aiutare a capire come si calcola l'ultima congruenza?
Io ho provato in questo modo, ma evidentemente sto sbagliando non tanto il ragionamento (i conti tornano), ma il procedimento, visto che mi vengono numeri più grandi di quelli che sono usciti a lezione.

Devo calcolare 13^1234 mod 7
MCD(13, 7) = -1
phi(7) = 6
13^phi(7) = -1 mod 7 che equivale a dire 13^6 = -1 mod 7
13^1234 = (13^6)^205 * 13^4
13^4 congruo 7 è il risultato, ma ovviamente quella potenza non ci deve stare

Il risultato "corretto" deve essere:
(-1)^1234 mod 7
x congruo 1 mod 7