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*}

  • 6
    $\begingroup$ 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? $\endgroup$ Oct 18 '10 at 2:59
  • $\begingroup$ Besides, what you just wrote is not a proof of the fact you claim. $\endgroup$ Oct 18 '10 at 3:00
  • 11
    $\begingroup$ @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. $\endgroup$ Oct 18 '10 at 3:10
  • 5
    $\begingroup$ Hmm, 6 questions on related topics in the past 3 hours... $\endgroup$
    – jericson
    Oct 18 '10 at 3:37
  • 3
    $\begingroup$ First you need to tell us precisely what "does not make sense", and why. $\endgroup$ 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 $\bmod n\!:\, \ a\,$ invertible $\,\Rightarrow\, a\, \{0,1,2,\ldots,n-1\}\, \equiv\, \{0,1,2,\ldots, n-1\}$

i.e. the map $\ x \to a\:x\ $ is a bijection $\bmod n\,$ so it permutes the congruence classes.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.