# Complete residue system proof

I was given a proof of this in class, but it does not make sense to me, can someone provide a better proof, or explain the one I have provided, thanks.

Suppose $\gcd(a,n) = 1$, where $a$ and $n$ are natural numbers. Prove that $0$, $a$, $2a$, $3a,\ldots, (n-1)a$, is complete residue system modulo $n$.

Proof given in class:

\begin{align*} ka &\equiv ra \pmod{n}\\ &\Rightarrow k \equiv r \pmod{n}\\ &\Rightarrow \text{$k-r$ divides $n$}\\ &\Rightarrow \text{$k=r$ because $0\leq k\lt n$, $0\leq r\lt n$} \end{align*}

-
First of all, k = r (mod n) means that n divides k - r, not the other way around as you have written. And what's with your continuous posting of incomplete proofs of somewhat easy facts? – Adrián Barquero Oct 18 '10 at 2:59
Besides, what you just wrote is not a proof of the fact you claim. – Adrián Barquero Oct 18 '10 at 3:00
@fmunshi: I think you ought to try a bit harder on your own before posting your questions here. And looking at numerical examples is helpful when you feel clueless. – Weltschmerz Oct 18 '10 at 3:10
Hmm, 6 questions on related topics in the past 3 hours... – jericson Oct 18 '10 at 3:37
First you need to tell us precisely what "does not make sense", and why. – Gone Oct 18 '10 at 3:47

A complete residue system modulo $n$ is a set of $n$ integers containing a representative element from each congruence class modulo $n$ (see Wikipedia for more details).

A commonly used complete residue system is $\{0,1,\ldots,n-1\}$ where it is easy to see that any two elements are incongruent.

The claim states that if gcd(a,n)=1, then $\{0,a,2a,\ldots,(n-1)a\}$ is a complete residue system modulo $n$. Since there are exactly $n$ elements in this set, in order to prove the claim, it is sufficient to show that $ka \not\equiv ra \pmod n$ whenever $0 \leq k<r \leq n-1$.

Step 1: $ka \equiv ra \pmod n$ implies $k \equiv r \pmod n$. While true, I think it should be remarked that we may "divide" by $a$ only because it is comprime to $n$. In fact, it's not really division, it's multiplication by an integer $b$ such that $ab \equiv 1 \pmod n$ (which can be shown to exist using the Extended Euclidean Algorithm). So $ka \equiv ra \pmod n$ implies $kab \equiv rab \pmod n$ implies $k \equiv r \pmod n$.

Step 2: $k \equiv r \pmod n$ implies $n$ divides $k-r$. There's a typo in the OP's statement. This is by the definition of congruent modulo n.

Step 3: $n$ divides $k-r$ implies $k=r$ because $0 \leq k<r \leq n-1$. There's some information left out here in the OP's statement. In order to have $n$ dividing $k-r$ while both $k$ and $r$ are between $0$ and $n-1$, we must have $k=r$ (note that 0 is divisible by n).

-

HINT $\rm\ \ a\:$ invertible $\rm\:(mod\ n)\ \ \Rightarrow\ \ a\ \{0,1,2,\ldots,n-1\}\ \equiv\ \{0,1,2,\ldots, n-1\}\ \ (mod\ n)$

i.e. the map $\rm\ x \to a\:x\$ is a bijection $\rm\ (mod\ n)\$ so it simply permutes the congruence classes.

-