Prove that the integers ## c, c+a, c+2a, c+3a, ...., c+(n-1)a ## ....

[Math100]

Homework Statement

Prove the following statement:
If $gcd(a, n)=1$, then the integers $c, c+a, c+2a, c+3a, ..., c+(n-1)a$ form a complete set of residues modulo $n$ for any $c$.

Relevant Equations

None.

Proof:

Suppose for the sake of contradiction that $r, s\in {0, ..., n-1}$ for $r<s$ where $c+ra\equiv c+sa\pmod {n}$.
Then $c+ra\equiv c+sa\pmod {n}\implies ra\equiv sa\pmod {n}\implies r\equiv s\pmod {n}$.
Thus $n\mid (r-s)\implies n<r-s$, which is a contradiction because $r\leq n-1$ and $s\leq n-1$ together implies $s-r<n$.
Therefore, if $gcd(a, n)=1$, then the integers $c, c+a, c+2a, c+3a, ..., c+(n-1)a$ form a complete set of residues modulo $n$ for any $c$.

 

[Delta2]

I find this proof mostly correct. Two minor mistakes or to be more accurate, incomplete statements:

• You should 've stated that because $gcd(a,n)=1$ then it follows that it holds $$ra\equiv sa \pmod n\Rightarrow r\equiv s \pmod n$$
• We end up with $n<r-s$ which it should be actually $n<s-r$ (maybe that's a typo ) because you initially took $r<s$ hence $r-s$ is negative. And the fact that $s-r<n$ comes from $s\leq n-1$ and $r\geq 0$.

 

[fresh_42]

Homework Statement:: Prove the following statement:
If $gcd(a, n)=1$, then the integers $c, c+a, c+2a, c+3a, ..., c+(n-1)a$ form a complete set of residues modulo $n$ for any $c$.
Relevant Equations:: None.

Proof:

Suppose for the sake of contradiction that $r, s\in {0, ..., n-1}$ for $r<s$ where $c+ra\equiv c+sa\pmod {n}$.
Then $c+ra\equiv c+sa\pmod {n}\implies ra\equiv sa\pmod {n}\implies r\equiv s\pmod {n}$.

This is already the contradiction since $s-r\in \{0,\ldots,n-1\}$ is a complete set of remainders.

Thus $n\mid (r-s)\implies n<r-s$, which is a contradiction because $r\leq n-1$ and $s\leq n-1$ together implies $s-r<n$.

You should have used $s-r$ since $r-s <0$ which makes things complicated, e.g. $n<r-s$ is wrong.<

Therefore, if $gcd(a, n)=1$, then the integers $c, c+a, c+2a, c+3a, ..., c+(n-1)a$ form a complete set of residues modulo $n$ for any $c$.

Where did you use $gcd(a, n)=1$?

You have shown that no two remainders $c+ra,c+sa$ can be the same modulo $n$ without being equal as integers. How do we know that all remainders actually occur?

 

[Math100]

Suppose for the sake of contradiction that $r, s\in \{0, ..., n-1\}$ for $r<s$ where $c+ra\equiv c+sa\pmod {n}$.
Since $gcd(a, n)=1$, it follows that $c+ra\equiv c+sa\pmod {n}\implies ra\equiv sa\pmod {n}\implies r\equiv s\pmod {n}$.
Then $n\mid (r-s)\implies n<s-r$, which is a contradiction because $r\leq n-1$ and $s\leq n-1$ together implies $s-r<n$.
Thus, any two of the integers $c, c+a, c+2a, c+3a, ..., c+(n-1)a$ are incongruent modulo $n$.
Therefore, if $gcd(a, n)=1$, then the integers $c, c+a, c+2a, c+3a, ..., c+(n-1)a$ form a complete set of residues modulo $n$ for any $c$.

 

[fresh_42]

You have basically repeated your former version.

Suppose for the sake of contradiction that $r, s\in \{0, ..., n-1\}$ for $r<s$ where $c+ra\equiv c+sa\pmod {n}$.
Since $gcd(a, n)=1$, it follows that $c+ra\equiv c+sa\pmod {n}\implies ra\equiv sa\pmod {n}\implies r\equiv s\pmod {n}$.

$gcd(a, n)=1$ is used in the last step because it guarantees that there is an $\alpha$ such that $\alpha \cdot a\equiv 1 \pmod n$ that is, that $a$ has a multiplicative inverse element. Now if
\begin{align*}
ra\equiv sa\pmod {n} \Longrightarrow r\equiv r\cdot 1\equiv r\cdot a\alpha \equiv s\cdot a\alpha \equiv s\cdot 1\equiv s\pmod {n}
\end{align*}
That's why the condition is needed. It guarantees the existence of $\alpha =a^{-1}.$
(see https://www.physicsforums.com/threads/prove-that-aa_-1-aa_-2-aa_-n-is-also-a-complete-set.1015722/)

Then $n\mid (r-s)\implies n<s-r$, which is a contradiction because $r\leq n-1$ and $s\leq n-1$ together implies $s-r<n$.
Thus, any two of the integers $c, c+a, c+2a, c+3a, ..., c+(n-1)a$ are incongruent modulo $n$.
Therefore, if $gcd(a, n)=1$, then the integers $c, c+a, c+2a, c+3a, ..., c+(n-1)a$ form a complete set of residues modulo $n$ for any $c$.

 

[Math100]

You have basically repeated your former version.

$gcd(a, n)=1$ is used in the last step because it guarantees that there is an $\alpha$ such that $\alpha \cdot a\equiv 1 \pmod n$ that is, that $a$ has a multiplicative inverse element. Now if
\begin{align*}
ra\equiv sa\pmod {n} \Longrightarrow r\equiv r\cdot 1\equiv r\cdot a\alpha \equiv s\cdot a\alpha \equiv s\cdot 1\equiv s\pmod {n}
\end{align*}
That's why the condition is needed. It guarantees the existence of $\alpha =a^{-1}.$
(see https://www.physicsforums.com/threads/prove-that-aa_-1-aa_-2-aa_-n-is-also-a-complete-set.1015722/)

If $gcd(a, n)=1$ should be used in the last step, then where should I insert/include that "There exists an $\alpha$ such that $\alpha\cdot a\equiv 1\pmod {n}\Longleftrightarrow gcd(a, n)=1$"?

 

[fresh_42]

If $gcd(a, n)=1$ should be used in the last step, then where should I insert/include that "There exists an $\alpha$ such that $\alpha\cdot a\equiv 1\pmod {n}\Longleftrightarrow gcd(a, n)=1$"?

It was ok what you wrote. I only wanted to explain where it is actually used because it isn't apparent by itself.

$gcd(a, n)=1$ makes $a$ a unit (multiplicative invertible element) modulo $n$, i.e. in $\mathbb{Z}/n\mathbb{Z}=\mathbb{Z}_n=\{0,1,2, \ldots,n-1 \}$ and this allows us to cancel it from the equation $r\cdot a \equiv s\cdot a.$

A counterexample if $gcd(a, n)\neq 1$ is the following:
Set $n=12\, , \, a=8\, , \,r=6\, , \,s=3.$ Here we have $6\cdot 8 \equiv 0 \equiv 3\cdot 8 \pmod {12}$ but $r\neq s.$