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

$\gcd(252, 105) = 21$

Comprovació. $252/21 = 12$ i $105/21 = 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\cdot252 + v\cdot105 = 21$, i es troben recorrent les divisions en ordre invers.

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

El resultat.

$9^{-1} \equiv 3 \pmod{13}$

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

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

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

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

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

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

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

$4 + 5k \equiv 5 \pmod{11}$

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

Pas 3 — desfer la substitució.

$x \equiv 49 \pmod{55}$

Verificació. $49 = 9\cdot5 + 4$, o sigui $49\equiv4$ mòdul $5$; 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.

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

$\gcd(144, 60) = 12$

Comprovació. $144/12 = 12$ i $60/12 = 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\cdot144 + v\cdot60 = 12$, i es troben recorrent les divisions en ordre invers.

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

El resultat.

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

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

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

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

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

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

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

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

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

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

Pas 3 — desfer la substitució.

$x \equiv 11 \pmod{36}$

Verificació. $11 = 2\cdot4 + 3$, o sigui $11\equiv3$ mòdul $4$; i $11 = 1\cdot9 + 2$, o sigui $11\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í: $1001 = 77\cdot13 + 0$, i es continua amb $77$ i $0$ fins a arribar a residu zero.

$\gcd(1001, 77) = 77$

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

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

El resultat.

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

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

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