# A question about properties in modular arithmetic

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.

• That's all good. – 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.
• Which is another way of saying $m$ is a unit in $\mathbb Z_n$; and there are $\phi (n)$ of them... – Chris Custer Jun 14 '18 at 22:14
• @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? – Vmimi Jun 16 '18 at 4:08
• I think that in my comment $m$ had to be $0$, but I can't remember, that's why I put $m$. – Vmimi Jun 16 '18 at 4:22
• @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. – Arnaud Mortier Jun 16 '18 at 16:26
• @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$. – Arnaud Mortier Jun 16 '18 at 16:29