ENT: 2007-04-06

1. Reminder: get going on your project!

2. Define (Z/nZ)^*.

3. Define phi(n) and prove that x^(phi(n)) = 1 (mod n) for each x in
   (Z/nZ)^*.  Prove this by proving that multiplication by x defines a
   permutation.  
   NOTE: This proves that every x in (Z/nZ)^* has a multiplicative inverse.
  
4. Define multiplicative order.

5. CRT: 
   Thm: if gcd(n,m)=1 and a,b in Z then x=a(mod m), y=b(mod n) has a 
   solution that is unique modulo n*m.
   Proof. 
    Existence:
     Consider a + tm = b (mod n).  If can solve for t, then 
     x = a+tm will work.  We have tm = b-a (mod n).  But gcd(m,n) = 1,
     so m has an inverse, say k, so t = t*m*k = (b-a)*k (mod n), solves.
    Uniqueness mod m*n:
     If x and y both work, then z = x-y solves z=0 (mod m) and z=0(mod n),
     so z = 0(mod m*n), so done.

6. In SAGE, do CRT by using CRT(a,b,m,n).

7. Prove Phi is multiplicative, i.e., that 
       (Z/mnZ)^* ---> (Z/mZ)^* x (Z/nZ)^*
   is a bijection.  
   Proof.  The above map is a group homomorphism.
   The existence part of the CRT theorem implies
   it is surjective, and the uniquess part implies it
   is injective.
   USEFUL -- compute phi by factoring and noting that
   for p prime, we have phi(p) = p-1. 

8. "Pop Quiz":
   1. What did you learn today that is clear?
   2. What was murky in the lecture?
   3. What do you want me to change about the class so that 
      you would be more likely to give perfect scores on the
      student evaluations at the end of the quarter?