Math 310: Problem set 11

Instructions: This problem set is due Friday, April 7, 2006. Explain each of your steps. However, you may use results from the web sites and, if you find them useful for doing calculations. (Note that the Bezout web form allows you to input values for a and b. Its output is the solution ma + nb = gcd(a,b). Thus it gives a solution x=m to ax = gcd(a,b) mod b. When a and b are relatively prime, it thus gives you a solution x=m to ax = 1 mod b.)

  1. State what the mathematical notion of a combination of n things taken r at a time is (look it up on the web, for example). Give a reference (such as a URL) for your answer.
  2. State what binomial coefficients are, what notation is used to denote them, and how they are related to the mathematical notion of combinations. Give a reference for your answer.
  3. State the binomial theorem. Give a reference for your answer.
  4. Note that 97 is prime and congruent to 1 mod 4. Demonstrate Fermat's Christmas Theorem by writing 97 as the sum 97 = m2 + n2 of the squares of two integers m and n.
  5. Use your answer to the previous problem to solve x2 = -1 (mod 97). Give the least positive residue modulo 97 for each solution.

    The other day the question came up of how to solve quadratic equations modulo numbers other than primes. We'll explore that a bit now.

  6. Let p and q be positive integers, and let c and m be integers. If x=c is a solution to x2 = m (mod pq), show that x=c is also a solution to both x2 = m (mod p) and to x2 = m (mod q).
  7. Now let p and q be distinct (i.e., different) primes and let c, d, m and n be integers such that c2 = m (mod p) and d2 = m (mod q). Assume x=n is a simultaneous solution to
    x = c (mod p) 
    x = d (mod q) 
    Show that n is a solution to x2 = m (mod pq). [Hint: Use the given congruences to show p and q both divide n2 - m. Then justify why that means that pq divides n2 - m.]

    For these last two problems, use the ideas of the preceding two problems to find all least positive residues which are solutions, or to show that there are no solutions.

  8. x2 = -1 (mod 35)
  9. x2 = 23 (mod 77)