Exercicis de teoria de nombres

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

El resultat.

$11^{-1} \equiv 11 \pmod{15}$

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

$5^{22} \equiv 1 \pmod{23}$

Pas 2 — reduir l'exponent mòdul $22$. Com que $39 = 1\cdot22 + 17$,

$5^{39} \equiv 5^{17} \pmod{23}$

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

$5^{39} \equiv 15 \pmod{23}$

L'error número u de tot el tema: reduir l'exponent mòdul $23$ en comptes de mòdul $22$. Són dos mòduls diferents que viuen a llocs diferents de la fórmula, i confondre'ls dona sempre resultats erronis.

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

$\gcd(368, 92) = 92$

Comprovació. $368/92 = 4$ i $92/92 = 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\cdot368 + v\cdot92 = 92$, i es troben recorrent les divisions en ordre invers.

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

El resultat.

$12^{-1} \equiv 10 \pmod{17}$

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

$3^{18} \equiv 1 \pmod{19}$

Pas 2 — reduir l'exponent mòdul $18$. Com que $29 = 1\cdot18 + 11$,

$3^{29} \equiv 3^{11} \pmod{19}$

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

$3^{29} \equiv 10 \pmod{19}$

L'error número u de tot el tema: reduir l'exponent mòdul $19$ en comptes de mòdul $18$. Són dos mòduls diferents que viuen a llocs diferents de la fórmula, i confondre'ls dona sempre resultats erronis.

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í: $231 = 165\cdot1 + 66$, i es continua amb $165$ i $66$ fins a arribar a residu zero.

$\gcd(231, 165) = 33$

Comprovació. $231/33 = 7$ i $165/33 = 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\cdot231 + v\cdot165 = 33$, i es troben recorrent les divisions en ordre invers.

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

El resultat.

$13^{-1} \equiv 7 \pmod{18}$

Verificació obligatòria: $13\cdot7 = 91 = 5\cdot18 + 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 $10$,

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

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

$10^{40} \equiv 10^{8} \pmod{17}$

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

$10^{40} \equiv 16 \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.

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í: $840 = 630\cdot1 + 210$, i es continua amb $630$ i $210$ fins a arribar a residu zero.

$\gcd(840, 630) = 210$

Comprovació. $840/210 = 4$ i $630/210 = 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\cdot840 + v\cdot630 = 210$, i es troben recorrent les divisions en ordre invers.

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

El resultat.

$14^{-1} \equiv 15 \pmod{19}$

Verificació obligatòria: $14\cdot15 = 210 = 11\cdot19 + 1$, o sigui que deixa residu $1$. Correcte.

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