Demuestre que $a \equiv b$ (mod $n$ ) si y sólo si $r = s$ .

Question

Sea $a, b \in \mathbb{Z}$ y que $n \in \mathbb{N}$ . Escriba a $a = qn + r$ y $b =q'n+s$ con $q,q' \in \mathbb{Z}$ y $r, s \in \{0,1,\ldots,n-1\}$ según el algoritmo divion.

Demuestra que $a \equiv b$ (mod $n$ ) si y sólo si $r = s$ .

Mi intento: Prueba. ( $\Rightarrow$ ) Supongamos que $a \equiv b$ (mod $n$ ). Esto implica que $n \mid a-b$ y $a - b =(qn+r)-(q'n+s)= n(q-q')+(r-s) = nk$ para algunos $k \in \mathbb{Z}$ . Si $n \mid (r-s)$ entonces $(\star)\hspace{1mm} r-s = nc$ para algunos $c \in \mathbb{Z}$ pero si $r = n-1$ y $s = 0$ entonces $(\star)$ se convierte en $n-1 = nc$ que no se cumple para ningún $c \in \mathbb{Z}$ . De ello se deduce que $n \nmid r-s$ a menos que $r-s = 0$ demostrando que $r = s.$ $(\Leftarrow)$ Por otro lado, supongamos que $r = s$ . Entonces $r- s = 0$ y $a- b = (qn+r)-(q'n+s) = n(q-q') + (r-s) = n(q-q') + 0 = nq - nq' = nk.$ De ello se deduce que $a \equiv b$ (mod $n).\hspace{1mm} \Box$

Sé que al probar la $(\Rightarrow)$ parte, cometí un error. Yo realmente no muestran que $r-s = 0$ . Mi TA dijo que tendría que demostrar que $|r-s| < n$ para mostrar $r-s = 0$ pero no sé muy bien por qué. Sé que desde $r$ y $s$ son restos, por lo que $0 \leq r \leq n$ y $0 \leq s \leq n$ . ¿Cómo puedo demostrar que $|r-s| < n$ y por qué esto demuestra que $r-s$ debe ser $0$ ?

Answer 1

Usted ha hecho todos los pasos para demostrar que $|r-s|<n$ - sólo que no las has dicho explícitamente. Cuando escribió "si $r=n-1$ y $s=0$ ", lo que estás diciendo es $$|r-s| \le n-1 - 0 = n-1 < n$$ que es exactamente lo que necesitabas mostrar.

---

Sin embargo, hay una forma más limpia de hacer esta pregunta.

Tenemos $$\begin{align}a \equiv b \pmod n &\iff (q-q')n + (r-s) \equiv 0\pmod n\\&\iff (r-s) \equiv 0 \pmod n\\&\iff r\equiv s \pmod n\end{align}$$

Pero $0\le r,s\le n-1$ por lo que debemos tener $r=s$ .