Elementary Number TheoryCam McLemanOctober 26, 2006One of number theory’s claims to fame is the unusual ease with which one canpose exceedingly difficult problems, and the enormity of the full toolkit neededto tackle all of these problems. Fortunately, the good news is that solvinga Putnam problem is rarely about having memorized the applicable theorem.Instead, there are a select few elementary results/topics that can cover a widerange of possible questions:• Modular arithmetic.• Euler’s theorem (in particular Fermat’s Little Theorem).• Prime factorization, gcd’s, and divisibility.Example 1. Show that the sequence11, 111, 1111, 11111, · · ·contains no perfect squares.Example 2. Prove that the fraction21n + 414n + 3is irreducible for every p ositive integer n.Example 3. What are the last two digits of 332006?Example 4. Suppose that the number of prime divisors of a p ositive integer nis a prime number p which does not divide n. Show that n is one more than amultiple of p.Problem 1. If 2n+1 and 3n+1 are both perfect squares, show that n is divisibleby 40.Problem 2. How many trailing zeros are at the end of the decimal expansion of15072?Problem 3. Find all positive integers d such that d divides both n2+ 1 and(n + 1)2+ 1 for some n.Problem 4. For any prime p, prove that every prime divisor of 2p− 1 is at leastp.1Problem 5. Prove that for any integers m and n, the quantitygcd(m, n)nnmis an integer.Problem 6. Let pkdenote the k-th prime number. Show thatpk< 22k.Problem 7. Prove that for any integer k, the number n = 9k· 2006 + 1 cannotbe expressed in the formn = x2+ y2+ z2for any integers x, y, and z.Problem 8. Count the number of pairs of positive integers (x, y) such that1x+1y=12006.Problem 9. Find the sum of the digits of the sum of the digits of the sum of thedigits of 20062005.Problem 10. Show that for any prime p, the number 2p+ 3pis never a perfectpower (greater than 1) of an integer.Problem 11. Show there are no non-trivial (i.e. other than (x, y, z) = (0, 0, 0))integer solutions to the equationx3+ 3y3+ 9z3− 9xyz = 0.Problem 12. For a given positive integer m, find all triples (n, x, y) of positiveintegers with m and n relatively prime, which satisfy the relation(x2+ y2)m=