Ejercicios resueltos de función de Euler y elementos invertibles

$36 = 4 \times 9 = 2^2 \times 3^2$

$\phi(36) = 36 \times \prod_{p|36} \left(1 - \frac{1}{p}\right)$

Los primos que dividen a 36 son 2 y 3:

$\phi(36) = 36 \times \left(1 - \frac{1}{2}\right) \times \left(1 - \frac{1}{3}\right)$

$= 36 \times \frac{1}{2} \times \frac{2}{3} = 36 \times \frac{2}{6} = 36 \times \frac{1}{3} = 12$

Para $n = p_1^{a_1} \times p_2^{a_2} \times \cdots$:

$\phi(n) = n \times \prod_{i} \left(1 - \frac{1}{p_i}\right) = \prod_{i} p_i^{a_i-1}(p_i - 1)$

$\phi(36) = \phi(2^2 \times 3^2) = \phi(2^2) \times \phi(3^2)$

$= 2^{2-1}(2-1) \times 3^{2-1}(3-1) = 2^1 \times 1 \times 3^1 \times 2 = 2 \times 6 = 12$ $\checkmark$

Un elemento $a \in \mathbb{Z}_{36}$ es invertible si y solo si $\gcd(a, 36) = 1$.

Debemos encontrar todos los $a \in \{0, 1, 2, \ldots, 35\}$ tales que $\gcd(a, 36) = 1$.

Los elementos NO invertibles son aquellos que comparten factores con $36 = 2^2 \times 3^2$:

Múltiplos de 2: $\{0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34\}$

Múltiplos de 3: $\{0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33\}$

Elementos con $\gcd(a, 36) > 1$: Unión de múltiplos de 2 y múltiplos de 3

$\{0, 2, 3, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 26, 27, 28, 30, 32, 33, 34\}$

$\mathbb{Z}_{36} \setminus \{\text{no invertibles}\} = \{1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35\}$

Contamos: $|\{1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35\}| = 12 = \phi(36)$ $\checkmark$

Para $a = 5$: $\gcd(5, 36) = 1$ $\checkmark$

Para $a = 7$: $\gcd(7, 36) = 1$ $\checkmark$

Para $a = 25$: $\gcd(25, 36) = \gcd(25, 36) = 1$ $\checkmark$ (ya que $25 = 5^2$ y $36 = 2^2 \times 3^2$)

Respuesta:

• $\phi(36) = 12$
• Elementos invertibles: $\{1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35\}$

$15 = 3 \times 5$

$\phi(15) = 15 \times \left(1 - \frac{1}{3}\right) \times \left(1 - \frac{1}{5}\right)$

$= 15 \times \frac{2}{3} \times \frac{4}{5} = 15 \times \frac{8}{15} = 8$

Como 7 es primo y $7 \nmid 15$, tenemos $\gcd(7, 15) = 1$ $\checkmark$

Por el Teorema de Euler: $7^{\phi(15)} \equiv 7^8 \equiv 1 \pmod{15}$

$7^1 \equiv 7 \pmod{15}$

$7^2 \equiv 49 \equiv 4 \pmod{15}$ (ya que $49 = 3 \times 15 + 4$)

$7^4 \equiv (7^2)^2 \equiv 4^2 \equiv 16 \equiv 1 \pmod{15}$ (ya que $16 = 1 \times 15 + 1$)

Como $7^4 \equiv 1 \pmod{15}$:

$7^8 = (7^4)^2 \equiv 1^2 \equiv 1 \pmod{15}$ $\checkmark$

Como $7^4 \equiv 1 \pmod{15}$, el orden de 7 módulo 15 divide a 4.

$100 = 4 \times 25 + 0$

Por tanto:

$7^{100} = (7^4)^{25} \equiv 1^{25} \equiv 1 \pmod{15}$

$100 = 8 \times 12 + 4$

$7^{100} = 7^{8 \times 12 + 4} = (7^8)^{12} \times 7^4 \equiv 1^{12} \times 7^4 \equiv 7^4 \equiv 1 \pmod{15}$

Hemos descubierto que el orden de 7 módulo 15 es 4, que es menor que $\phi(15) = 8$. Esto es normal, ya que el Teorema de Euler garantiza que $a^{\phi(n)} \equiv 1 \pmod{n}$, pero el orden puede ser un divisor propio de $\phi(n)$.

Respuesta:

• $7^{\phi(15)} = 7^8 \equiv 1 \pmod{15}$ (verificando el Teorema de Euler)
• $7^{100} \equiv 1 \pmod{15}$
• Además, encontramos que $\text{ord}_{15}(7) = 4$

Teorema de Wilson: Si $p$ es primo, entonces $(p-1)! \equiv -1 \pmod{p}$.

Casos base:

• Para $p = 2$: $(2-1)! = 1! = 1 \equiv -1 \equiv 1 \pmod{2}$ $\checkmark$
• Para $p = 3$: $(3-1)! = 2! = 2 \equiv -1 \pmod{3}$ $\checkmark$

Caso general ($p \geq 5$):

En $\mathbb{Z}_p$, cada elemento no nulo $a \in \{1, 2, \ldots, p-1\}$ tiene un inverso único $a^{-1}$ tal que $a \cdot a^{-1} \equiv 1 \pmod{p}$.

$a$ es su propio inverso si $a^2 \equiv 1 \pmod{p}$, es decir, $(a-1)(a+1) \equiv 0 \pmod{p}$.

Como $p$ es primo, esto ocurre si y solo si $p | (a-1)$ o $p | (a+1)$.

Para $1 \leq a \leq p-1$:

• $p | (a-1) \Rightarrow a = 1$
• $p | (a+1) \Rightarrow a = p-1$

Por tanto, solo 1 y $p-1$ son sus propios inversos módulo $p$.

Los elementos $\{2, 3, \ldots, p-2\}$ se pueden emparejar en pares $(a, a^{-1})$ donde $a \neq a^{-1}$.

Cada par satisface $a \cdot a^{-1} \equiv 1 \pmod{p}$.

$(p-1)! = 1 \times 2 \times 3 \times \cdots \times (p-2) \times (p-1)$

Los elementos $\{2, 3, \ldots, p-2\}$ se cancelan en pares que dan producto $\equiv 1 \pmod{p}$:

$(p-1)! \equiv 1 \times (p-1) \equiv p-1 \equiv -1 \pmod{p}$

$(7-1)! = 6! = 1 \times 2 \times 3 \times 4 \times 5 \times 6$

Calculamos paso a paso:

$1 \times 2 = 2$

$2 \times 3 = 6$

$6 \times 4 = 24 \equiv 3 \pmod{7}$ (ya que $24 = 3 \times 7 + 3$)

$3 \times 5 = 15 \equiv 1 \pmod{7}$ (ya que $15 = 2 \times 7 + 1$)

$1 \times 6 = 6 \equiv -1 \pmod{7}$

Por tanto: $6! \equiv -1 \pmod{7}$ $\checkmark$

En $\mathbb{Z}_7$:

• $1^{-1} = 1$ (inverso de sí mismo)
• $6^{-1} = 6$ (ya que $6 \times 6 = 36 \equiv 1 \pmod{7}$) (inverso de sí mismo)
• $2^{-1} = 4$ (ya que $2 \times 4 = 8 \equiv 1 \pmod{7}$)
• $3^{-1} = 5$ (ya que $3 \times 5 = 15 \equiv 1 \pmod{7}$)

Los pares son: $(2{,}4)$ y $(3{,}5)$

$6! = 1 \times (2 \times 4) \times (3 \times 5) \times 6 = 1 \times 1 \times 1 \times 6 = 6 \equiv -1 \pmod{7}$ $\checkmark$

Respuesta: El Teorema de Wilson queda demostrado y verificado para $p = 7$.

Como 13 es primo, $\mathbb{Z}_{13}^* = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12\}$

$|\mathbb{Z}_{13}^*| = \phi(13) = 12$

El orden de un elemento $a$ es el menor entero positivo $k$ tal que $a^k \equiv 1 \pmod{13}$.

Elemento 1:

$1^1 = 1 \equiv 1 \pmod{13}$

$\text{ord}_{13}(1) = 1$

Elemento 2:

$2^1 = 2$, $2^2 = 4$, $2^3 = 8$, $2^4 = 16 \equiv 3 \pmod{13}$

$2^5 = 2 \times 3 = 6$, $2^6 = 2 \times 6 = 12 \equiv -1 \pmod{13}$

$2^{12} = (2^6)^2 \equiv (-1)^2 = 1 \pmod{13}$

Verificamos: $2^{12} = 4096 = 315 \times 13 + 1 \equiv 1 \pmod{13}$

$\text{ord}_{13}(2) = 12$

Elemento 3:

$3^1 = 3$, $3^2 = 9$, $3^3 = 27 \equiv 1 \pmod{13}$

$\text{ord}_{13}(3) = 3$

Elemento 4:

$4 = 2^2$, por tanto $4^k = (2^2)^k = 2^{2k}$

$\text{ord}_{13}(4) = \frac{\text{ord}_{13}(2)}{\gcd(\text{ord}_{13}(2), 2)} = \frac{12}{\gcd(12, 2)} = \frac{12}{2} = 6$

Elemento 5:

$5^1 = 5$, $5^2 = 25 \equiv 12 \equiv -1 \pmod{13}$

$5^4 = (5^2)^2 \equiv (-1)^2 = 1 \pmod{13}$

$\text{ord}_{13}(5) = 4$

Elemento 6:

$6^1 = 6$, $6^2 = 36 \equiv 10 \pmod{13}$, $6^3 = 6 \times 10 = 60 \equiv 8 \pmod{13}$

$6^4 = 6 \times 8 = 48 \equiv 9 \pmod{13}$, $6^5 = 6 \times 9 = 54 \equiv 2 \pmod{13}$

$6^6 = 6 \times 2 = 12 \equiv -1 \pmod{13}$

$6^{12} = (6^6)^2 \equiv 1 \pmod{13}$

$\text{ord}_{13}(6) = 12$

Elemento 7:

$7^1 = 7$, $7^2 = 49 \equiv 10 \pmod{13}$, $7^3 = 7 \times 10 = 70 \equiv 5 \pmod{13}$

$7^4 = 7 \times 5 = 35 \equiv 9 \pmod{13}$, $7^5 = 7 \times 9 = 63 \equiv 11 \pmod{13}$

$7^6 = 7 \times 11 = 77 \equiv 12 \equiv -1 \pmod{13}$

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

$\text{ord}_{13}(7) = 12$

Usando propiedades y cálculos similares:

$\text{ord}_{13}(8) = 4$ (ya que $8 = 2^3$ y $8^4 \equiv 1 \pmod{13}$)

$\text{ord}_{13}(9) = 3$ (ya que $9 = 3^2$ y $9^3 \equiv 1 \pmod{13}$)

$\text{ord}_{13}(10) = 6$

$\text{ord}_{13}(11) = 12$

$\text{ord}_{13}(12) = 2$ (ya que $12 \equiv -1$ y $(-1)^2 = 1$)

Los generadores de $\mathbb{Z}_{13}^*$ son los elementos de orden máximo, es decir, orden 12.

Los generadores son: $\{2, 6, 7, 11\}$

• La cantidad de generadores es $\phi(\phi(13)) = \phi(12) = 4$ $\checkmark$
• Todos los órdenes dividen a $|\mathbb{Z}_{13}^*| = 12$ $\checkmark$
• Los divisores de 12 son: $\{1, 2, 3, 4, 6, 12\}$, y encontramos elementos de cada uno de estos órdenes $\checkmark$

Respuesta:

• Órdenes: Como se muestra en la tabla
• Generadores de $\mathbb{Z}_{13}^*$: $\{2, 6, 7, 11\}$