4
$\begingroup$

I recently came upon a strange pattern, and have absolutely no idea why it exists. I was hoping for an explanation.

Let there be three integers: $p$, $a$ and $n$; $p$ is any prime number, while $a$ and $n$ are numbers such that 1\leq a < p and 1 \leq n < p

Let Set $S$ be $\{{an^1\pmod p, an^2\pmod p, \dots, an^{p-1}\pmod p\}}$. Why is it that the number of distinct numbers in Set $S$ is always a divisor of $p-1$?

An example : Let $p$ be 7, $a$ be $3$ and $n$ be $2$.

Therefore Set S would be : $\{{3 * 2^1\pmod7,\dots,3* 2^6\pmod7\}}$

which equals to: $6\pmod 7$, $5\pmod7$, $3\pmod 7$, $6\pmod7$, $5\pmod7$, $3\pmod7$.

There are 3 distinct numbers in this set. $6$, or $p-1$, is divisible by $3$.

This is true for any prime $p$. Why is the number of distinct numbers in Set $S$ always a divisor of $p-1$?

I realize this is a seemingly random pattern, but I need to understand it to complete my paper.

  • 1
    Fixed link: [Lagrange's theorem (group theory)](http://en.wikipedia.org/wiki/Lagrange%27s_theorem_%28group_theory%29)2012-04-23

3 Answers 3

2

Without group theory:

Look at your 7, 3, 2 example. Note how the numbers go 6, 5, 3, 6, 5, 3; you get the distinct numbers 6, 5, 3, and then they repeat. Well, that always happens: you get a string of distinct numbers, and then that string repeats, exactly, until you get to the end. Since you write down $p-1$ numbers total, and the string repeates exactly until you have written down the $p-1$ numbers, the number of numbers in the string must be a factor of $p-1$.

Well, there are a few assertions in that paragraph that need to be proved. You don't need group theory to prove them, you can find the topic discussed (although not in exactly the terms I've used) in any introductory Number Theory text. I'm sorry, but I'm not up to writing it all out here.

  • 0
    Awesome, thanks!2012-04-24
2

Hint $\ $ Given you have no knowledge of group theory, you can employ these two simple facts.

$(1)\ \ \ \rm mod\ p\!:\ n^{p-1}\equiv 1\ \Rightarrow\:$ the order k of n divides $\rm p\!-\!1,\:$ i.e. $\:\!$ if $\rm\:k>0\:$ is least such that $\rm n^k\equiv 1\:$ then $\rm\:k\ |\ p\!-\!1.\:$ Thus the sequence of powers $\rm\:n,n^2,\ldots,n^{p-1}\:\!$ decomposes into the subsequence $\rm\:n,n^2,\ldots,n^k\!\equiv\! 1\:$ repeated $\rm\:(p\!-\!1)/k\:$ times.

$(2)\ \ $ The map $\rm\:x \to a\:\!x\:$ is $1\!-\!1$ since $\rm\:a\not\equiv 0\:$ $\Rightarrow$ $\rm\:a^{-1}\:$ exists mod $\rm p.\:$ Hence scaling all elements of the repeated subsequence by $\rm\: a\:$ preserves its length, i.e. the elements remain distinct. Note that the elements of the original subsequence are distinct, else $\rm\:n^i \equiv n^j\:$ for $\rm\:1\le i < j \le k\:$ yields $\rm\:n^{j-i}\equiv 1\:$ for $\rm\:0 < j\!-\!i < k,\:$ contra minimality of $\rm k$ (here, again, we've used the fact that $\rm\: mod\ p\!:\ n\not\equiv 0\:$ implies that $\rm\:n^{-1}$ exists, hence $\rm\:n\:$ is cancellable from both sides of a congruence).

0

This is an example of Lagrange's theorem in group theory. The elements $an^k$ form a coset in the group $U_p$, the multiplicative group of the field of $p$ elements.

  • 0
    @Qiaochu, sure, but the phenomenon was known long before there was any such discipline as group theory, and can be explained without any reference to group theory.2012-04-23