5
$\begingroup$

Why is it that $\{1\cdot a \pmod p, 2\cdot a \pmod p,\ldots, (p-1)\cdot a \pmod p\} = \{1, 2,\ldots, p-1\}$ (albeit in a different order) when a and p are coprimes?

I can't figure this out and I've been beating my head for the whole weekend.

Googling around I've found mention of Fermat's Little Theorem (e.g. here), but I can't see how it helps me.

I've verified it by hand, it seems perfectly believable to me (mostly because I find myself thinking of the way the circle of fifths works), but I can't come up with a good proof.

Any help, pretty please?

Thanks a lot.

P.S.: Pardon my English. I'm from the land of pizza and mandolins.

$\endgroup$
5
  • 2
    $\begingroup$ +1 for the post-scriptum. Quale città? $\endgroup$
    – Did
    Jul 15, 2012 at 11:18
  • 2
  • $\begingroup$ @did: x, for values of x between Venice and Padua. $\endgroup$ Jul 19, 2012 at 18:04
  • $\begingroup$ @Zev, thanks, that's what I meant. How do you say it in English, then - "a is coprime to b"? $\endgroup$ Jul 19, 2012 at 18:06
  • $\begingroup$ @tobiatesan: Yes, that's fine; an alternative would be that "$a$ and $b$ are coprime to each other", or if you are speaking about many numbers $a_i$, you could say "the $a_i$ are mutually coprime" or "the $a_i$ are pairwise coprime". $\endgroup$ Jul 19, 2012 at 18:07

3 Answers 3

7
$\begingroup$

Suppose $ra$ and $sa$ are the same, modulo $p$. Then $sa-ra$ is a multiple of $p$. So $(s-r)a$ is a multiple of $p$. But by hypothesis $a$ and $p$ are coprime, so $s-r$ is a multiple of $p$. But if $r$ and $s$ are between 1 and $p-1$, inclusive, then $s-r$ can't be a multiple of $p$ unless $r=s$.

This shows that all the numbers in the first set in your question are different. Since zero doesn't appear in that set, and since there are $p-1$ numbers in that set, they must be the same as the numbers in the second set in your question.

$\endgroup$
1
  • $\begingroup$ Brilliant. I like it. I wouldn't have been able to do what you've done there on my own, that is, being clever enough to just concentrate on proving that the numbers in the first set are unique and let everything else snap in place. Thank you a lot. $\endgroup$ Jul 15, 2012 at 10:21
3
$\begingroup$

If it weren't the case, that would mean that you can get back to the same place in $n\lt p$ steps of $a$; that is, we would have $na=kp$ for some integer $k$. But $a$ and $p$ are coprime, so all the factors of $p$ have to come from $n$, which contradicts $n\lt p$.

$\endgroup$
2
  • $\begingroup$ Thanks. Concise, sharp, like it, but, honestly, I wouldn't have been able to understand it without reading Gerry's first, but that's mostly my fault. $\endgroup$ Jul 15, 2012 at 10:25
  • 1
    $\begingroup$ @tobiatesan: I think we can share the blame for that :-) $\endgroup$
    – joriki
    Jul 15, 2012 at 10:26
3
$\begingroup$

This can be interpreted as a group-theoretic result: the set of numbers coprime to $n$ form a group under multiplication modulo $n$. The hardest part of this is showing that inverses exist. This follows from Bézout's theorem, which states that for any $a$ and $n$ there exist $x$ and $y$ coprime such that $ax + yn = \gcd(a,n)$. From this we can see that if $a$ and $n$ are coprime, i.e. $\gcd(a,n)=1$, then $ax$ is $1$ mod $n$, and $x$ must be coprime to $n$ too (because $\gcd(r,s)$ divides any combination of $r$ and $s$, and here we have a combination of $x$ and $n$ that gives 1), so $a$ has a multiplicative inverse modulo $n$.

Anyway, once you've got that the set of numbers coprime to $n$ form a group under multiplication modulo $n$, that's essentially equivalent to saying the map "multiply by $a$" is a bijection modulo $n$. That's essentially the same as your original statement.

(Technicality: we showed that multiply-by-$a$ is invertible in the group of numbers coprime to $n$ modulo $n$, when really what we wanted was for it to be invertible in the set of numbers modulo $n$, but it's not hard to see that the argument above extends to that case. I suppose what I'm really doing is showing that $a$ is a unit in the ring of numbers modulo $n$, and the group I mentioned is the group of units in that ring).

This answer uses some more heavyweight machinery than necessary, but I think it's a neat way of looking at the result.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .