Exercicis de teoria de nombres

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

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

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

$4^{50} \equiv 4^{2} \pmod{13}$

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

$4^{50} \equiv 3 \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(9,11) = 1$, o sigui que sí, i és única mòdul $9\cdot11 = 99$.

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

$2 + 9k \equiv 6 \pmod{11}$

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

Pas 3 — desfer la substitució.

$x \equiv 83 \pmod{99}$

Verificació. $83 = 9\cdot9 + 2$, o sigui $83\equiv2$ mòdul $9$; i $83 = 7\cdot11 + 6$, o sigui $83\equiv6$ mòdul $11$. 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í: $108 = 45\cdot2 + 18$, i es continua amb $45$ i $18$ fins a arribar a residu zero.

$\gcd(108, 45) = 9$

Comprovació. $108/9 = 12$ i $45/9 = 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\cdot108 + v\cdot45 = 9$, i es troben recorrent les divisions en ordre invers.

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

El resultat.

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

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

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

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

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

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

$6^{31} \equiv 6 \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,13) = 1$, o sigui que sí, i és única mòdul $6\cdot13 = 78$.

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

$5 + 6k \equiv 4 \pmod{13}$

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

Pas 3 — desfer la substitució.

$x \equiv 17 \pmod{78}$

Verificació. $17 = 2\cdot6 + 5$, o sigui $17\equiv5$ mòdul $6$; i $17 = 1\cdot13 + 4$, o sigui $17\equiv4$ mòdul $13$. 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í: $1000 = 625\cdot1 + 375$, i es continua amb $625$ i $375$ fins a arribar a residu zero.

$\gcd(1000, 625) = 125$

Comprovació. $1000/125 = 8$ i $625/125 = 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\cdot1000 + v\cdot625 = 125$, i es troben recorrent les divisions en ordre invers.

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

El resultat.

$10^{-1} \equiv 4 \pmod{13}$

Verificació obligatòria: $10\cdot4 = 40 = 3\cdot13 + 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 $23$ és primer i no divideix $2$,

$2^{22} \equiv 1 \pmod{23}$

Pas 2 — reduir l'exponent mòdul $22$. Com que $41 = 1\cdot22 + 19$,

$2^{41} \equiv 2^{19} \pmod{23}$

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

$2^{41} \equiv 3 \pmod{23}$

L'error número u de tot el tema: reduir l'exponent mòdul $23$ en comptes de mòdul $22$. 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í: $77 = 55\cdot1 + 22$, i es continua amb $55$ i $22$ fins a arribar a residu zero.

$\gcd(77, 55) = 11$

Comprovació. $77/11 = 7$ i $55/11 = 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\cdot77 + v\cdot55 = 11$, i es troben recorrent les divisions en ordre invers.