Vamos $a$, $b$, y $n$ ser enteros con $0 \le a \lt n$$0 \le b \lt n$. Supongamos $a \equiv b \pmod n$. A continuación,$a-b=0$$a=b$. ¿Por qué la congruencia de dos enteros negativos implica que ellos deben ser iguales?
Respuestas
¿Demasiados anuncios?
No es suficiente que $a,b$ son no negativos, también es necesario que los $a,b$ son de menos de $n$. Con estas dos condiciones, a continuación, $a\equiv b$ implica que el $a=b$. La razón es que el $a\equiv b$ significa que $a-b$ es un múltiplo entero de $n$. Sin embargo, este múltiplo entero no puede ser $n$ o más ( $a\ge b+n$ , imposible), ni $-n$ o menor ( $a+n\le b$ , también es imposible). Por lo tanto el único múltiplo entero de $n$ disponible es $0n$.
Hurkyl
Puntos
57397
La clave del truco aquí es la interacción entre la magnitud y la divisibilidad — cada distinto de cero múltiples de $n$ debe tener una magnitud de al menos tan grande como $n$.
Simbólicamente, si $k \neq 0$,$|kn| \geq |n|$.
Desde enteros en la misma congruencia de la clase están separados por múltiplos de $n$, esto pone un límite a la distancia a la que puede ser. Tenemos
Si $a \equiv b \bmod n$$a \neq b$, $|a-b| \geq |n|$
La premisa de que el problema se restringe tanto $a$ $b$ a un estrecho intervalo: ambos están contenidos en el conjunto de $\{ 0, 1, \ldots, n-1 \}$. La mayor diferencia posible entre dos elementos de este conjunto tiene magnitud $n-1$. Es decir, para cualesquiera dos elementos de la $x,y$ de este conjunto, tenemos $|x-y| \leq n-1$.
Así que por la observación anterior, el hecho de que $a \equiv b \bmod n$ implica que una de las condiciones siguientes es verdadera:
- $a = b$
- $|a-b| \geq n$
y podemos descartar la segunda posibilidad, porque $|a-b| \leq n-1$.
David HAust
Puntos
2696
W. l.o.g. $\ 0 \le b\le a < n\,\Rightarrow\, 0\le a\!-\!b < n,\ $ $\ n\mid a\!-\!b\iff a\!-\!b = 0$
Comentario $ $ Este espectáculo la singularidad parte del hecho de que $\,0,1,2,\ldots,n\!-\!1\,$ forman un sistema completo de representantes de clases de equivalencia de a $\,\Bbb Z_n = $ enteros $\!\bmod n.\,$ La misma prueba que funciona para cualquier secuencia de $n$ enteros consecutivos, ya que - como el anterior - que cualquiera de los dos elementos difieren en menos de $n$, por lo que su diferencia es divisible por $n$ sólo si son iguales.
