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?

      Answer.

      There are n^k strings of length k on an n letter alphabet. I probably said that n times in class.

   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.)

      Answer.

      The first letter can be any of the n. After that there are just n-1 choices for each letter, so the number of strings is n(n-1)^k-1.

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

      Answer.

      There are n(n-1)^k-2 strings of length k-1 with no double letters. For each such string you can choose one of the k-1 letters to double up. So there are n(n-1)^k-2(k-1) strings of length k with exactly one double letter.

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

   Answer.

   Since 101 is prime, Fermat's little theorem says 10¹⁰⁰ == 1 (mod 101).

   Since 97 is prime, Fermat's little theorem says 10⁹⁶ == 1 (mod 97). Then

     10100 == 1096104 == 1002 == (-3)2 == 9 (mod 97)
   

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

   Answer.

   
    (x2 - 2/x)50
      = (x2)50 -50(x2)49(2/x) + ...
      = x100 - 50*2x97 + (50*49/2)22x94 - (50*49*48/6)*23x97+
   

   so the coefficient of x⁹⁰ is 0 and the coefficient of x⁹¹ is -156800.

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.

      Answer.

      This is false. The relation = on a two element set is antisymmtric but not total.

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

      Answer.

      This is false. The relation consisting of all ordered pairs from a two element set is total but not antisymmetric.

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

      Answer.

      This is false. The equivalence relation = on a two element set is antisymmtric.

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

      Answer.

      This is false. This is false. The equivalence relation consisting of all ordered pairs from a two element set is total.

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

      Answer.

      This was very hard. Only Avram got it; no one else came close. There are n(n-1)/2 pairs of distinct elements of S. Totality requires that for each x != y, at least one of (x,y) or (y,x) be in R. Antisymmetry requires that just one of them is in R. So there are 2^n(n-1)/2 choices so far. Then each of the n pairs (x,x) may be in R, or not, without affecting either totality or antisymmetry. So altogether there are 2^n(n-1)/2*2ⁿ relations 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.

   Answer.

   There are 2¹⁰⁰ subsets of the set of 100 primes. Each way to write N as a product of two factors corresponds to choosing one of these subsets and its complement. So there are 2⁹⁹ ways to do the job.

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".

      Answer.

      The square of every odd number is 1 (mod 8), so 1 has the four square roots 1, 3, 5 and 7 (mod 8).

   2. Prove

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

      Answer.

      Fermat's little theorem says

      	(a(p-1)/2)2 == ap-1 ===+-1 (mod p)
      

      so a(p-1)/2 is a square root of 1. Since p is prime, it has only two square roots, and those are +-1, so a(p-1)/2 must equal one of them.

   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).
      

      Answer.

      If a has a square root then a == b² (mod p) for some b. Then Fermat's little theorem says a^(p-1)/2 == b^p-1 == 1 (mod p).

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

      Answer.

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

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

      Answer.

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

      Answer.