Exercicis de teoria de nombres

Pas 1 — Fermat. Com que $13$ és primer i no divideix $8$,

$8^{12} \equiv 1 \pmod{13}$

Pas 2 — reduir l'exponent mòdul $12$. Com que $27 = 2\cdot12 + 3$,

$8^{27} \equiv 8^{3} \pmod{13}$

Pas 3 — calcular la potència petita i reduir.

$8^{27} \equiv 5 \pmod{13}$

L'error número u de tot el tema: reduir l'exponent mòdul $13$ en comptes de mòdul $12$. Són dos mòduls diferents que viuen a llocs diferents de la fórmula, i confondre'ls dona sempre resultats erronis.

L'algorisme d'Euclides. Es basa en què $\gcd(a,b) = \gcd(b, r)$, on $r$ és el residu de dividir $a$ entre $b$. Com que els residus decreixen estrictament, el procés acaba.

Aquí: $512 = 320\cdot1 + 192$, i es continua amb $320$ i $192$ fins a arribar a residu zero.

$\gcd(512, 320) = 64$

Comprovació. $512/64 = 8$ i $320/64 = 5$, i aquests dos quocients han de ser coprimers. Si tenen algun factor comú, no havies arribat al màxim.

De pas: per Bézout, existeixen enters $u$ i $v$ amb $u\cdot512 + v\cdot320 = 64$, i es troben recorrent les divisions en ordre invers.

Existeix? Sí: $\gcd(15,22) = 1$, i aquesta és exactament la condició necessària i suficient perquè hi hagi invers.

Per què. Per Bézout hi ha enters $u$ i $v$ amb $15u + 22v = 1$. Reduint mòdul $22$, el segon terme desapareix i queda $15u \equiv 1$.

El resultat.

$15^{-1} \equiv 3 \pmod{22}$

Verificació obligatòria: $15\cdot3 = 45 = 2\cdot22 + 1$, o sigui que deixa residu $1$. Correcte.

Aquesta comprovació costa cinc segons i detecta qualsevol error de càlcul.

Pas 1 — Fermat. Com que $11$ és primer i no divideix $9$,

$9^{10} \equiv 1 \pmod{11}$

Pas 2 — reduir l'exponent mòdul $10$. Com que $36 = 3\cdot10 + 6$,

$9^{36} \equiv 9^{6} \pmod{11}$

Pas 3 — calcular la potència petita i reduir.

$9^{36} \equiv 9 \pmod{11}$

L'error número u de tot el tema: reduir l'exponent mòdul $11$ en comptes de mòdul $10$. Són dos mòduls diferents que viuen a llocs diferents de la fórmula, i confondre'ls dona sempre resultats erronis.