2007-04-11

1. * Reminder -- feel free to slow me down if necessary; do NOT be intimidated.
   * Reminder: homework is due monday

2. Defn: primitive root mod p -- an integer a that generates (Z/pZ)^*, 
   i.e. that has multiplicative order p-1.  (Define "generates"
   and "multiplicative order"). 

   Open Problem (Artin): There are infinitely many primes p such
   that 2 is a primitive root modulo p. 
   
   E.g., 2 is a primitive root modulo p for 

     p = 3 5 11 13 19 29 37 53 59 61 67 83 101 107 131 139 149 163 173 179 181 197 211 227 269 293 317 347 349 373 379 389 419 421 443 461 467 491 509 523 541 547 557 563 587 613 619 653 659 661 677 701 709 757 773 787 797 821 827 829 853 859 877 883 907 941 947 ...

   A major open problem that has stumped everybody for over 50 years
   is to prove that this list is infinite. 

3. Theorem 1. For every prime p, there is a primitive root modulo p.

4. Prop: A polynomial f(x) in k[x], for k a field, has at most deg(f) roots.
GIVE examples when not in a field.

5. Prop: For any divisor d of p-1, the poly x^d - 1 has exactly d roots.

6. Lemma: If a, b in (Z/pZ)^* have coprime multiplicative orders n,m , then
   the order of c = a*b is n*m.

7. Proof of Theorem 1. 
   A counting argument at each prime power divisor of p-1 combined 
   with multiplying.

8. Example: p = 13. Do as in notes!

9. Other facts:
   Theorem 2. Primitive roots exist modulo p^n for any odd prime p,
   (but not moduo 2^n for n >= 2).

   Also, the number of primitive roots is phi(phi(n)).