2
$\begingroup$

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
    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?2010-10-18
  • 0
    Besides, what you just wrote is not a proof of the fact you claim.2010-10-18
  • 10
    @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.2010-10-18
  • 0
    Pick some small numbers and see how it works. You can learn a lot.2010-10-18
  • 5
    Hmm, 6 questions on related topics in the past 3 hours...2010-10-18
  • 2
    First you need to tell us precisely what "does not make sense", and why.2010-10-18
  • 0
    What happens if a=3, n=5? 2 is special, so may not give you a proper clue.2010-10-18

2 Answers 2

4

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

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

1

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.