I am taking a elementary class on number theory this semester, and among the exercises from the third lecture there is this one:
For $m > 1$ and $gcd(m, a) = 1$, show that the remainders from the divisions of $a, 2a, 3a, ..., ma$ by $m$ are the numbers $0, 1, 2, ..., m - 1$ at some ordering.
I know this is quite a simple proof using congruence modulo m, and it's used when studying Fermat's little theorem. The problem is, we still haven't learned about congruence and modular groups, and we aren't allowed to use those concepts to solve earlier exercises. Actually, by the third lecture we still weren't taught the concept of prime numbers itself, only the concept of coprime numbers. So we are expected to prove this without using the notion of congruence. And I'm pretty stuck on it for the last 2 weeks. Any insights?
You just need to prove that no two numbers $ax$ and $ay$ leave the same remainder if $x\ne y$.
If $ax=mp+r$ and $ay=mq+r$ then $a(x-y)=m(p-q)$. Thus $m$ divides $a(x-y)$. Since $\gcd(m,a)=1$, this implies that $m$ divides $x-y$. Since $0\le x,y < m$, we have $0 \le |x-y| < m$ and so $|x-y|=0$ is the only possiblility.