Demostrar que si $\gcd(a,n)=1$ entonces los enteros $c,c+a,c+2a,\ldots,c+(n-1)a$ forman un conjunto completo de residuos modulo $n$ para cualquier $c$

Question

Supongo que tengo que demostrar que los enteros dados son iguales a $0,1,2,\ldots, (n-1)$ mod n tomados en algún orden. Sin embargo, no estoy seguro de cómo empezar, ¿alguna ayuda?

Answer 1

Supongamos que hay $i< j$ tal que $i,j\in\{0,\ldots,n-1\}$ y $$ c+ia\equiv c+ja\;(\text{mod } n) $$ entonces $n$ divide $(j-i)a$ que es una contradicción con $0<j-i<n$ y $\text{gcd}(a,n)=1$ . Esto significa que el conjunto de $n$ números $\{c,c+a,+\ldots,c+(n-1)a\}$ tienen residuos distintos módulo $n$ . Pero hay exactamente $n$ residuos distintos módulo $n$ por lo que la conclusión es la siguiente.

Answer 2

Lema: Los números enteros $a, 2a, 3a, \ldots na$ son un sistema completo de residuos módulo $n$ .

Prueba: Hay $n$ números en este conjunto, por lo que basta con demostrar que todos son inequivalentes módulo $n$ . Si no es así, para algunos $0<k<j<n$ tenemos

$$n|(ka-ja)$$

Como $0<|k-j|<n$ , $n\not | (k-j)$ pero también $\gcd (n,a)=1$ , una contradicción con el teorema de que $\gcd(a,b)=1$ implica que $a|(bc)\implies a|c$ . $\square$

Teorema: Cualquier traducción de un sistema de residuos completo es también un sistema de residuos completo. Es decir, si $\{x_1,\ldots, x_n\}$ es un sistema completo de residuos, también lo es $\{c+x_1,\ldots, c+x_n\}$

Prueba: Una vez más, sólo tenemos que demostrar que todos ellos son inequivalentes módulo $n$ . Esto se debe a que

$$n|(c+x_i-(c+x_j))\iff n|(x_i-x_j),\quad 1\le i\ne j\le n$$

Sin embargo, $x_i\not\equiv x_j\mod n$ así que por definición.., $x_i-x_j\not\equiv 0\mod n\iff n\not |(x_i-x_j)$ . $\square$

Desde $a, 2a, 3a, \ldots, (n-1)a$ es un sistema de residuos completo, también lo es $c+a, c+2a,\ldots, c+(n-1)a$ .