Putnam 1994

Problem B4

A is the 2 x 2 matrix (aij) with a11 = a22 = 3, a12 = 2, a21 = 4 and I is the 2 x 2 unit matrix. Show that the greatest common divisor of the entries of An - I tends to infinity.

Solution

It is a trivial induction that An has the form (cij), where c11 = r, c12 = s, c21 = 2s, c22 = r, with r an odd integer which tends to infinity with n (for example, r > 2n), and s an even integer. Hence the gcd of the entries of An - I is the gcd of r - 1 and s. Also det A = 1, hence det(An) = 1 and so r2 - 2s2 = 1, or (r - 1)(r + 1) = 2s2. It follows that the gcd of r - 1 and s is either √(r - 1) or √(2r - 2). [If p is an odd prime and h is the highest power of p that divides r - 1, then p does not divide r + 1, and so h must be even and h/2 the highest power of p dividing n. Both r - 1 and r + 1 are even, but one is not divisible by 4. If h is the highest power of 2 dividing the other, then h must be even and h/2 is the highest power of 2 dividing n.] But r - 1 tends to infinity with n, so the gcd does also.