Is there a simple (read primarily elementary) proof that performing $6k \mod p$ where $k$ runs from $1$ to $p$ will always return the sequence of counting numbers from $[0,1,2,...,p-1]$ (though not in that order), for all $p >= 5$?
Asked
Active
Viewed 34 times
2 Answers
2
We need to assume $p\gt 3$. Consider the remainders when the $p$ numbers $6\cdot 1$, $6\cdot 2$, $6\cdot 3$, and so on up to $6\cdot p$ are divided by $p$. These remainders are all in the interval $[0,p-1]$. If we can show they are all different, then we will know they take on, in some order, all values from $0$ to $p-1$.
Suppose to the contrary the remainders are not all different. Then there exist integers $1\le i\lt j\le p$ such that $6i$ and $6j$ have the same remainder on division by $p$. It follows that $p$ divides $6j-6i$, that is, $6(j-i)$. But $p$ is relatively prime to $6$, so $p$ divides $j-i$. This is impossible, since $1\le j-i\lt p$.
André Nicolas
- 507,029
1
Yes. For $p\ge 5$, $6$ is invertible modulo $p$, hence multiplication by $6$ is a bijection.
Bernard
- 175,478
-
You mean multiplication by $6$ mod $p$. – user236182 Oct 10 '15 at 22:58
-
Oops! It's getting late here… I'll correct that. Thanks for pointing it. – Bernard Oct 10 '15 at 23:18