Some time ago, I posted a question on six primes numbers forming an arithmetic progression, and someone commented the following: " Let $m$ and $n$ be positive integers with $\gcd(m,n)=1$. Then the sequence $m,2m,3m,…,nm$ when taken mod $n$ will give the integers from $1$ to $n$ , each occurring exactly once ". I wanted to know why so I tried to "prove" it, this what I did:

I supposed the contrary, that in the sequence $a_1 m \equiv a_2 m \pmod n$, with the condition that $a_1\not \equiv a_2 \pmod n$ (I do not know if it´s possible to use that notation but it just means that they are not congruent) , because $a_1 \neq a_2$ and because both $a_1$ and $a_2$ and have to be less or equal to $n$ .

So I did this:

$a_1 m \equiv a_2 m \pmod n$

$a_1 m - a_2 m \equiv 0 \pmod n$

$(a_1 - a_2)m\equiv 0 \pmod n$

This means that $(a_1 - a_2)m$ is a multiple of $n$, but this is a contradiction because $\gcd(m,n)=1$ and since $a_1\not \equiv a_2 \pmod n$ then $a_1 - a_2 \not \equiv 0 \pmod n$, which means that $a_1 - a_2$ doesn´t have all factors of $n$ and therefore it is not a multiple.

This may be in a textbook, so sorry if I made you lose your time.

Anyway, I would just like you to tell me if it´s ok what I did.

  • $\begingroup$ That's all good. $\endgroup$ – Arnaud Mortier Jun 14 '18 at 22:04

Your argument is perfect. Note that the property $$\text{$m,2m,3m,…,nm$ when taken mod $n$}\\ \text{will give the integers from $1$ to $n$,} \\ \text{each occurring exactly once.}$$ is another way of saying that $$\text{$m$ is a generator of the group $\Bbb Z/n\Bbb Z$}.$$

which is equivalent to $m,n$ being coprime like you said.

Since you have gone all this way, you might as well want to learn a bit of group theory for free!

| cite | improve this answer | |
  • 1
    $\begingroup$ Which is another way of saying $m$ is a unit in $\mathbb Z_n$; and there are $\phi (n)$ of them... $\endgroup$ – Chris Custer Jun 14 '18 at 22:14
  • $\begingroup$ @Arnaud Mortier could you explain me the notations you are using here please? I also have another question. I know that the sign used in modular arithmetic ($ \equiv $) behaves a lot like the equal sign in equations. The only operation you can't do is division but I heard that there was an exception to that rule, I can't remember how it was, but I was like if $ax \equiv m \pmod n$ then you could divide if $n$ and $x$ were coprime or something like that. Could you explain it to me and also tell me and explanation of why it happens please? $\endgroup$ – Vmimi Jun 16 '18 at 4:08
  • $\begingroup$ I think that in my comment $m$ had to be $0$, but I can't remember, that's why I put $m$. $\endgroup$ – Vmimi Jun 16 '18 at 4:22
  • $\begingroup$ @Vmimi If you have never seen the notation $\Bbb Z/n\Bbb Z$ it may be that you are a victim of the $\Bbb Z_n$ flu. $\endgroup$ – Arnaud Mortier Jun 16 '18 at 16:26
  • $\begingroup$ @Vmimi As for your second question, you're right, you can divide by $x$ if and only if $x$ is coprime with $n$, and the reason is related to the OP: since $x,2x,\etc,nx$ represents once every integer modulo $n$, it means that for some integer $k$, you have $kx=1\bmod n$. You call that $k$ "$x$ inverse", and multiplying by $k$ is like dividing by $x$. $\endgroup$ – Arnaud Mortier Jun 16 '18 at 16:29

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.