/Solutions

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?

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.

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.

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.