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 2n 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 = 02 + 02, 1 = 02 + 12, 2 = 12 + 12.]
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.