[FrontPage] [TitleIndex] [WordIndex

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

1. Casting out sevens

Recall that we can test a number in base 10 written as dndn-1...d1d0 for divisibility by 9 by adding up all the digits and seeing if the sum is divisible by 9. For divisibility by 7, we can use a different test: double the last digit and subtract it from the remaining digits. For example, starting with 154 we compute 15-2⋅4=15-8=7; since the result is divisible by 7, we conclude that so is 154. If instead we started with 193 we'd compute 19-2⋅3 = 13, which is not divisible by 7 (just as 193 is not divisible by 7).

  1. Prove that this works, i.e. prove that dndn-1...d1d0 is divisible by seven if and only if dndn-1d1 - 2⋅d0 is. (It may help to think of the original number as 10x+y, where y is the last digit.)

  2. Suppose we want to do a similar trick to test divisibility by 13. What do we do with the last digit in this case?

1.1. Solution

  1. Write n = 10x+y. Working in ℤ7, we have n=10x+y=3x+y. We want to show that this quantity equals 0 iff x-2y does. Suppose x-2y=0; then multiply both sides by 3 to get 3x-6y=3x+y=0. Conversely, if 3x+y=0, then we can multiply both sides by -2 to get -6x-2y=x-2y=0.

  2. Again let n = 10x+y. We want to choose c so that in ℤ13, x+cy=0 iff 10x+y=0. We can get the right x coefficient in the second equation by multiplying both sides of the first one by 10; this gives 10x+10cy=0, and we win if 10c=1 (mod 13). After some trial and error we notice that c=4 works. (To see that the converse works, we can observe that multiplying 10x+y by 4 gives 40x+4y = x+4y (mod 13), or we can just argue that multiplication is invertible in ℤ13.)

Note that subtracting 9 times the last digit also works, since -9 = 4 (mod 13).

A quick test: 13²=169 → 16+4⋅9 = 16+36 = 52 → 5+4⋅2 = 13, so 169 is divisible by 13. A slower test: 986⋅13 = 12818 → 1281+4⋅8 = 1313 (which looks awfully divisible by 13) → 131+12 = 143 → 14+12 = 26, and now we just have to recognize 26=2⋅13 because further application of the rule leaves us at 26.

2. Factorials

  1. Let x² = 1 (mod p), where p is prime and 0≤x<p. Show that x = ±1 (mod p). Hint: Use the fact that p|(x²-1).

  2. Compute the value of (p-2)! mod p as a function of p when p is prime. Hint: Cancel inverses.
  3. Compute the value of (m-2)! mod m as a function of m when m is composite.

2.1. Solution

  1. We will consider only x in the range 0≤x<p. If x² = 1 (mod p), then x²-1 = 0 (mod p), or in other words p|(x²-1). But x²-1 = (x-1)(x+1), so p|(x+1) or p|(x-1). Let's suppose p|(x+1); then x≥p-1, but x<p, so x=p-1. Alternatively, if p|(x-1), we have x-1=0 or x-1≥p. Only the x-1=0 case is permitted by the bounds on x, giving x=1.

  2. Recall that every x with 1<x<p has a multiplicative inverse mod p, with the property that xx-1 = 1 (mod p). From the preceding, the only x with 0≤x<p which are their own inverses mod p are 1 and p-1. So for every x in the range 2≤x≤p-2, there is some x-1≠x such that xx-1 = 1 (mod p). But this x-1 must also appear [2,p-2], so when we compute (p-2)!, each x>1 is canceled by its inverse. The only term left is 1. It follows that (p-2)! mod p = 1.

  3. Since m is composite, we have m = ab for some a,b > 1. If a and b are distinct and both are less than or equal to m-2, then ab|(m-2)! implies (m-2)! = 0 (mod m). We can drop the condition that a,b≤m-2, since if b≥(m-1) (say) we have m = ab ≥ 2(m-1) ≥ 2m-2 ⇒ 2 ≥ m, and there are no composite number less than or equal to 2. But we still have to consider the case where a=b, i.e. where m=a² for some a. Now we don't see a twice in (m-2)!, but we may see both a and 2a if 2a ≤ m-2 = a²-2. We can rewrite 2a ≤ a²-2 as 2a+2 ≤ a² or 2+2/a ≤ a; this clearly holds for a≥3, implying that if m=a² for a≥3, we again have (m-2)! mod m = 0. We still have the case where m=a² for a = 2. Here we calculate: (4-2)! = 2! = 2 mod 4 = 2. So we have that (m-2)! mod m = 0 for all composite m except 4, for which it is 2.

3. Relative primes

A set of numbers x1,x2...,xn is relatively prime if gcd(x1,x2...xn) = 1. Show that for any n > 2, there exists a set of n distinct numbers that are relatively prime, but for which gcd(xi,xj) > 1 for all i, j.

3.1. Solution

Let p1,p2,...pn be n distinct primes. For each i, let xi = Πj≠i pj. Then for each pair xi, xj, there is some k equal to neither i nor j such that pk divides both xi and xj, implying gcd(xi,xj) ≠ 1. Now consider g = gcd(x1...xn). From g|x1 we have that every prime factor of g is a prime factor of x1, i.e. that it must be one of p2...pn. But for each pi, if pi|g, then pi|xi, a contradiction. It follows that g has no prime factors, i.e. that g=1.

4. Invertible matrices in ℤp

The inverse of a 2×2 matrix with entries in any field (e.g. ℝ, ℂ, ℚ, ℤp) is given by the formula

d & -b \\
-c & a

and an inverse exists if and only if ad-bc ≠ 0.

Use this fact to count the number of distinct invertible 2×2 matrices with entries in ℤp, where p is prime.

4.1. Solution

We need to count the number of 4-tuples (a,b,c,d) of elements of ℤp for which ad-bc ≠ 0. It may be slightly easier to first count all 4-tuples of elements of ℤp (there are p4 exactly), and then subtract out those for which ad-bc=0, or equivalently for which ad=bc. This is not too hard, except that we have to be a little bit careful with handling zeros.

Case 1: ad=bc=0
On the left-hand side, we can make a=0 and d arbitrary (p choices) or make a≠0 and d=0 (p-1 choices); we thus have 2p-1 choices for a and d. The same applies to b and c on the right-hand side, giving (2p-1)² choices total.
Case 2: ad=bc≠0

Here we can choose a, d, and b arbitrarily (as long as none are 0), but then c = adb-1 is determined. This gives (p-1)³ choices.

So the total number is p4 - (p-1)3 - (2p-1)2. We can expand this to get p4 - p3 - p2 + p = (p2-1)(p2-p). This last expression follows from an alternative proof, where we count the number of nonzero vectors for the first row (p2-1) and multiply by the number of vectors for the second row that are not multiples of the first row (p2-p, since there are p multiples of the first row).

2014-06-17 11:57