[FrontPage] [TitleIndex] [WordIndex

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.


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

  1. 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.)

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

d & -b \\
-c & a

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.

2014-06-17 11:57