Theorem-66 The Existence of Primitive Roots.pptx

Powerpoint presentation in Theory of numbers course for mscied math program

1. The Existence of Primitive Roots (Theorem 66) Daryl Dave J. Baroy

2. Theorem 66. Consider a prime p  2 and let s is a positive integer, then has a primitive root. In fact, if r is an odd primitive root modulo , then it is also a primitive root modulo if r is even, r + is a primitive root modulo .  

3. Proof. If r is a primitive root module , then by Euler’s theorem ( and no positive exponent smaller than ) has this property. Note that, ) = ) ) = ) ) = ) so that .  

4. Proof continue. If r is odd, then ( Thus by Theorem 56, we get. ( It is important to note that no smaller power of r is congruent to 1 modulo . This power as well would also be congruent to 1 modulo contradicting that r is a primitive root of . It follows that r is a primitive root modulo .  

5. Proof continue. While, if r is even, then is odd. Hence (( Because ( r+ we see that (( As a result, we see that (( and since for no smaller power of r+ is congruent to 1 modulo , we see that r+ is a primitive root modulo . QED  

6. Exercise 4. Find the values of  𝜙( )  and  𝜙( ). Since 𝑝 is a prime number and 𝑠 is a positive integer, we have  𝜙 . Now , we find  𝜙( ). Since  2  and   are coprime, we use the property that  𝜙( ) = 𝜙 (𝑚)𝜙(𝑛)  for coprime  𝑚  and  𝑛 . So , we have  𝜙( ) = 𝜙 (2)𝜙( .   Show that there are the same number of primitive roots modulo   as there are modulo   , where p is an odd prime and s is a positive integer.  

7. The order of elements modulo  . Let   𝑥  be an integer such that  (𝑥, ) = 1 . We know that the order of  𝑥  modulo   divides  𝜙( )  by Euler's theorem. Hence, the order of  𝑥 modulo   must be a divisor of  . Therefore order of  𝑥 modulo   equals  𝜙 ( ) = (𝑝−1). Thus , there are the same number of primitive roots modulo 2𝑝𝑠 as modulo 𝑝𝑠.   Exercise 4.

8. Exercise 4 . Example Let's consider an example with p = 3 and s = 2 . Modulo = = 9 Euler’s totient function of φ ( ) = 2: ≡ 2 , ≡4, ≡8 , ≡ 7, ≡ 5, ≡1. 5 : ≡ 5, ≡ 7, ≡ 8, ≡ 4, ≡2, ≡1. So , 2 and 5 is a primitive root modulo 9. Modulo = = 18 Euler’s totient function of φ ( ) = φ φ 5: ≡ 5 , ≡ 7 ≡ 8 , ≡ 4 , ≡2 , ≡ 1 . 1 1 : ≡1 ≡ 11, ≡ 7, ≡ 17, ≡ 7, ≡ 5 . So , 5 and 11 is a primitive root modulo 18 .