# 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?

# 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.

# 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.

# 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.