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

1.1. Solution

Basically, we are solving two equations in two unknowns, and the only twist is that we are doing it in ℤ₃₁ instead of ℚ.

Let's start by using the first equation to get an expression for d in terms of m and x:

• d = 25^-1(x-19m).

Plugging this into the second equation gives:

• y = 9m + 4⋅25^-1(x-19m).

This would be easier to solve if we knew what 25^-1 was in ℤ₃₁.

Using the extended Euclidean algorithm, we want to find n₁ and m₁ such that 31n₁ + 25m₁ = 1.

Write 31 = 1⋅25 + 6 to reduce to the problem of finding n₂ and m₂ such that 25n₂ + 6m₂ = 1. Here since 25 = 4⋅6 + 1, we easily get 25⋅1 + 6⋅(-4) = 1, giving n₂ = 1 and m₂ = -4.

Working backwards, we have 6 = (31-25) so 1 = 25 - 4⋅6 = 25 - 4⋅(31-25) = 5⋅25 - 4⋅31. So 25^-1 = 5 (mod 31).

Note: If we don't want to go through the extended Euclidean algorithm, there are other alternatives: one is to just guess the correct answer (possibly by trying out cases until we find one that works, or by Googling "inverse of 25 mod 31"), and verify that it is correct by multiplying 5⋅25 = 125 = 31⋅4 + 1. This is perfectly acceptable in a proof, although it may not work if the modulus is much larger. Another is to use Euler's theorem and calculate 25^-1 = 25^30-1 = 25²⁹ = 34694469519536141888238489627838134765625 = 5 (mod 31). This requires either having a calculator that can handle really big numbers, or using something like the Russian Peasant's Algorithm to calculate the exponent mod 31 a piece at a time. Either approach is likely to be more computationally expensive than the extended Euclidean algorithm, and in general we won't expect the Euler's theorem approach to work when m is a large composite number, since we can't compute the totient of m (and thus figure out what exponent we need) unless we can factor m.

However we found 25^-1, we can now put it back in our y formula:

• y = 9m + 4⋅5(x-19m).

Rearrange to put m by itself:

• 371m = 20x - y.

Knock down the 371 by taking it mod 31:

• 30m = 20x - y.

Now we need to know what 30^-1 is in ℤ₃₁. The easy way to do this is to notice that 30 = -1, so 30^-1 = (-1)^-1 = -1. Multiplying both sides by -1 then gives

• m = -20x + y.

Since 11 = -20 (mod 31), we can make this a little cleaner by rewriting it as

• m = 11x + y.

Our formula for d (with 25^-1 replaced by 5) says

• d = 5(x-19m) = 5(x - 19(11x + y)) = -1040x - 95y = 14x - 2y.

Summarizing, we have

(with everything taken mod 31). As a quick check, if we use our example of x = 3, y = 5, we get m = 33+5 = 38 = 7 (mod 31) and d = 42-10 = 32 = 1 (mod 31), which is what we started with.

2. A strange equivalence

Given x and y in ℕ, let x ≡ y if there exist k and l in ℕ such that 2^kx = 2^ly.

1. Show that ≡ is an equivalence relation.
2. Prove or disprove: If x ≡ x' and y ≡ y', then xy ≡ x'y'.
3. Prove or disprove: If x ≡ x' and y ≡ y', then x+y ≡ x'+y'.

2.1. Solution

1. Reflexive: let 2^k = 2^l = 2⁰ = 1; then 2^kx = x = 2^lx. Symmetric: If 2^kx = 2^ly, then 2^ly = 2^kx. Transitive: Let 2^kx = 2^ly and 2^my = 2ⁿz. Suppose that m ≥ l. Then 2^k+m-lx = 2^my = 2ⁿz. Alternatively, if m < l, then 2^n+l-mz = 2^m+l-my = 2^ly = 2^kx. (Extra sneaky transitivity proof: 2^k+mx = 2^m2^kx = 2^m2^ly = 2^l2^my = 2^l2ⁿz = 2^l+nz. This avoids the case analysis.)

2. Proof: Let 2^kx = 2^k'x' and 2^ly = 2^l'y'. Then 2^k+k'x = 2^l+l'y'.

3. Disproof: 1 ≡ 2, and 1 ≡ 4, but it is not the case that 2 ≡ 6.

3. Factorials

The factorial of n, written n!, is equal to the product of the natural numbers from 1 to n. Formally, n! = .

1. Prove that n! + k is composite for any 1 < k ≤ n.

2. Give a counterexample that shows that n! + k might not be composite if k = 1, even if k < n.

3.1. Solution

1. If k ≤ n, then k is a factor of n! (since it's included in the big product). So we have k|n! and k|k, implying k|(n!+k). Now observe that (a) k ≠ 1; (b) since n ≥ k > 1, n! ≥ 2! = 2, implying n! + k ≥ k+2 and in particular n! + k ≠ k. Thus n! + k has a factor that is neither equal to itself or 1, so it's composite.

2. The smallest possibly counterexample works: 2! + 1 = 3 is prime. The next counterexample is 3! + 1 = 7. After that the counterexamples start getting pretty thin. The next smallest one is 11! + 1 = 39916801, which happens to be prime, but not obviously so.