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

$\gcd(48, 18) = 6$

Comprovació. $48/6 = 8$ i $18/6 = 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\cdot48 + v\cdot18 = 6$, i es troben recorrent les divisions en ordre invers.

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

El resultat.

$7^{-1} \equiv 7 \pmod{12}$

Verificació obligatòria: $7\cdot7 = 49 = 4\cdot12 + 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 $3$,

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

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

$3^{100} \equiv 3^{4} \pmod{7}$

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

$3^{100} \equiv 4 \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(3,5) = 1$, o sigui que sí, i és única mòdul $3\cdot5 = 15$.

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

$2 + 3k \equiv 3 \pmod{5}$

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

Pas 3 — desfer la substitució.

$x \equiv 8 \pmod{15}$

Verificació. $8 = 2\cdot3 + 2$, o sigui $8\equiv2$ mòdul $3$; i $8 = 1\cdot5 + 3$, o sigui $8\equiv3$ 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í: $100 = 75\cdot1 + 25$, i es continua amb $75$ i $25$ fins a arribar a residu zero.

$\gcd(100, 75) = 25$

Comprovació. $100/25 = 4$ i $75/25 = 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\cdot100 + v\cdot75 = 25$, i es troben recorrent les divisions en ordre invers.

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

El resultat.

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

Verificació obligatòria: $3\cdot2 = 6 = 1\cdot5 + 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 $2$,

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

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

$2^{50} \equiv 2^{0} \pmod{11}$

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

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

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

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

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

Pas 3 — desfer la substitució.

$x \equiv 17 \pmod{20}$

Verificació. $17 = 4\cdot4 + 1$, o sigui $17\equiv1$ mòdul $4$; i $17 = 3\cdot5 + 2$, o sigui $17\equiv2$ 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í: $270 = 192\cdot1 + 78$, i es continua amb $192$ i $78$ fins a arribar a residu zero.

$\gcd(270, 192) = 6$

Comprovació. $270/6 = 45$ i $192/6 = 32$, 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\cdot270 + v\cdot192 = 6$, i es troben recorrent les divisions en ordre invers.

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

El resultat.

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

Verificació obligatòria: $5\cdot9 = 45 = 4\cdot11 + 1$, o sigui que deixa residu $1$. Correcte.

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