September 18, 2007

A Few More Number Theory Problems

Two more “introductory” problems from “104 Number Theory Problems:”

1. Let x, y, z be positive integers such that

1/x – 1/y = 1/z.

Let h be the greatest common divisor of x, y, z. Prove that hxyz and h(y – z)

are perfect squares.

2. Prove that any number consisting of 2ⁿ identical digits has at least n distinct prime factors.

Three actual Putnam problems:

3. (2000 Putnam, A-2) Prove that there exist infinitely many integers n such that n,  n+1,  n+2 are each the sum of the squares of two integers. [Example: 0 = 0² + 0², 1 = 0² + 1², 2 = 1² + 1².]

4. (1999 Putnam, B-6) Let S be a finite set of integers, each greater than 1. Suppose that for each integer n there is some s Î S such that gcd(s, n) = 1 or gcd(s, n) = s. Show that there exist s, t Î S such that gcd(s, t) is prime.

(not number theory, but a good game problem…)

5. (1995 Putnam, B-5) A game starts with four heaps of beans, containing 3, 4, 5, and 6 beans. The two players move alternately. A move consists of taking EITHER

(a) one bean from a heap, provided that at least two beans are left behind in that heap, OR

(b) a complete heap of 2 or 3 beans.

The player who takes the last heap wins. To win the game, do you want to move first or second? Give a winning strategy.

(end)