Exercicis de teoria de nombres

Pas 1 — Fermat. Com que $7$ és primer i no divideix $10$,

$10^{6} \equiv 1 \pmod{7}$

Pas 2 — reduir l'exponent mòdul $6$. Com que $25 = 4\cdot6 + 1$,

$10^{25} \equiv 10^{1} \pmod{7}$

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

$10^{25} \equiv 3 \pmod{7}$

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

Pas 0 — hi ha solució? $\gcd(5,9) = 1$, o sigui que sí, i és única mòdul $5\cdot9 = 45$.

Pas 1 — substitució. De la primera congruència, $x = 1 + 5k$. Fiquem-ho a la segona:

$1 + 5k \equiv 4 \pmod{9}$

Pas 2 — aïllar $k$ multiplicant per l'invers de $5$ mòdul $9$.

Pas 3 — desfer la substitució.

$x \equiv 31 \pmod{45}$

Verificació. $31 = 6\cdot5 + 1$, o sigui $31\equiv1$ mòdul $5$; i $31 = 3\cdot9 + 4$, o sigui $31\equiv4$ mòdul $9$. Les dues condicions es compleixen.

Amb pocs mòduls, aquest mètode de substitució és més ràpid que la fórmula general.

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í: $65 = 26\cdot2 + 13$, i es continua amb $26$ i $13$ fins a arribar a residu zero.

$\gcd(65, 26) = 13$

Comprovació. $65/13 = 5$ i $26/13 = 2$, 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\cdot65 + v\cdot26 = 13$, i es troben recorrent les divisions en ordre invers.

Existeix? Sí: $\gcd(13,20) = 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 $13u + 20v = 1$. Reduint mòdul $20$, el segon terme desapareix i queda $13u \equiv 1$.

El resultat.

$13^{-1} \equiv 17 \pmod{20}$

Verificació obligatòria: $13\cdot17 = 221 = 11\cdot20 + 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 $8$,

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

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

$8^{20} \equiv 8^{0} \pmod{11}$

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

$8^{20} \equiv 1 \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.

Pas 0 — hi ha solució? $\gcd(7,8) = 1$, o sigui que sí, i és única mòdul $7\cdot8 = 56$.

Pas 1 — substitució. De la primera congruència, $x = 2 + 7k$. Fiquem-ho a la segona:

$2 + 7k \equiv 5 \pmod{8}$

Pas 2 — aïllar $k$ multiplicant per l'invers de $7$ mòdul $8$.

Pas 3 — desfer la substitució.

$x \equiv 37 \pmod{56}$

Verificació. $37 = 5\cdot7 + 2$, o sigui $37\equiv2$ mòdul $7$; i $37 = 4\cdot8 + 5$, o sigui $37\equiv5$ mòdul $8$. Les dues condicions es compleixen.

Amb pocs mòduls, aquest mètode de substitució és més ràpid que la fórmula general.

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í: $345 = 207\cdot1 + 138$, i es continua amb $207$ i $138$ fins a arribar a residu zero.

$\gcd(345, 207) = 69$

Comprovació. $345/69 = 5$ i $207/69 = 3$, 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\cdot345 + v\cdot207 = 69$, i es troben recorrent les divisions en ordre invers.

Existeix? Sí: $\gcd(9,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 $9u + 22v = 1$. Reduint mòdul $22$, el segon terme desapareix i queda $9u \equiv 1$.

El resultat.

$9^{-1} \equiv 5 \pmod{22}$

Verificació obligatòria: $9\cdot5 = 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 $13$ és primer i no divideix $9$,

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

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

$9^{15} \equiv 9^{3} \pmod{13}$

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

$9^{15} \equiv 1 \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.

Pas 0 — hi ha solució? $\gcd(11,5) = 1$, o sigui que sí, i és única mòdul $11\cdot5 = 55$.

Pas 1 — substitució. De la primera congruència, $x = 3 + 11k$. Fiquem-ho a la segona:

$3 + 11k \equiv 2 \pmod{5}$

Pas 2 — aïllar $k$ multiplicant per l'invers de $11$ mòdul $5$.

Pas 3 — desfer la substitució.

$x \equiv 47 \pmod{55}$

Verificació. $47 = 4\cdot11 + 3$, o sigui $47\equiv3$ mòdul $11$; i $47 = 9\cdot5 + 2$, o sigui $47\equiv2$ mòdul $5$. Les dues condicions es compleixen.

Amb pocs mòduls, aquest mètode de substitució és més ràpid que la fórmula general.