Simulacre d'examen de teoria de nombres

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 $2$,

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

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

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

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

$2^{100} \equiv 2 \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.

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.

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.

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

El resultat.

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

Verificació obligatòria: $9\cdot5 = 45 = 2\cdot22 + 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 $3$,

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

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

$3^{55} \equiv 3^{7} \pmod{17}$

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

$3^{55} \equiv 11 \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.

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 $23$ és primer i no divideix $2$,

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

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

$2^{41} \equiv 2^{19} \pmod{23}$

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

$2^{41} \equiv 3 \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í: $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.

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.

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

$\gcd(84, 36) = 12$

Comprovació. $84/12 = 7$ i $36/12 = 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\cdot84 + v\cdot36 = 12$, i es troben recorrent les divisions en ordre invers.

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.