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

$\gcd(76, 38) = 38$

Comprovació. $76/38 = 2$ i $38/38 = 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\cdot76 + v\cdot38 = 38$, i es troben recorrent les divisions en ordre invers.

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

El resultat.

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

Verificació obligatòria: $6\cdot6 = 36 = 5\cdot7 + 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 $7$,

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

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

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

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

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

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

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

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

Pas 3 — desfer la substitució.

$x \equiv 33 \pmod{65}$

Verificació. $33 = 6\cdot5 + 3$, o sigui $33\equiv3$ mòdul $5$; i $33 = 2\cdot13 + 7$, o sigui $33\equiv7$ mòdul $13$. 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í: $225 = 135\cdot1 + 90$, i es continua amb $135$ i $90$ fins a arribar a residu zero.

$\gcd(225, 135) = 45$

Comprovació. $225/45 = 5$ i $135/45 = 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\cdot225 + v\cdot135 = 45$, i es troben recorrent les divisions en ordre invers.

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

El resultat.

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

Verificació obligatòria: $7\cdot4 = 28 = 3\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 $11$ és primer i no divideix $3$,

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

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

$3^{70} \equiv 3^{0} \pmod{11}$

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

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

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

$4 + 7k \equiv 9 \pmod{11}$

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

Pas 3 — desfer la substitució.

$x \equiv 53 \pmod{77}$

Verificació. $53 = 7\cdot7 + 4$, o sigui $53\equiv4$ mòdul $7$; i $53 = 4\cdot11 + 9$, o sigui $53\equiv9$ 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í: $396 = 132\cdot3 + 0$, i es continua amb $132$ i $0$ fins a arribar a residu zero.

$\gcd(396, 132) = 132$

Comprovació. $396/132 = 3$ i $132/132 = 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\cdot396 + v\cdot132 = 132$, i es troben recorrent les divisions en ordre invers.

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

El resultat.

$8^{-1} \equiv 7 \pmod{11}$

Verificació obligatòria: $8\cdot7 = 56 = 5\cdot11 + 1$, o sigui que deixa residu $1$. Correcte.

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