Exercicis de teoria de nombres

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

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

Pas 2 — reduir l'exponent mòdul $6$. Com que $33 = 5\cdot6 + 3$,

$4^{33} \equiv 4^{3} \pmod{7}$

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

$4^{33} \equiv 1 \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(6,7) = 1$, o sigui que sí, i és única mòdul $6\cdot7 = 42$.

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

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

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

Pas 3 — desfer la substitució.

$x \equiv 31 \pmod{42}$

Verificació. $31 = 5\cdot6 + 1$, o sigui $31\equiv1$ mòdul $6$; i $31 = 4\cdot7 + 3$, o sigui $31\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í: $315 = 180\cdot1 + 135$, i es continua amb $180$ i $135$ fins a arribar a residu zero.

$\gcd(315, 180) = 45$

Comprovació. $315/45 = 7$ i $180/45 = 4$, 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\cdot315 + v\cdot180 = 45$, i es troben recorrent les divisions en ordre invers.

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

El resultat.

$7^{-1} \equiv 13 \pmod{15}$

Verificació obligatòria: $7\cdot13 = 91 = 6\cdot15 + 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 $3$ és primer i no divideix $5$,

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

Pas 2 — reduir l'exponent mòdul $2$. Com que $22 = 11\cdot2 + 0$,

$5^{22} \equiv 5^{0} \pmod{3}$

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

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

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

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

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

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

Pas 3 — desfer la substitució.

$x \equiv 29 \pmod{72}$

Verificació. $29 = 3\cdot8 + 5$, o sigui $29\equiv5$ mòdul $8$; i $29 = 3\cdot9 + 2$, o sigui $29\equiv2$ 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í: $56 = 42\cdot1 + 14$, i es continua amb $42$ i $14$ fins a arribar a residu zero.

$\gcd(56, 42) = 14$

Comprovació. $56/14 = 4$ i $42/14 = 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\cdot56 + v\cdot42 = 14$, i es troben recorrent les divisions en ordre invers.

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

El resultat.

$11^{-1} \equiv 9 \pmod{14}$

Verificació obligatòria: $11\cdot9 = 99 = 7\cdot14 + 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 $6$,

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

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

$6^{40} \equiv 6^{0} \pmod{11}$

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

$6^{40} \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(11,4) = 1$, o sigui que sí, i és única mòdul $11\cdot4 = 44$.

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

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

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

Pas 3 — desfer la substitució.

$x \equiv 35 \pmod{44}$

Verificació. $35 = 3\cdot11 + 2$, o sigui $35\equiv2$ mòdul $11$; i $35 = 8\cdot4 + 3$, o sigui $35\equiv3$ mòdul $4$. Les dues condicions es compleixen.

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