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).
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.)
- Suppose we want to do a similar trick to test divisibility by 13. What do we do with the last digit in this case?
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.
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.
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).
- Compute the value of (p-2)! mod p as a function of p when p is prime. Hint: Cancel inverses.
- Compute the value of (m-2)! mod m as a function of m when m is composite.
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.
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.
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.
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
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.
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).