Exercicis de teoria de nombres

Pas 1 — Fermat. Com que $17$ és primer i no divideix $3$,

$3^{16} \equiv 1 \pmod{17}$

Pas 2 — reduir l'exponent mòdul $16$. Com que $55 = 3\cdot16 + 7$,

$3^{55} \equiv 3^{7} \pmod{17}$

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

$3^{55} \equiv 11 \pmod{17}$

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

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

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

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

Pas 3 — desfer la substitució.

$x \equiv 54 \pmod{65}$

Verificació. $54 = 4\cdot13 + 2$, o sigui $54\equiv2$ mòdul $13$; i $54 = 10\cdot5 + 4$, o sigui $54\equiv4$ 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.

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

$\gcd(432, 180) = 36$

Comprovació. $432/36 = 12$ i $180/36 = 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\cdot432 + v\cdot180 = 36$, i es troben recorrent les divisions en ordre invers.

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

El resultat.

$4^{-1} \equiv 3 \pmod{11}$

Verificació obligatòria: $4\cdot3 = 12 = 1\cdot11 + 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 $19$ és primer i no divideix $5$,

$5^{18} \equiv 1 \pmod{19}$

Pas 2 — reduir l'exponent mòdul $18$. Com que $44 = 2\cdot18 + 8$,

$5^{44} \equiv 5^{8} \pmod{19}$

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

$5^{44} \equiv 4 \pmod{19}$

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

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

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

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

Pas 3 — desfer la substitució.

$x \equiv 72 \pmod{77}$

Verificació. $72 = 6\cdot11 + 6$, o sigui $72\equiv6$ mòdul $11$; i $72 = 10\cdot7 + 2$, o sigui $72\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.

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

$\gcd(561, 357) = 51$

Comprovació. $561/51 = 11$ i $357/51 = 7$, 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\cdot561 + v\cdot357 = 51$, i es troben recorrent les divisions en ordre invers.

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

El resultat.

$5^{-1} \equiv 8 \pmod{13}$

Verificació obligatòria: $5\cdot8 = 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 $19$ és primer i no divideix $2$,

$2^{18} \equiv 1 \pmod{19}$

Pas 2 — reduir l'exponent mòdul $18$. Com que $200 = 11\cdot18 + 2$,

$2^{200} \equiv 2^{2} \pmod{19}$

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

$2^{200} \equiv 4 \pmod{19}$

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

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

$1 + 8k \equiv 5 \pmod{11}$

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

Pas 3 — desfer la substitució.

$x \equiv 49 \pmod{88}$

Verificació. $49 = 6\cdot8 + 1$, o sigui $49\equiv1$ mòdul $8$; i $49 = 4\cdot11 + 5$, o sigui $49\equiv5$ 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.