Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
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? –  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
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. –  Weltschmerz Oct 18 '10 at 3:10
5  
Hmm, 6 questions on related topics in the past 3 hours... –  jericson Oct 18 '10 at 3:37
2  
First you need to tell us precisely what "does not make sense", and why. –  Bill Dubuque Oct 18 '10 at 3:47
show 2 more comments

2 Answers

up vote 4 down vote accepted

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).

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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