1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.