Ejercicios resueltos de congruencias lineales

$\gcd(9, 15) = 3$

Para que exista solución, debe cumplirse que $\gcd(9, 15) | 6$.

Como $3 | 6$, la ecuación tiene solución.

Dividiendo toda la congruencia por $\gcd(9, 15) = 3$:

$\frac{9x \equiv 6 \pmod{15}}{3} \Rightarrow 3x \equiv 2 \pmod{5}$

Necesitamos encontrar $3^{-1} \pmod{5}$:

$3 \times 2 = 6 \equiv 1 \pmod{5}$

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

$x \equiv 2 \times 2 \equiv 4 \pmod{5}$

Como la congruencia original tenía $\gcd(9, 15) = 3$ soluciones distintas módulo 15, estas son:

• $x \equiv 4 \pmod{15}$
• $x \equiv 4 + 5 \equiv 9 \pmod{15}$
• $x \equiv 4 + 10 \equiv 14 \pmod{15}$

Para $x = 4$: $9 \times 4 = 36 \equiv 6 \pmod{15}$ $\checkmark$

Para $x = 9$: $9 \times 9 = 81 \equiv 6 \pmod{15}$ (ya que $81 = 5 \times 15 + 6$) $\checkmark$

Para $x = 14$: $9 \times 14 = 126 \equiv 6 \pmod{15}$ (ya que $126 = 8 \times 15 + 6$) $\checkmark$

Respuesta: $x \equiv 4, 9, 14 \pmod{15}$

$3x \equiv 2 \pmod{5}$

Encontramos $3^{-1} \pmod{5}$:

$3 \times 2 = 6 \equiv 1 \pmod{5}$

Por tanto: $x \equiv 2 \times 2 \equiv 4 \pmod{5}$

$2x \equiv 3 \pmod{7}$

Encontramos $2^{-1} \pmod{7}$:

$2 \times 4 = 8 \equiv 1 \pmod{7}$

Por tanto: $x \equiv 3 \times 4 \equiv 12 \equiv 5 \pmod{7}$

Tenemos el sistema:

$$\begin{cases} x \equiv 4 \pmod{5} \\ x \equiv 5 \pmod{7} \end{cases}$$

Como $\gcd(5, 7) = 1$, existe solución única módulo $5 \times 7 = 35$.

De la primera congruencia: $x = 5k + 4$ para algún $k \in \mathbb{Z}$

Sustituyendo en la segunda:

$5k + 4 \equiv 5 \pmod{7}$

$5k \equiv 1 \pmod{7}$

Necesitamos $5^{-1} \pmod{7}$:

$5 \times 3 = 15 \equiv 1 \pmod{7}$

Por tanto: $k \equiv 1 \times 3 \equiv 3 \pmod{7}$

$k = 7j + 3$ para algún $j \in \mathbb{Z}$

$x = 5k + 4 = 5(7j + 3) + 4 = 35j + 15 + 4 = 35j + 19$

$x \equiv 19 \pmod{35}$

$19 = 3 \times 5 + 4 \Rightarrow 19 \equiv 4 \pmod{5}$ $\checkmark$

$19 = 2 \times 7 + 5 \Rightarrow 19 \equiv 5 \pmod{7}$ $\checkmark$

Verificando las congruencias originales:

$3 \times 19 = 57 \equiv 2 \pmod{5}$ (ya que $57 = 11 \times 5 + 2$) $\checkmark$

$2 \times 19 = 38 \equiv 3 \pmod{7}$ (ya que $38 = 5 \times 7 + 3$) $\checkmark$

$\gcd(12, 20) = 4$

Para que exista solución, debe cumplirse que $\gcd(12, 20) | 8$.

Como $4 | 8$, la congruencia tiene solución.

$\frac{12x \equiv 8 \pmod{20}}{4} \Rightarrow 3x \equiv 2 \pmod{5}$

Necesitamos encontrar $3^{-1} \pmod{5}$:

$3 \times 2 = 6 \equiv 1 \pmod{5}$

Por tanto: $x \equiv 2 \times 2 \equiv 4 \pmod{5}$

Como $\gcd(12, 20) = 4$, existen exactamente 4 soluciones distintas módulo 20.

Las clases de equivalencia tienen la forma $x \equiv 4 + 5k \pmod{20}$ para $k = 0, 1, 2, 3$:

• $k = 0$: $x \equiv 4 \pmod{20}$
• $k = 1$: $x \equiv 4 + 5 \equiv 9 \pmod{20}$
• $k = 2$: $x \equiv 4 + 10 \equiv 14 \pmod{20}$
• $k = 3$: $x \equiv 4 + 15 \equiv 19 \pmod{20}$

Para $x = 4$: $12 \times 4 = 48 \equiv 8 \pmod{20}$ (ya que $48 = 2 \times 20 + 8$) $\checkmark$

Para $x = 9$: $12 \times 9 = 108 \equiv 8 \pmod{20}$ (ya que $108 = 5 \times 20 + 8$) $\checkmark$

Para $x = 14$: $12 \times 14 = 168 \equiv 8 \pmod{20}$ (ya que $168 = 8 \times 20 + 8$) $\checkmark$

Para $x = 19$: $12 \times 19 = 228 \equiv 8 \pmod{20}$ (ya que $228 = 11 \times 20 + 8$) $\checkmark$

Las soluciones se pueden expresar como:

$x \equiv 4 \pmod{5}$

O equivalentemente: $x \in \{4, 9, 14, 19\} + 20\mathbb{Z}$

Respuesta: $x \equiv 4, 9, 14, 19 \pmod{20}$ o más concisamente $x \equiv 4 \pmod{5}$

La congruencia $ax \equiv 1 \pmod{15}$ tiene solución si y solo si $\gcd(a, 15) = 1$.

$15 = 3 \times 5$

Los valores de $a$ coprimos con 15 son aquellos que no son múltiplos de 3 ni de 5:

$a \in \{1, 2, 4, 7, 8, 11, 13, 14\}$ (considerando $0 \leq a < 15$)

Para a = 1:

$1 \times x \equiv 1 \pmod{15} \Rightarrow x \equiv 1 \pmod{15}$

Para a = 2:

Necesitamos $2^{-1} \pmod{15}$:

$2 \times 8 = 16 \equiv 1 \pmod{15}$

Por tanto: $x \equiv 8 \pmod{15}$

Para a = 4:

$4 \times 4 = 16 \equiv 1 \pmod{15}$

Por tanto: $x \equiv 4 \pmod{15}$

Para a = 7:

$7 \times 13 = 91 = 6 \times 15 + 1 \equiv 1 \pmod{15}$

Por tanto: $x \equiv 13 \pmod{15}$

Para a = 8:

$8 \times 2 = 16 \equiv 1 \pmod{15}$

Por tanto: $x \equiv 2 \pmod{15}$

Para a = 11:

$11 \times 11 = 121 = 8 \times 15 + 1 \equiv 1 \pmod{15}$

Por tanto: $x \equiv 11 \pmod{15}$

Para a = 13:

$13 \times 7 = 91 \equiv 1 \pmod{15}$

Por tanto: $x \equiv 7 \pmod{15}$

Para a = 14:

$14 \times 14 = 196 = 13 \times 15 + 1 \equiv 1 \pmod{15}$

Por tanto: $x \equiv 14 \pmod{15}$

Podemos verificar usando el algoritmo extendido de Euclides para cada caso, pero los resultados obtenidos por tanteo son correctos.

Respuesta: La congruencia tiene solución para $a \in \{1, 2, 4, 7, 8, 11, 13, 14\}$, que son exactamente los elementos invertibles en $\mathbb{Z}_{15}$.