Number Theory Problems – Handout
Find all prime numbers p and q such that p2 − pq + q 2 − 7 is a prime
number.
Problem 1:
Prove the expression gcd(m, n)nm is an integer for all pairs of integers
n ≥ m ≥ 1. [Putnam 2000]
Problem 2:
What is the largest positive integer n for which n3 + 100 is divisible by
n + 10? [AIME 1986 P5]
Problem 3:
√
Show that any composite number n has a prime factor ≤ n.
Problem 4:
21n+4
Prove that for any natural number n, the fraction 14n+3
is in lowest
terms. [IMO 1959 P1]
Problem 5:
Let 1, 4, . . . and 9, 16, . . . be two arithmetic progressions. The set S is
the union of the first 2004 terms of each sequence. How many distinct
numbers are in S? [AMC 10B P21]
Problem 6:
Compute
(104 + 324)(224 + 324)(344 + 324)(464 + 324)(584 + 324)
.
(44 + 324)(164 + 324)(284 + 324)(404 + 324)(524 + 324)
[AIME 1987 P14]
Problem 7:
The integer n is the smallest positive multiple of 15 such that every digit
of n is either 8 or 0. Compute n/15. [AIME 1984 P2]
Problem 8:
Let n > 2 be an integer. Prove that among the fractions n1 , n2 , . . . , n−1
n
,
an even number of them are irreducible.
Problem 9:
1
Positive integers are written on all the faces of a cube, one on each. At
each vertex, the product of numbers on meeting faces is written. The
sum of all corner numbers is 2004. If T denotes the sum of numbers on
all faces, find all possible values of T . [RMO 2004]
Problem 10:
Solve the equation y 3 = x3 + 8x2 − 6x + 8 for positive integers x and y.
[RMO 2000]
Problem 11:
Let S be the set of all possible remainders when a number of the form
2n , n ≥ 0, is divided by 1000. Let T be the sum of elements in S. Find
the remainder when T is divided by 1000. [AIME 2011 P11]
Problem 12:
For positive integers n and k, let f (n, k) be the remainder when n is
divided by k, and let F (n) = max1≤k≤n/2 f (n, k). Find the remainder
when 100
P
n=20 F (n) is divided by 1000. [AIME 2013 P14]
Problem 13:
Let n ≥ 2 be a positive integer with divisors 1 = d1 < d2 < . . . < dk = n.
Prove that d1 d2 +d2 d3 +. . .+dk−1 dk is always less than n2 and determine
when it is a divisor of n2 . [IMO 2002 P4]
Problem 14:
Determine all non-negative integral solutions, if any (apart from permu-
tations), of n41 + n42 + . . . + n414 = 1599. [USAMO 1979 P1]
Problem 15:
Determine all integral solutions of a2 + b2 + c2 = a2 b2 . [USAMO 1976
P3]
Problem 16:
Find all tuples of positive integers (a, b, c) such that lcm(a, b, c) =
ab+bc+ca
4
. [Japan 2020 Junior Finals P3]
Problem 17:
Let a, b be distinct naturals such that ab(a+b) is divisible by a2 +ab+b2 .
Show that |a − b| > (ab)1/3 . [Russia Grade 11 2/20]
Problem 18:
2
Let m, n be distinct positive integers. Prove that
gcd(m, n) + gcd(m + 1, n + 1) + gcd(m + 2, n + 2) ≤ 2|m − n| + 1
and determine when equality holds. [INMO 2019]
Problem 19:
Let a > b > c > d be positive integers and suppose ac + bd = (b + d +
a − c)(b + d − a + c). Prove that ab + cd is not prime.
Problem 20: