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í: $720 = 168\cdot4 + 48$, i es continua amb $168$ i $48$ fins a arribar a residu zero.

$\gcd(720, 168) = 24$

Comprovació. $720/24 = 30$ i $168/24 = 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\cdot720 + v\cdot168 = 24$, i es troben recorrent les divisions en ordre invers.

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

El resultat.

$6^{-1} \equiv 21 \pmod{25}$

Verificació obligatòria: $6\cdot21 = 126 = 5\cdot25 + 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 $3$,

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

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

$3^{81} \equiv 3^{9} \pmod{13}$

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

$3^{81} \equiv 1 \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(7,8) = 1$, o sigui que sí, i és única mòdul $7\cdot8 = 56$.

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

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

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

Pas 3 — desfer la substitució.

$x \equiv 41 \pmod{56}$

Verificació. $41 = 5\cdot7 + 6$, o sigui $41\equiv6$ mòdul $7$; i $41 = 5\cdot8 + 1$, o sigui $41\equiv1$ mòdul $8$. 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í: $999 = 666\cdot1 + 333$, i es continua amb $666$ i $333$ fins a arribar a residu zero.

$\gcd(999, 666) = 333$

Comprovació. $999/333 = 3$ i $666/333 = 2$, 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\cdot999 + v\cdot666 = 333$, i es troben recorrent les divisions en ordre invers.

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

El resultat.

$8^{-1} \equiv 15 \pmod{17}$

Verificació obligatòria: $8\cdot15 = 120 = 7\cdot17 + 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 $5$ és primer i no divideix $2$,

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

Pas 2 — reduir l'exponent mòdul $4$. Com que $33 = 8\cdot4 + 1$,

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

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

$2^{33} \equiv 2 \pmod{5}$

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

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

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

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

Pas 3 — desfer la substitució.

$x \equiv 33 \pmod{70}$

Verificació. $33 = 3\cdot10 + 3$, o sigui $33\equiv3$ mòdul $10$; i $33 = 4\cdot7 + 5$, o sigui $33\equiv5$ 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í: $128 = 96\cdot1 + 32$, i es continua amb $96$ i $32$ fins a arribar a residu zero.

$\gcd(128, 96) = 32$

Comprovació. $128/32 = 4$ i $96/32 = 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\cdot128 + v\cdot96 = 32$, i es troben recorrent les divisions en ordre invers.

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

El resultat.

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

Verificació obligatòria: $5\cdot13 = 65 = 4\cdot16 + 1$, o sigui que deixa residu $1$. Correcte.

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