Number Theory

Rohan Goyal
June 11, 2021

Please do not share this file publicly.

§1 Problems
§1.1 Size Ideas:
Shared previously(I’ll still add a few)

§1.2 Prime Exponents:

Problem 1.1 (Serbia 2021). Let a > 1 and c be natural numbers and let b 6= 0 be an
integer. Prove that there exists a natural number n such that the number an + b has a
divisor of the form cx + 1, x ∈ N.

Problem 1.2 (ISL 2019 N5). Let a be a positive integer. We say that a positive integer b
is a-good if an


b − 1 is divisible by an + 1 for all positive integers n with an ≥ b. Suppose
b is a positive integer such that b is a-good, but b + 2 is not a-good. Prove that b + 1 is
prime.

Problem 1.3 (ISL 2006 N7). For all positive integers n, show that there exists a positive
integer m such that n divides 2m + m.

Problem 1.4 (ISL 2011 N6). Let P (x) and Q(x) be two polynomials with integer
coefficients, such that no nonconstant polynomial with rational coefficients divides both
P (x) and Q(x). Suppose that for every positive integer n the integers P (n) and Q(n)
are positive, and 2Q(n) − 1 divides 3P (n) − 1. Prove that Q(x) is a constant polynomial.

Problem 1.5 (Russia 2012 11.8). For a positive integer n define Sn = 1! + 2! + . . . + n!.
Prove that there exists an integer n such that Sn has a prime divisor greater than 102012 .

§1.3 Theoretic stuff, exponential, heavy duty:

Problem 1.6 (ELMOSL 2011 N1). Prove that n3 − n − 3 is not a perfect square for
any integer n.

Problem 1.7 (ELMOSL 2011 N4). Let p > 13 be a prime of the form 2q + 1, where q is
prime. Find the number of ordered pairs of integers (m, n) such that 0 ≤ m < n < p − 1
and
3m + (−12)m ≡ 3n + (−12)n (mod p).

1
Rohan Goyal (June 11, 2021) Number Theory

Problem 1.8 (ISL 2019 N8). Let a and b be two positive integers. Prove that the integer
 2
4a
a2 +
b
is not a square. (Here dze denotes the least integer greater than or equal to z.)
Problem 1.9 (USOMO 2020/3). Let p be an odd prime. An integer x is called a
quadratic non-residue if p does not divide x − t2 for any integer t.

Denote by A the set of all integers a such that 1 ≤ a < p, and both a and 4 − a are
quadratic non-residues. Calculate the remainder when the product of the elements of A
is divided by p.
Problem 1.10 (USEMO 2020/6). Prove that for every odd integer n > 1, there exist
integers a, b > 0 such that, if we let Q(x) = (x + a)2 + b, then the following conditions
hold:
• we have gcd(a, n) = gcd(b, n) = 1;
• the number Q(0) is divisible by n; and
• the numbers Q(1), Q(2), Q(3), . . . each have a prime factor not dividing n.

§1.4 Polynomial Stuff:

Shared previously(I’ll still add a few)

§1.5 Constructions:
Problem 1.11. Does there exist an infinite sequence of positive integers a1 , a2 , . . . such
that
Every positive integer appears in the sequence exactly once.
For every positive integer n the product a1 a2 . . . an of the first n terms of the
sequence is an n’th power?
Problem 1.12 (USATSTST 2015/5). Let ϕ(n) denote the number of positive integers
less than n that are relatively prime to n. Prove that there exists a positive integer m
for which the equation ϕ(n) = m has at least 2015 solutions in n.
Problem 1.13 (USATST 2021/1). Determine all integers s ≥ 4 for which there exist
positive integers a, b, c, d such that s = a + b + c + d and s divides abc + abd + acd + bcd.
Problem 1.14 (Real Shortlist/Komal). Let f (k) = 2k + 1 for arbitrary positive integer
k. Is there any positive integer n which divides f (f (n)), but does not divide f (f (f (n)))?
Problem 1.15 (Kazakhastan ’17?). Prove that there are infinitely many odd composite
n such that
n−1
n|2 2 + 1
Problem 1.16 (ELMO 2020/6). For any positive integer n, let
τ (n) denote the number of positive integer divisors of n,
σ(n) denote the sum of the positive integer divisors of n, and
ϕ(n) denote the number of positive integers less than or equal to n that are relatively
prime to n.
Let a, b > 1 be integers. Brandon has a calculator with three buttons that replace the
integer n currently displayed with τ (n), σ(n), or ϕ(n), respectively. Prove that if the
calculator currently displays a, then Brandon can make the calculator display b after a
finite (possibly empty) sequence of button presses.

2
Rohan Goyal (June 11, 2021) Number Theory

§1.6 NT!
Problem 1.17 (ISL 2017 N1). For each integer a0 > 1, define the sequence a0 , a1 , a2 , . . .
for n ≥ 0 as (√ √
an if an is an integer,
an+1 =
an + 3 otherwise.
Determine all values of a0 such that there exists a number A such that an = A for
infinitely many values of n.
Problem 1.18 (CHMMC Proof 2021). Find all positive integers n ≥ 3 such that
there exists a permutation a1 , a2 , · · · , an of 1, 2 · · · n such that a1 , 2a2 , · · · , nan can be
rearranged into an arithmetic progression.
Problem 1.19 (USEMO 2019/4). Prove that for any prime p, there exists a positive
integer n such that
1n + 2n−1 + 3n−2 + · · · + n1 ≡ 2020 (mod p).
Problem 1.20 (China TST 2021/4/1). Find all functions f : Z+ → Z+ such that for
all positive integers m, n with m ≥ n,
f (mϕ(n3 )) = f (m) · ϕ(n3 ).
Here ϕ(n) denotes the number of positive integers coprime to n and not exceeding n.
Problem 1.21 (Taiwan 2021). Let a1 , a2 , a3 , . . . be a sequence of positive integers such
that a1 = 2021 and
√ √
an+1 − an = b an c.
Show that there are infinitely many odd numbers and infinitely many even numbers in
this sequence.
Problem 1.22 (KWPT 2021). n ≥ 2 is a given positive integer. i ≤ ai ≤ n satisfies for
all 1 ≤ i ≤ n, and Si is defined as a1 + a2 + ... + ai (S0 = 0). Show that there exists such
1 ≤ k ≤ n that satisfies a2k + Sn−k < 2Sn − n(n+1)2 .
Problem 1.23 (ISL 2019 N4). Find all functions f : Z>0 → Z>0 such that a + f (b)
divides a2 + bf (a) for all positive integers a and b with a + b > 2019.
Problem 1.24 (USATSTST 2020/8). For every positive integer N , let σ(N ) denote the
sum of the positive integer divisors of N . Find all integers m ≥ n ≥ 2 satisfying
σ(m) − 1 σ(n) − 1 σ(mn) − 1
= = .
m−1 n−1 mn − 1
Problem 1.25 (Russia 2021 10.7). Find all permutations (a1 , a2 , ..., a2021 ) of (1, 2, ..., 2021),
such that for every two positive integers m and n with difference bigger than 2021 , the
following inequality holds:
GCD(m + 1, n + a1 ) + GCD(m + 2, n + a2 ) + ... + GCD(m + 2021, n + a2021 ) < 2|m − n|
Problem 1.26 (LMAOSL 2021 N2). Let k be a positive integer such that p = 2k − 1 is
a prime. Let P be an integer polynomial satisfying
π
P (sin(θ + 2k−1
)) = P (sin(θ))
for all θ ∈ R. Define the sequence (ai )i≥0 by a0 = 1, a1 = 2, and
an+1 = 4an − an−1
Show that for any i, j we have p | P (ai ) − P (aj ).

3
Rohan Goyal (June 11, 2021) Number Theory
√
Problem 1.27 (ISL 2019 N6). Let H = {bi 2c : i ∈ Z>0 } = {1, 2, 4, 5, 7, . . . } and let n
be a positive integer. Prove that there exists a constant C such that, if A ⊆ {1, 2, . . . , n}
√
satisfies |A| ≥ C n, then there exist a, b ∈ A such that a − b ∈ H. (Here Z>0 is the set
of positive integers, and bzc denotes the greatest integer less than or equal to z.)

Problem 1.28 (Russia 2021 10.4). Given a natural number n > 4 and 2n + 4 cards
numbered with 1, 2, . . . , 2n + 4. On the card with number m a real number am is written
such that bam c = m. Prove that it’s possible to choose 4 cards in such a way that the
sum of the numbers on the first two cards differs from the sum of the numbers on the
two remaining cards by less than
1
n − n2
p

Problem 1.29 (LMAO 2021/3). Find the least positive integer k that satisfies the
following:
For any monic polynomial P (x) of degree 2021 with integer coefficients, there exists a set
T (dependent on P ) of k integers, such that there is no set S which satisfies the following
three conditions simultaneously:

1. T ⊆ S

2. S is proper subset of Z

3. If u, v ∈ S, then P (u) + v ∈ S

Problem 1.30 (Komal). Prove that for all sufficiently large n, and any set of integers
of size n, there exist 2021 elements with least common multiple at least n2020.99

Problem 1.31 (Miklos 2019/3). Prove that there are infinitely many integers m, n,
such that 1 < m < n, and the greatest common divisors (m, n), (m, n + 1), (m + 1, n)
√
and (m + 1, n + 1) are all greater than n/999.

Problem 1.32 (MOMO 2019/3). Let S(n) denote the sum of digits of n when written
in base ten. Given a positive integer k, determine all pairs of pairwise distinct positive
integers (n1 , ..., nk ) satisfying the following conditions:

1. n1 , n2 , ..., nk are not multiples of 10

2. as t runs through positive integers, the expression S(n1 t) + ... + S(nk t) covers all but
finitely many positive integers.

Problem 1.33 (LMAO 2021/8). Given an odd

j k
prime q, find all integer polynomials P
p
such that every prime p > q 2021 , divides P (q q
), and P (1) = 0.

Problem 1.34 (Taiwan
TST). Given a prime p = 8k + 1 for some integer k. Let r be
√
the remainder when 4k
k is divided by p. Prove that r is not an integer.

Problem 1.35 (Iran TST 2021/3). There exist 4 positive integers a, b, c, d such that
abcd 6= 1 and each pair of them have a GCD of 1. Two functions f, g : N → {0, 1} are
multiplicative functions such that for each positive integer n we have :

f (an + b) = g(cn + d)
Prove that at least one of the followings hold.
i) for each positive integer n we have f (an + b) = g(cn + d) = 0

4
Rohan Goyal (June 11, 2021) Number Theory

ii) There exists a positive integer k such that for all n where (n, k) = 1 we have
g(n) = f (n) = 1.

(Function f is multiplicative if for any natural numbers a, b we have f (ab) = f (a)f (b))

Problem 1.36 (RMM 2020/6). For each integer n ≥ 2, let F (n) denote the greatest
prime factor of n. A strange pair is a pair of distinct primes p and q such that there is
no integer n ≥ 2 for which F (n)F (n + 1) = pq.

Prove that there exist infinitely many strange pairs.