If this exam is like most of the others I've made up in my career, it's probably too long. I get carried away thinking of interesting questions. So do as much as you can in the allotted time. Turn in your paper. Then take the exam home and do it again as homework for Tuesday.

1. Let L be the set of all k letter strings you can make with an n letter alphabet A.

   Reminder: in strings order matters and repetitions are allowed.

   1. What is the cardinality of L?

   2. How many of the strings in L have no double letters? (A string has double letters if some letter appears in two adjacent positions. "bookkeeper" has three such pairs. "radar" has none, even though it has two a's and two r's.)

   3. How many of the strings in L have exactly one pair of double letters?

2. What is the remainder when you divide 10¹⁰⁰ (a googol) by 101? When you divide it by 97?

3. What are the coefficients of x⁹⁰ and x⁹¹ in the expansion of (x² - 2/x)⁵⁰?

4. A binary relation R on a set S is antisymmetric if xRy and yRx imply x=y. R is total if for every x != y in S either xRy or yRx. For example, the relation "less than" for integers is antisymmetric and total. So is "less than or equal to".

   1. Prove or disprove: if R is antisymmetric then it is total.

   2. Prove or disprove: if R is total then it is antisymmetric.

   3. Prove or disprove: if R is antisymmetric then it is not an equivalence relation.

   4. Prove or disprove: if R is total then it is not an equivalence relation.

   5. Suppose S has n elements. Count the number of binary relations on S that are both antisymmetric and total.

5. Let N = 3*5*7*11*13* ... *523*541*547 be the product of the first hundred odd primes. Count the positive integral solutions to the equation

   	N = x2 - y2 .
   

   Hint: Remember that

   	x2 - y2 = (x-y)*(x+y).
   

   Then count how many ways are there to write N as a product of two factors.

   Note. The Prime Number Theorem says (in one form) that the n^th prime is about n*ln(n). The approximation isn't very good for small numbers: the 101^st prime is 547, while 101 * ln(101) = 466.127172.

6. I know you won't have time for this one on the exam. Try it at home over the weekend.

   Here's a theorem we haven't proved (yet). Use it in what follows.

   	If p is prime and a !== 0 (mod p) then a has either no square
   	roots (mod p) or exactly two.
   

   Note: html isn't kind to mathematics. I'll write == for the congruence symbol, and !== to negate a congruence.

   For example, modulo 7,

   	1 == 12 == 62 (mod 7)
   	2 == 32 == 42 (mod 7)
   	4 == 22 == 52 (mod 7)
   

   so 1, 2 and 4 each have two square roots mod 7, while the equations

   	3 == x2 (mod 7)
   	5 == x2 (mod 7)
   	6 == x2 (mod 7)
   

   have no solutions, so 3, 5 and 6 have no square roots.

   1. Show that the theorem is false if you omit the hypothesis "p is prime".

   2. Prove

      	Suppose p is prime and a !== 0 (mod p).
      	Then a(p-1)/2 == +-1 (mod p).
      

   3. Prove

      	Suppose p is prime and a !== 0 (mod p).
      	If a has a square root mod p
      	then a(p-1)/2 == 1 (mod p).
      

   4. State the converse of the theorem in the previous part of this problem.

   5. Optional, extra credit, to try at home: prove the converse you stated in the previous part of this problem.

   6. Optional, extra credit, to try at home: prove the theorem stated at the start of this problem.