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