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 '12 at 11:18
  • 2
    $\begingroup$ Please note that there is no notion of "coprimes"; instead, "coprimeness" is a relation that may or may not hold between two or more integers. $\endgroup$ – Zev Chonoles Jul 15 '12 at 12:58
  • $\begingroup$ @did: x, for values of x between Venice and Padua. $\endgroup$ – Tobia Tesan Jul 19 '12 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$ – Tobia Tesan Jul 19 '12 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$ – Zev Chonoles Jul 19 '12 at 18:07
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$ – Tobia Tesan Jul 15 '12 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$ – Tobia Tesan Jul 15 '12 at 10:25
  • 1
    $\begingroup$ @tobiatesan: I think we can share the blame for that :-) $\endgroup$ – joriki Jul 15 '12 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$

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.