# 1. Casting out sevens

Recall that we can test a number in base 10 written as d_{n}d_{n-1}...d_{1}d_{0} 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 d

_{n}d_{n-1}...d_{1}d_{0}is divisible by seven if and only if d_{n}d_{n-1}d_{1}- 2⋅d_{0}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?

## 1.1. Solution

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.

# 2. Factorials

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.

## 2.1. Solution

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 x_{1},x_{2}...,x_{n} is **relatively prime** if gcd(x_{1},x_{2}...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_{1},p_{2},...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_{1}...x_{n}). From g|x_{1} we have that every prime factor of g is a prime factor of x_{1}, i.e. that it must be one of p_{2}...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^{4} 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^{4} - (p-1)^{3} - (2p-1)^{2}. We can expand this to get p^{4} - p^{3} - p^{2} + p = (p^{2}-1)(p^{2}-p). This last expression follows from an alternative proof, where we count the number of nonzero vectors for the first row (p^{2}-1) and multiply by the number of vectors for the second row that are not multiples of the first row (p^{2}-p, since there are p multiples of the first row).