Order

Order

boggart0803 20 Feb 2009 02:09

For every prime $p$
Fermat's Little Theorem tells us that for each $a$ such that $(a,p)=1$, $a^p \equiv 1 \mod{p}$
Nevertheless, we can observe that some number to a power less than $p-1$ can be congruent to $1$ modulo $p$
For each integer $a$ with $(a,p)=1$, we define the order of a to be the smallest number $d$ such that$a^d \equiv 1 \mod {p}$
For example, for p=11, the order of $1$ is $1$, the order of $2$ is 12, and so on…
I found that there are many special properties of orders
1) the order always divide $p-1$
2) the number of $a$ with $1\leq a \leq p-1$ such that the order of $a$ is $d$ is exactly $\phi (d)$
Hence this leads to a fact $\sum_{d \mid p-1} \phi(d)=p-1$

There are still many amazing properties of order, hope people can discover theorems of themself!

Re: Order

Kevin Davidsaver 21 Feb 2009 00:33

One way of looking at number 2 is that the integers $1,2,\dots,p-1$ form a cyclic group modulo $p$ with respect to multiplication. That means there is one integer that, when you multiply it with itself repeatedly, generates the whole set. Of course there are $\varphi(p-1)$ different generators for the set. That's useful because it means we can think of every non-zero number as a power of a single number modulo $p$.

As an example, 3 generates $1,2,\dots,6$ modulo 7.

And notice that the same thing doesn't happen if you use a composite modulus. If you look at the integers [$1,2,\dots,n$]] for a composite number $n$ which are coprime to $n$, you'll get the same result except you won't always hve $\varphi(d)$ elements of order $d$ for each $d$ dividing $\varphi(n)$. For instance, modulo 8 the numbers you're looking at are $1,3,5,7$ where $3,5,7$ all have order 2.

Also notice that the integers modulo $n$ are cyclic with respect to addition for all $n$, prime or composite and are always generated by the number 1. The existence of these cyclic groups lets you extend the identity from number 2 above to any $n$ as we proved in class.