Ejercicios resueltos de verificación de congruencias

Para que $a \equiv b \pmod{n}$, debe cumplirse que $n | (a - b)$.

$247 - 7 = 240$

$240 \div 15 = 16$

Como $240 = 15 \times 16$, entonces $15 | 240$.

Por tanto, $247 \equiv 7 \pmod{15}$ $\checkmark$

Verificación alternativa: $247 \bmod 15 = 7$ y $7 \bmod 15 = 7$ $\checkmark$

$-89 = -7 \times 13 + 2 = -91 + 2$

Por tanto, $-89 \equiv 2 \pmod{13}$

Primero calculamos $183 \bmod 13$:

$183 = 14 \times 13 + 1 = 182 + 1$

Por tanto, $183 \equiv 1 \pmod{13}$

$-89 \equiv 2 \pmod{13}$

$183 \equiv 1 \pmod{13}$

Como $2 \neq 1$, entonces $-89 \not\equiv 183 \pmod{13}$

Para encontrar un número que sea congruente con $-89$:

$-89 \equiv 2 \pmod{13}$

Un ejemplo sería: $-89 \equiv 15 \equiv 28 \equiv 41 \pmod{13}$

Verificación: $41 - (-89) = 130 = 10 \times 13$ $\checkmark$

Dado:

• $a \equiv b \pmod{n} \Rightarrow n | (a - b) \Rightarrow a = b + kn$ para algún $k \in \mathbb{Z}$
• $c \equiv d \pmod{n} \Rightarrow n | (c - d) \Rightarrow c = d + \ell n$ para algún $\ell \in \mathbb{Z}$

$(a + c) - (b + d) = (a - b) + (c - d)$

Como $n | (a - b)$ y $n | (c - d)$, entonces:

$(a - b) = kn$ y $(c - d) = \ell n$

Por tanto: $(a + c) - (b + d) = kn + \ell n = (k + \ell)n$

Esto significa que $n | [(a + c) - (b + d)]$, por tanto $a + c \equiv b + d \pmod{n}$ $\checkmark$

$ac - bd = a(d + \ell n) - bd = ad + a\ell n - bd = d(a - b) + a\ell n$

Como $a - b = kn$:

$ac - bd = d \cdot kn + a\ell n = n(dk + a\ell)$

Por tanto, $n | (ac - bd)$, lo que implica $ac \equiv bd \pmod{n}$ $\checkmark$

Sean $a = 17$, $b = 5$, $c = 23$, $d = 11$ con $n = 12$:

• $17 \equiv 5 \pmod{12}$ $\checkmark$
• $23 \equiv 11 \pmod{12}$ $\checkmark$

Verificación suma: $(17 + 23) \equiv (5 + 11) \pmod{12} \Rightarrow 40 \equiv 16 \pmod{12} \Rightarrow 4 \equiv 4 \pmod{12}$ $\checkmark$

Verificación producto: $17 \times 23 \equiv 5 \times 11 \pmod{12} \Rightarrow 391 \equiv 55 \pmod{12} \Rightarrow 7 \equiv 7 \pmod{12}$ $\checkmark$

Tenemos:

• $x \equiv 3 \pmod{7} \Rightarrow x = 7k + 3$ para algún $k \in \mathbb{Z}$
• $x \equiv 5 \pmod{11}$

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

$7k \equiv 2 \pmod{11}$

Necesitamos $7a \equiv 1 \pmod{11}$:

$7 \times 8 = 56 \equiv 1 \pmod{11}$

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

$k \equiv 2 \times 8 \equiv 16 \equiv 5 \pmod{11}$

Entonces $k = 11j + 5$ para algún $j \in \mathbb{Z}$

$x = 7k + 3 = 7(11j + 5) + 3 = 77j + 35 + 3 = 77j + 38$

Por tanto, $x \equiv 38 \pmod{77}$

Para $j = -1$: $x = 77(-1) + 38 = -39$

Para $j = 0$: $x = 77(0) + 38 = 38$

Para $j = 1$: $x = 77(1) + 38 = 115 > 100$

Para $x = -39$:

• $-39 = 7(-6) + 3 \Rightarrow -39 \equiv 3 \pmod{7}$ $\checkmark$
• $-39 = 11(-4) + 5 \Rightarrow -39 \equiv 5 \pmod{11}$ $\checkmark$

Para $x = 38$:

• $38 = 7(5) + 3 \Rightarrow 38 \equiv 3 \pmod{7}$ $\checkmark$
• $38 = 11(3) + 5 \Rightarrow 38 \equiv 5 \pmod{11}$ $\checkmark$

Las soluciones son: $x \in \{-39, 38\}$