Order of an Element
If and are relatively prime integers, Euler's theorem says that , where is Euler's totient function. But is not necessarily the smallest positive exponent that satisfies the equation ; the smallest positive exponent is called the order of mod .
Analysis of the orders of elements has numerous applications in elementary number theory. In particular, the proof of the theorem on the existence of primitive roots hinges upon counting elements of a given order and answering questions about which orders are possible.
This definition of order is consistent with other, more general definitions of "order" in group theory and set theory. In particular, the number of elements in a set is sometimes referred to as its order. In this case, the order of is the (set-theoretic) order of the set of powers of mod . (In the language of group theory, the order of is the order of the cyclic subgroup generated by .)
Definition
Given a positive integer and an integer such that the smallest positive integer for which mod is called the order of modulo . Note that Euler's theorem says that , so such numbers indeed exist. The order of mod is sometimes written as for short.
There are distinct congruence classes mod of integers that are relatively prime to , namely . Compute their orders mod .
- The powers of are . The order of is .
- The powers of are . The order of is .
- The powers of are . The order of is .
- The powers of are . The order of is .
- The powers of are . The order of is .
- The powers of are . The order of is .
The example suggests another way to think about the order: the sequence of powers of is periodic, and the order of is simply the minimum period of this sequence.
Basic Properties
Notice that in each case of the previous example, the order was , as noted above. Moreover, the order was always a divisor of . This is true in general:
If , then .
; if is a prime, then for any .
If , then .
In order to prove property , let . Since and , for any nd . By Bezout's identity, there exist and such that Then, from the minimality of it follows that , which cannot hold unless they are equal and .
(Another way to see (1) is that the minimum period of a periodic sequence divides any other period, essentially by the division algorithm.)
Property (2) follows from property (1) and Euler's theorem, and property (3) follows from property (1) applied to .
Prove that for all positive integers and .
It is immediate that : certainly , and implies , so . Then the result follows from property (1) above.
If with prime and , then .
It follows from property (1) above that , so must equal either or . Since , the order cannot be , so it is .
Prove that there does not exist an integer such that .
Suppose there does exist such , and let be the smallest prime divisor of . Then it follows from that . However, we know by property (2) above and (the order is divisible by a prime); thus , which contradicts being the smallest prime divisor of .
Prove that any prime factor of the Fermat number is congruent to modulo . Show that there are infinitely many prime numbers of the form for any fixed .
Consider a prime such that ; that is, .Then and consequently . So for some . We will prove that in fact . Indeed, if this is not the case, then and so . But this implies that , so , but this is impossible. Therefore, we have found that and so by Property (1) above.
The second part is a direct consequence of the first. Indeed, it is enough to prove that there exists an infinite set of Fermat numbers , any two relatively prime. Then we could take a prime factor of each such Fermat number and apply the first part to obtain that each such prime is of the form . Not only is it easy to find such a sequence of co-prime Fermat numbers, but in fact any two distinct Fermat numbers are relatively prime. Indeed, suppose that . Then and so . Combining this with , we obtain a contradiction. Hence both parts of the problem are solved.
Primitive Roots mod p
The positive integer is called a primitive root mod if and . The proof that primitive roots exist mod where is a prime involves counting elements of various orders mod . Here is an outline.
Step 1: Prove a version of the division algorithm for polynomials with coefficients in . That is, given two polynomials and with coefficients in , we can write for some polynomials and , such that or deg deg .
Step 2: Use step 1 to show that a polynomial of degree has at most roots mod : If is a root of , write and evaluate at to show that . Induct on the degree of . Note that we are using that is prime in a subtle way: namely, if , then , so either or . This last conclusion fails for composite modulus in general. For instance, has four roots mod .
Step 3: Suppose there is an element of order , . Then has at most roots mod , by step 2, but on the other hand are all distinct roots. So this is the entire set of roots. Show that exactly of these roots have order (because the others have smaller orders).
Step 4: For every divisor , let be the number of elements of order mod . Step 3 shows that either or . Now every nonzero element mod has some order , so the sum of the is : (This last equality is proved in the page on proofs by bijections.) So equality holds everywhere, so we have proved:
Let be an odd prime. For every , there are exactly elements of order in .
In particular, there are primitive roots.
Prime Divisors of 1 mod p
What do all prime divisors of have in common?
To list the first few, we have
Notice that all the primes are either or . In other words, it appears that all prime divisors of that are greater than are of the form . Indeed, the observation is true and can be generalized as follows:
If is a prime divisor of , then either or .
Although this result is immediate by cyclotomic polynomials, it is also simple using the divisibility properties of order. We make use of the following handy lemma:
If with prime and , then .
It follows from property (1) above that , so must equal either or . Since , the order cannot be , so it is .
Since , satisfies .
If , then .
If , then according to the property above , i.e .