MA 341 B1 - Spring 2005
Number Theory

Homework #9 -- Selected Solutions

Numerical exploration
  1. For which primes p less than 40 is 2 a square modulo p? Any conjectures?
    You should observe that for p odd, 2 is a square modulo p if and only if p=1 or 7 (mod 8).
  2. Compute the value of (p-1)! (mod p) for p=2,3,5,7,11,13 and 17. (Remember that you should not be working with large numbers!) Any observations? (There should be a definite pattern here...if not, you've made some computation error.)
    You should observe that (p-1)! = -1 (mod p).
  3. Compute 34953495178945739845757 mod 25.
    Since φ(25)=20, we know that u20=1 (mod 25) as long as u is not a multiple of 5. (See the question #5.) Since 945739845757 = 17 (mod 20), we have
    34953495178945739845757 = 3945739845757 = 317 (mod 25).
    To compute 317, note that by squaring we have, 32=9, 34=11, 38=21, 316=21 and thus 317=13 (all modulo 25).

    The final answer is thus 13.

Prove or disprove and salvage if possible
(Make sure that you prove your salvage!)
  1. For a in Zm, aφ(m)=1 (mod m).
    We proceed just as we did in class in the case when m was a prime. Namely, in Zm there are φ(m) units; call them u1,u2,...,uφ(m). Then the set {a*u1,a*u2,...,a*uφ(m)} is just the set of units mod m rearranged. (To see this, if a*ui=a*uj for some i and j, multiplying both sides of this equation by the inverse of a yields that ui=uj.) Thus,
    u1*u2*...*uφ(m)= a*u1*a*u2,...*a*uφ(m)= aφ(m)*u1*u2*...*uφ(m).
    Since the product of units is again a unit (HW 6 #5), we can cancel u1*u2*...*uφ(m) from both sides of the equation. This yields aφ(m)=1 (mod m) and proves the theorem.
  2. The division algorithm holds in Z[&radic-2]. That is, given α,β in Z[√-2], there exists q,r in Z[√-2] such that α=βq+r and N(r) < N(β).
    (Remember that N(a+b√-2)=a2+2b2.)
    We can repeat the same geometric argument as in class. In this case, the lattice generatd by β has each fundamental unit being a rectangle. The square of the lengths of the two side lengths of any such rectangle are N(β) and 2N(β). Using the Pythagorean theorem, we then have that the length from the midpoint of rectangle to a corner is 3/4 N(β). As in class, this suffices to prove the division algorithm.
  3. Let p be a prime number in Z. Then p is composite in Z[i] if and only if p=x2+y2 for some x and y in Z.
    For (⇐) if p=x2+y2 then p =(x+iy)(x-iy) and p is composite.
    For (⇒) if p=αβ with α,β non-units, then N(α)N(β)=N(p)=p2. Since p is a prime, N(α)=N(β)=p. (Note that neither of these norms could equal 1.) If α=x+yi, then p=x2+y2.
  4. Let n be in Z and let ar ar-1... a1 a0 be the base 10 representation of the number n.
    If a_0 + a_1 + ... + a_r is a multiple of three, then n is a multiple of 3.
    If a_0 + a_1 + ... + a_r is a multiple of nine, then n is a multiple of 9.
    Can you devise a simple rule for being a multiple of 11?
    By definition of base 10, we have an equation:
    n = ar10r + ar-110r-1 + ... + a1101+a0.
    Reducing this equation mod 3 yields
    n = ar1r + ar-11r-1 + ... + a111+a0 = ar + ar-1 + a1 + a0 (mod 3)
    since 10 = 1 (mod 3). Thus n is congruent to zero mod 3 if and only if the sum of its base 10 digits is congruent to zero mod 3. Since being a multiple of 3 is the same as being congruent to zero mod 3, this completes the question.

    Since 10 = 1 (mod 9), the above argument works the same mod 9.

    For 11, note that

    n = ar(-1)r + ar-1(-1)r-1 + ... + a1(-1)1+a0 (mod 11)
    since 10 = -1 (mod 11). Thus, n is a multiple of 11 if and only if the alternating sum of its digits is a multiple of 11.
  5. Prove your observations from question #2.
    The observation is that (p-1)! = -1 (mod p)

    To see that this is true, we will pair up each term of the product with its multiplicative inverse. Note that 1 and -1 are there own multiplicative inverses. For every other number, that number and its multiplicative inverse are distinct. (I've proven this below as a lemma.) Accepting this fact as true, we then have that all the terms in (p-1)! cancel out except for 1 and -1. Thus

    (p-1)! = 1*(-1) = -1 (mod p).
    Lemma: For p a prime, if x and x-1 are equal in Zp then x=1 or -1 (mod p).

    Proof: x = x-1 (mod p) &rArr x2=1 (mod p) &rArr p | x2-1 &rArr p | (x-1)(x+1)
    &rArr p | x-1 or p | x+1 (Euclid's lemma) &rArr x = 1 (mod p) or x = -1 (mod p)

    (Note that this lemma is not true is p weren't prime!)