Exercicis de teoria de nombres

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

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

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

$5^{60} \equiv 5^{0} \pmod{13}$

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

$5^{60} \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(7,9) = 1$, o sigui que sí, i és única mòdul $7\cdot9 = 63$.

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

$3 + 7k \equiv 4 \pmod{9}$

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

Pas 3 — desfer la substitució.

$x \equiv 31 \pmod{63}$

Verificació. $31 = 4\cdot7 + 3$, o sigui $31\equiv3$ mòdul $7$; 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í: $1071 = 462\cdot2 + 147$, i es continua amb $462$ i $147$ fins a arribar a residu zero.

$\gcd(1071, 462) = 21$

Comprovació. $1071/21 = 51$ i $462/21 = 22$, 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\cdot1071 + v\cdot462 = 21$, i es troben recorrent les divisions en ordre invers.

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

El resultat.

$4^{-1} \equiv 7 \pmod{9}$

Verificació obligatòria: $4\cdot7 = 28 = 3\cdot9 + 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 $7$ és primer i no divideix $2$,

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

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

$2^{100} \equiv 2^{4} \pmod{7}$

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

$2^{100} \equiv 2 \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,7) = 1$, o sigui que sí, i és única mòdul $5\cdot7 = 35$.

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

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

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

Pas 3 — desfer la substitució.

$x \equiv 17 \pmod{35}$

Verificació. $17 = 3\cdot5 + 2$, o sigui $17\equiv2$ mòdul $5$; i $17 = 2\cdot7 + 3$, o sigui $17\equiv3$ mòdul $7$. 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í: $91 = 35\cdot2 + 21$, i es continua amb $35$ i $21$ fins a arribar a residu zero.

$\gcd(91, 35) = 7$

Comprovació. $91/7 = 13$ i $35/7 = 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\cdot91 + v\cdot35 = 7$, i es troben recorrent les divisions en ordre invers.

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

El resultat.

$2^{-1} \equiv 4 \pmod{7}$

Verificació obligatòria: $2\cdot4 = 8 = 1\cdot7 + 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 $5$ és primer i no divideix $3$,

$3^{4} \equiv 1 \pmod{5}$

Pas 2 — reduir l'exponent mòdul $4$. Com que $45 = 11\cdot4 + 1$,

$3^{45} \equiv 3^{1} \pmod{5}$

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

$3^{45} \equiv 3 \pmod{5}$

L'error número u de tot el tema: reduir l'exponent mòdul $5$ en comptes de mòdul $4$. 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(3,7) = 1$, o sigui que sí, i és única mòdul $3\cdot7 = 21$.

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

$1 + 3k \equiv 2 \pmod{7}$

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

Pas 3 — desfer la substitució.

$x \equiv 16 \pmod{21}$

Verificació. $16 = 5\cdot3 + 1$, o sigui $16\equiv1$ mòdul $3$; i $16 = 2\cdot7 + 2$, o sigui $16\equiv2$ mòdul $7$. Les dues condicions es compleixen.

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