1. A secret code
The IT manager at the First Bank of Insecurity wants to use customer birthdays to verify people calling its customer service desk, where we take a customer birthday as consisting of a month m in the range (1..12) and a day d in the range (1..31). But upper management insists that the bank can't violate its customers' privacy by storing the actual dates. So the IT manager suggests storing instead a pair (x,y) where
- x = 19m+25d (mod 31)
and
- y = 9m+4d (mod 31).
For example, if a customer's birthday is (7,1), the encoded value would be (3,5). When a customer calls up, a highly trained customer service representative can compute this encoding based on the customer's actual birthday and compare it with the bank's records. But in the other direction (the IT manager reasons), it would take an expensive brute-force search of all 366 possible birthdays to figure out what the actual birthday was given just x and y.
Show that this system does not in fact provide much security, by giving a simple formula for computing m and d given x and y. (Since you are working mod 31, it's OK if your formula returns 0 for d when the actual value is 31.)
2. A strange equivalence
Given x and y in ℕ, let x ≡ y if there exist k and l in ℕ such that 2kx = 2ly.
- Show that ≡ is an equivalence relation.
- Prove or disprove: If x ≡ x' and y ≡ y', then xy ≡ x'y'.
- Prove or disprove: If x ≡ x' and y ≡ y', then x+y ≡ x'+y'.
3. Factorials
The factorial of n, written n!, is equal to the product of the natural numbers from 1 to n. Formally, n! = 
.
Prove that n! + k is composite for any 1 < k ≤ n.
Give a counterexample that shows that n! + k might not be composite if k = 1, even if k < n.