1. Casting out sevens

Recall that we can test a number in base 10 written as d_nd_n-1...d₁d₀ 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 d_nd_n-1...d₁d₀ is divisible by seven if and only if d_nd_n-1d₁ - 2⋅d₀ 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 ℤ₇, 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 ℤ₁₃, 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 ℤ₁₃.)

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 x₁,x₂...,x_n is relatively prime if gcd(x₁,x₂...x_n) = 1. Show that for any n > 2, there exists a set of n distinct numbers that are relatively prime, but for which gcd(x_i,x_j) > 1 for all i, j.

3.1. Solution

Let p₁,p₂,...p_n be n distinct primes. For each i, let x_i = Π_j≠i p_j. Then for each pair x_i, x_j, there is some k equal to neither i nor j such that p_k divides both x_i and x_j, implying gcd(x_i,x_j) ≠ 1. Now consider g = gcd(x₁...x_n). From g|x₁ we have that every prime factor of g is a prime factor of x₁, i.e. that it must be one of p₂...p_n. But for each p_i, if p_i|g, then p_i|x_i, 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.

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 p⁴ 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 p⁴ - (p-1)³ - (2p-1)². We can expand this to get p⁴ - p³ - p² + p = (p²-1)(p²-p). This last expression follows from an alternative proof, where we count the number of nonzero vectors for the first row (p²-1) and multiply by the number of vectors for the second row that are not multiples of the first row (p²-p, since there are p multiples of the first row).