Exercicis de teoria de nombres

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

$\gcd(84, 36) = 12$

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

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

El resultat.

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

Verificació obligatòria: $4\cdot7 = 28 = 1\cdot27 + 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 $11$,

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

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

$11^{12} \equiv 11^{0} \pmod{7}$

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

$11^{12} \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(9,10) = 1$, o sigui que sí, i és única mòdul $9\cdot10 = 90$.

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

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

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

Pas 3 — desfer la substitució.

$x \equiv 31 \pmod{90}$

Verificació. $31 = 3\cdot9 + 4$, o sigui $31\equiv4$ mòdul $9$; i $31 = 3\cdot10 + 1$, o sigui $31\equiv1$ mòdul $10$. 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í: $154 = 66\cdot2 + 22$, i es continua amb $66$ i $22$ fins a arribar a residu zero.

$\gcd(154, 66) = 22$

Comprovació. $154/22 = 7$ i $66/22 = 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\cdot154 + v\cdot66 = 22$, i es troben recorrent les divisions en ordre invers.

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

El resultat.

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

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

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

Pas 2 — reduir l'exponent mòdul $16$. Com que $77 = 4\cdot16 + 13$,

$2^{77} \equiv 2^{13} \pmod{17}$

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

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

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

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

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

Pas 3 — desfer la substitució.

$x \equiv 17 \pmod{84}$

Verificació. $17 = 1\cdot12 + 5$, o sigui $17\equiv5$ mòdul $12$; 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í: $289 = 187\cdot1 + 102$, i es continua amb $187$ i $102$ fins a arribar a residu zero.

$\gcd(289, 187) = 17$

Comprovació. $289/17 = 17$ i $187/17 = 11$, 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\cdot289 + v\cdot187 = 17$, i es troben recorrent les divisions en ordre invers.

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

El resultat.

$3^{-1} \equiv 5 \pmod{7}$

Verificació obligatòria: $3\cdot5 = 15 = 2\cdot7 + 1$, o sigui que deixa residu $1$. Correcte.

Aquesta comprovació costa cinc segons i detecta qualsevol error de càlcul.