SOAR Homework Eight

These homework problems are meant to expand your understanding of what goes on during class. Any you turn in will be graded and returned to you. Answers may or may not be posted on the web, depending on demand.

Problems

1. An Expanded Chinese Remainder Theorem:   Given x in M_m and y in M_n where gcd(m,n)=1, there is a unique z in M_mn such that

   z	= x mod m
   z	= y mod n

   Prove this statement as follows:
   1. Prove that z = x n n^-1 + y m m^-1, where n^-1 is the inverse of n modulo m and m^-1 is the inverse of m modulo n, satisfies the equations.
   2. Suppose z₁ and z₂ are two possible solutions. Show that Z = z₁ - z₂ satisfies

      Z	= 0 mod m
      Z	= 0 mod n

   3. From part (b), show that Z must be divisible by mn, and hence Z = 0 mod mn. Show that this means that z₁ = z₂ mod mn, or that z₁ = z₂ as elements of M_mn.
   4. Can you state (and prove?) a general Chinese remainder theorem?
2. [See Homework 2, Problem 6] Recall that Z[sqrt(-5)] is the set of numbers a+bsqrt(-5), where a and b are integers.
   1. Show that Z[sqrt(-5)] is a group under addition. (That is, the set is Z[sqrt(-5)] and the operation is addition.)
   2. Is Z[sqrt(-5)] a group under multiplication? What if we require that one of a or b be non-zero? (Hint: find c+d sqrt(-5) so that (1+sqrt(-5))(c+d sqrt(-5)) = 1.)
3. [Hard] This problem is a sketch of a proof that (M_p, ×) is a cyclic group. (That is, there is an element g in M_p such that M_p is, as a set, simply {1, g, g², g³, ..., g^p-2}. Put another way, there is an element g in M_p with g^p-1 = 1 and g^k not equal to 1 for 0 < k < p-1.)
   1. Suppose m is an element of M_p. Let d be the smallest positive integer with m^d = 1. (This d is the order of the element m.) Show that d | (p-1).
   2. Since m^d=1, show that (m²)^d = 1, (m³)^d = 1, and so on up to (m^d-1)^d = 1.
   3. Show that part (b) allows us to factor x^d-1 into

      xd -1 = x (x-m) (x-m2) (x-m3) ... (x-md-1) mod p.

      (Hint: what are the roots of the equation on the left-hand side? On the right-hand side? You may assume that a polynomial of degree d has at most d roots.)
   4. Show that part (c) implies that if M_p contains an element of order d, then it contains exactly phi(d) of them. Let us write N_d for the number of elements of order d. This problem means that N_d = 0 or N_d = phi(d).
   5. Let d₁, d₂, ...,d_k be the divisors of p-1. Show that both

      Nd1 + Nd2 + ... + Ndk = p-1

      and

      phi(d1) + phi(d2) + ... + phi(dk) = p-1

   6. Conclude from part (e) that N_p-1 = phi(p-1). This means that there is an element of order p-1 in M_p, as desired.
4. A topic we won't go into too much depth with is the idea of a subgroup. This is a group within a group. The operation is inherited from the larger group, as is the identity (so the identity element must be in any subgroup). Consider the following examples:
   1. Show that the elements G = {0,2,4} of the group Z₆ = {0,1,2,3,4,5} form a subgroup. (That is, show that G is a group.)
   2. In fact, G in part (a) is isomorphic to Z₃ = {0,1,2}. That is, the elements and the multiplication table have the ``same form'' (the translation of ``iso'' and ``morph''). Show this by writing down the multiplication tables for both G and Z₃. (This shows that Z₃ is a subgroup of Z₆.)
   3. Show that C₄ = {1, r, r², r³   |   r⁴=1} is a subgroup of

      D4 = {1,r,r2, r3, m, mr, mr2, mr3   |   r4 = 1, m2 = 1, mr=r3m} .

   4. For what values of k is {1,mr^k} a subgroup of D₄?
   5. List all other subgroups of D₄ that you can find.

These problems are also available as a pdf file.

Solutions

Please email Peter if you are interested in answers or solutions for the web. Thanks.