NT Constuct

OMC

Rohan Goyal
August 1, 2021

”Random Fact, which if true... ”

-Atul

§1 Lagrange and CRT type construction

Theorem 1.1 (Chinese Remainder Theorem)

Let a1 , a2 , · · · an be a list of pairwise co-prime naturals. Let b1 , b2 , · · · bn be a list of
n naturals. Then, there exists a unique k ∈ {1, 2, · · · , a1 a2 · · · an } such that

k ≡ b1 (mod a1 )
≡ b2 (mod a2 )
≡ b3 (mod a3 )
..
.
≡ bn (mod an )

Look at the set of congruences we want as n tuples.

Now, we can just look at it as

(b1 , b2 , · · · , bn ) = (b1 , 0, 0, · · · ) + (0, b2 , 0, · · · 0) + · · · (0, 0, 0, · · · bn )

then we just want to construct (b1 , 0, 0, · · · 0) as the others would be constructed similarly.

Now we just want ca2 a3 · · · an ≡ b1 (mod a1 ) for some c but then c = (a2 · · · an )−1 b1 and
thus we are done where the inverse is (mod a1 )!

Theorem 1.2 (Lagrange Interpolation)

If x1 < x2 < · · · xn+1 are complex numbers and a1 , a2 , · · · an+1 are some other
complex numbers then there exists a unique polynomial P of degree atmost n such
that P (xi ) = ai .

1
Rohan Goyal (August 1, 2021) NT Constuct

P (x1 ), P (x2 ), · · · P (xn+1 ) then you can find such a unique atmost n degree polynomial.

Adapting same idea as before, we just want tuple (a1 , 0, 0, 0, · · · )

Q1 (x) = (x − x2 )(x − x3 ) · · · (x − xn+1 )

P1 (x) = Q1a(x
1
1)
Q1 (x) and similarly defining other Pi and summing over all we find a
required P .

Now, for uniqueness, just observe that if R, S satisfy the conditions then R − S takes
(0, 0, 0, · · · 0) but then it has n + 1 roots and is atmost n degree so must be 0 polynomial.

Exercise 1.3 (USA EGMOTST 2020). Find the largest integer N ∈ {1, 2, . . . , 2019}
such that there exists a polynomial P (x) with integer coefficients satisfying the following
property: for each positive integer k, P k (0) is divisible by 2020 if and only if k is divisible
by N . Here P k means P applied k times, so P 1 (0) = P (0), P 2 (0) = P (P (0)), etc.

§2 How to build from what you have?

Example 2.1 (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.

So, we want 2015 numbers to take the same value of φ(n). How do you think we can go
about this?

ϕ(pα1 1 pα2 2 · · · pαnn ) = (pα1 1 − pα1 1 −1 ) · · ·

pn then let’s just pick all primes less than it.

spn and s(pn − 1) then φ(spn ) = φ(s)(pn − 1) and φ(s(pn − 1)) = φ(s)(pn − 1) if
rad(pn − 1)|s so I was saying why don’t we pick s to include p1 , p2 , · · · pn−1 i.e. all primes
less than pn .

p1 p2 p3 · · · p2014 and replaced pi with pi − 1 so we have 2014 options and one is the number
itself so we are done. s = p1 p2 ···p
pi
2014

Example 2.2 (RMM 2012/4)

n +1
Prove that there are infinitely many positive integers n such that 22 +1 is divisible
by n but 2n + 1 is not.

f (n) = 2n + 1, there are infinitely many n such that n|f (f (n)) but n - f (n).

xa + 1|xb + 1 iff a|b and both are odd. Let b = ak + r =⇒ xa + 1|xak + 1 =⇒

xa + 1|xak+r + xr =⇒ xa + 1|xr − 1 =⇒ r = 0 =⇒ a|b.

n|f (n) ⇐⇒ f (n)|f (f (n)) so if n satisfies our condition so does f (n).

2
Rohan Goyal (August 1, 2021) NT Constuct

n|f (f (n)) ⇐⇒ f (n)|f (f (f (n))) so if we just need to find one number that satisfies our
conditions.

3 does not work but what about multiples of 3?

3p we would want p - 23p + 1 or equivalently p - 23 + 1 =⇒ p 6= 3 and we want 3p|f (f (3p))

we want but then we want p|f (f (3p)).

So we can just a pick prime factor of f (f (3)) and we will be done since f (f (3))|f (f (3p)).

29 + 1 = 513 = 9 × 57 = 27 × 19 so p = 19 so 3p works.

Example 2.3 (EGMO 2018/2)

Consider the set
1
A= 1 + : k = 1, 2, 3, 4, · · · .
k
Prove that every integer x ≥ 2 can be written as the product of one or more elements
of A, which are not necessarily different.
For every integer x ≥ 2 let f (x) denote the minimum integer such that x can be
written as the product of f (x) elements of A, which are not necessarily different.
Prove that there exist infinitely many pairs (x, y) of integers with x ≥ 2, y ≥ 2, and

f (xy) < f (x) + f (y).

(Pairs (x1 , y1 ) and (x2 , y2 ) are different if x1 6= x2 or y1 6= y2 ).

k+1 k
k · k−1 · · · 21 = k + 1 so first part done!
a
2a × ( 2 2+1 a a
a ) = 2 + 1 so f (2 + 1) = a + 1 is very good, because you just need a + 1 terms!!

Now, let’s say it has prime divisor 3 then 3 itself needs 2 terms and (2a + 1)/3 also needs
atleast a terms hence we are done!

3
Rohan Goyal (August 1, 2021) NT Constuct

§3 Problems for practice

The section is roughly ordered by difficulty and its fairly extensive so choose problems
that appeal to you and try to do them. Some of these might be closer to combo or
algebra than NT but that’s okay and similarly some are closer to normal NT than you’d
expect a usual construct problem to be and that’s okay too.

I’ve divided into subsections roughly based on difficulty but last problems of each
subsection might be harder than the subsection name suggests.

§3.1 Easy
Problem 3.1 (USAMO 2017/1). Prove that there are infinitely many distinct pairs
(a, b) of relatively prime integers a > 1 and b > 1 such that ab + ba is divisible by a + b.
Problem 3.2. 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 3.3 (ISL 2020 N1). Given a positive integer k show that there exists a prime
p such that one can choose distinct integers a1 , a2 · · · , ak+3 ∈ {1, 2, · · · , p − 1} such that
p divides ai ai+1 ai+2 ai+3 − i for all i = 1, 2, · · · , k.
Problem 3.4 (ISL 2007 N2). Let b, n > 1 be integers. Suppose that for each k > 1
there exists an integer ak such that b − ank is divisible by k. Prove that b = An for some
integer A
Problem 3.5 (ISL 2017 N2). Let p ≥ 2 be a prime number. Eduardo and Fernando
play the following game making moves alternately: in each move, the current player
chooses an index i in the set {0, 1, 2, . . . , p − 1} that was not chosen before by either
of the two players and then chooses an element ai from the set {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.
Eduardo has the first move. The game ends after all the indices have been chosen .Then
the following number is computed:
p−1
X
M = a0 + a1 10 + a2 102 + · · · + ap−1 10p−1 = ai .10i
i=0
The goal of Eduardo is to make M divisible by p, and the goal of Fernando is to prevent
this.

Prove that Eduardo has a winning strategy.

Problem 3.6 (USAMO 2011/4). Consider the assertion that for each positive integer
n
n ≥ 2, the remainder upon dividing 22 by 2n − 1 is a power of 4. Either prove the
assertion or find (with proof) a counterexample.
Problem 3.7 (IMO 2016/4). A set of positive integers is called fragrant if it contains at
least two elements and each of its elements has a prime factor in common with at least
one of the other elements. Let P (n) = n2 + n + 1. What is the least possible positive
integer value of b such that there exists a non-negative integer a for which the set
{P (a + 1), P (a + 2), . . . , P (a + b)}
is fragrant?

4
Rohan Goyal (August 1, 2021) NT Constuct

Problem 3.8 (ISL 2019 N3). We say that a set S of integers is rootiful if, for any positive
integer n and any a0 , a1 , · · · , an ∈ S, all integer roots of the polynomial a0 +a1 x+· · ·+an xn
are also in S. Find all rootiful sets of integers that contain all numbers of the form 2a − 2b
for positive integers a and b.

Problem 3.9 (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 3.10 (ISL 2020 N6). For a positive integer n, let d(n) be the number of
positive divisors of n, and let ϕ(n) be the number of positive integers not exceeding n
which are coprime to n. Does there exist a constant C such that

ϕ(d(n))
≤C
d(ϕ(n))

for all n ≥ 1

Problem 3.11 (Komal, derived from the RMM). 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 3.12 (China MO 2019/2). Call a set of 3 positive integers {a, b, c} a Pythagorean
set if a, b, c are the lengths of the 3 sides of a right-angled triangle. Prove that for any
2 Pythagorean sets P, Q, there exists a positive integer m ≥ 2 and Pythagorean sets
P1 , P2 , . . . , Pm such that P = P1 , Q = Pm , and ∀1 ≤ i ≤ m − 1, Pi ∩ Pi+1 6= ∅.

Problem 3.13 (USATST 2015/2). Prove that for every n ∈ N, there exists a set S of n
positive integers such that for any two distinct a, b ∈ S, a − b divides a and b but none
of the other elements of S.

Problem 3.14 (ISL 2018 A3). Given any set S of positive integers, show that at least
one of the following two assertions holds:
P P
(1) There exist distinct finite subsets F and G of S such that x∈F 1/x = x∈G 1/x;
P
(2) There exists a positive rational number r < 1 such that x∈F 1/x 6= r for all finite
subsets F of S.

5
Rohan Goyal (August 1, 2021) NT Constuct

§3.2 Medium
Problem 3.15 (China TST 2021/4). 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 3.16 (APMO 2009/4). Prove that for any positive integer k, there exists an
arithmetic sequence ab11 , ab22 , ab33 , ..., abkk of rational numbers, where ai , bi are relatively prime
positive integers for each i = 1, 2, ..., k such that the positive integers a1 , b1 , a2 , b2 , ..., ak , bk
are all distinct.
Problem 3.17 (MOMO 2020/5). Let S be the set of positive integers (x, y) such that
gcd(x, y) = 1. Is it possible to assign a positive integer f (x, y) to each (x, y) ∈ S such
that the following conditions are satisfied?
• |f (p, r) − f (q, s)| ≤ 2 holds for any positive integers p, q, r, s satisfying pq − rs = 1;
• for every (a, b) ∈ S with a > b, f (a + b, b) = f (a, b);
• and for any n ≥ 2019, the equation f (p, q) = n has infinitely many solutions
(p, q) ∈ S.
Problem 3.18 (ISL 2014 N4). Let n > 1 be a given integer. Prove that infinitely many
terms of the sequence (ak )k≥1 , defined by
k
n
ak = ,
k
are odd. (For a real number x, bxc denotes the largest integer not exceeding x.)
Problem 3.19 (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 3.20 (ISL 2020 N4). For any odd prime p and any integer n, let dp (n) ∈
{0, 1, . . . , p − 1} denote the remainder when n is divided by p. We say that (a0 , a1 , a2 , . . . )
is a p-sequence, if a0 is a positive integer coprime to p, and an+1 = an + dp (an ) for n > 0.
(a) Do there exist infinitely many primes p for which there exist p-sequences (a0 , a1 , a2 , . . . )
and (b0 , b1 , b2 , . . . ) such that an > bn for infinitely many n, and bn > an for infinitely
many n?
(b) Do there exist infinitely many primes p for which there exist p-sequences (a0 , a1 , a2 , . . . )
and (b0 , b1 , b2 , . . . ) such that a0 < b0 , but an > bn for all n > 1?
Problem 3.21 (ISL 2020 A5). A magician intends to perform the following trick. She
announces a positive integer n, along with 2n real numbers x1 < · · · < x2n , to the
audience. A member of the audience then secretly chooses a polynomial P (x) of degree n
with real coefficients, computes the 2n values P (x1 ), . . . , P (x2n ), and writes down these
2n values on the blackboard in non-decreasing order. After that the magician announces
the secret polynomial to the audience. Can the magician find a strategy to perform such
a trick?

6
Rohan Goyal (August 1, 2021) NT Constuct

Problem 3.22 (EGMO 2014/3). We denote the number of positive divisors of a positive
integer m by d(m) and the number of distinct prime divisors of m by ω(m). Let k be
a positive integer. Prove that there exist infinitely many positive integers n such that
ω(n) = k and d(n) does not divide d(a2 + b2 ) for any positive integers a, b satisfying
a + b = n.

Problem 3.23 (USAMO 2013/5). Given positive integers m and n, prove that there is a
positive integer c such that the numbers cm and cn have the same number of occurrences
of each non-zero digit when written in base ten.

Problem 3.24 (ISL 2013 N4). Determine whether there exists an infinite sequence of
nonzero digits a1 , a2 , a3 , · · · and a positive integer N such that for every integer k > N ,
the number ak ak−1 · · · a1 is a perfect square.

Problem 3.25 (ISL 2012 N5). For a nonnegative integer n define rad(n) = 1 if n = 0 or
n = 1, and rad(n) = p1 p2 · · · pk where p1 < p2 < · · · < pk are all prime factors of n. Find
all polynomials f (x) with nonnegative integer coefficients such that rad(f (n)) divides
rad(f (nrad(n) )) for every nonnegative integer n.

7
Rohan Goyal (August 1, 2021) NT Constuct

§3.3 Hard
Problem 3.26 (ISL 2019 A7). Let Z be the set of integers. We consider functions
f : Z → Z satisfying
f (f (x + y) + y) = f (f (x) + y)
for all integers x and y. For such a function, we say that an integer v is f-rare if the set

Xv = {x ∈ Z : f (x) = v}

is finite and nonempty.

(a) Prove that there exists such a function f for which there is an f -rare integer.
(b) Prove that no such function f can have more than one f -rare integer.

Problem 3.27 (IMO 2004/6). We call a positive integer alternating if every two consec-
utive digits in its decimal representation are of different parity.

Find all positive integers n such that n has a multiple which is alternating.

Problem 3.28 (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.

Problem 3.29 (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 3.30 (Iran 2020 Round 3/N4). Prove that for every two positive integers a, b
greater than 1. there exists infinitly many n such that the equation φ(an − 1) = bm − bt
can’t hold for any positive integers m, t.

Problem 3.31 (USAMO 2006/3). For integral m, let p(m) be the greatest prime divisor
of m. By convention, we set p(±1) = 1 and p(0) = ∞. Find all polynomials f with integer
coefficients such that the sequence

{p f n2 − 2n}n≥0

is bounded above. (In particular, this requires f n2 6= 0 for n ≥ 0.)

Problem 3.32 (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.

Problem 3.33 (IMO 2003/6). Let p be a prime number. Prove that there exists a prime
number q such that for every integer n, the number np − p is not divisible by q.

8
Rohan Goyal (August 1, 2021) NT Constuct

Problem 3.34 (Vietnam TST 2021/6). Let n ≥ 3 be a positive integers and p be a

prime number such that p > 6n−1 − 2n + 1. Let S be the set of n positive integers with
different residues modulo p. Show that there exists a positive integer c such that there are
exactly two ordered triples (x, y, z) ∈ S 3 with distinct elements, such that x − y + z − c
is divisible by p.

Problem 3.35 (Kazakhastan ’17?). Prove that there are infinitely many odd composite
n such that
n−1
n|2 2 + 1

Problem 3.36 (ELMO 2019/6). Carl chooses a functional expression* E which is a

finite nonempty string formed from a set x1 , x2 , . . . of variables and applications of a
function f , together with addition, subtraction, multiplication (but not division), and
fixed real constants. He then considers the equation E = 0, and lets S denote the set
of functions f : R → R such that the equation holds for any choices of real numbers
x1 , x2 , . . . . (For example, if Carl chooses the functional equation

f (2f (x1 ) + x2 ) − 2f (x1 ) − x2 = 0,

then S consists of one function, the identity function.

(a) Let X denote the set of functions with domain R and image exactly Z. Show that
Carl can choose his functional equation such that S is nonempty but S ⊆ X.

(b) Can Carl choose his functional equation such that |S| = 1 and S ⊆ X?

*These can be defined formally in the following way: the set of functional expressions
is the minimal one (by inclusion) such that (i) any fixed real constant is a functional
expression, (ii) for any positive integer i, the variable xi is a functional expression, and
(iii) if V and W are functional expressions, then so are f (V ), V + W , V − W , and V · W .

Problem 3.37 (USAMO 2012/3). Determine which integers n > 1 have the property
that there exists an infinite sequence a1 , a2 , a3 , . . . of nonzero integers such that the
equality
ak + 2a2k + . . . + nank = 0
holds for every positive integer k.

Problem 3.38 (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 3.39 (IMO 2017/6). An ordered pair (x, y) of integers is a primitive point if
the greatest common divisor of x and y is 1. Given a finite set S of primitive points,
prove that there exist a positive integer n and integers a0 , a1 , . . . , an such that, for each
(x, y) in S, we have:

a0 xn + a1 xn−1 y + a2 xn−2 y 2 + · · · + an−1 xy n−1 + an y n = 1.

9
Rohan Goyal (August 1, 2021) NT Constuct

Problem 3.40 (ISL 2015 N7). Let Z>0 denote the set of positive integers. For any
positive integer k, a function f : Z>0 → Z>0 is called k-good if gcd(f (m)+n, f (n)+m) ≤ k
for all m 6= n. Find all k such that there exists a k-good function.

Problem 3.41 (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.

Problem 3.42 (Canada 2014/5). Fix positive integers n and k ≥ 2. A list of n integers
is written in a row on a blackboard. You can choose a contiguous block of integers, and
I will either add 1 to all of them or subtract 1 from all of them. You can repeat this
step as often as you like, possibly adapting your selections based on what I do. Prove
that after a finite number of steps, you can reach a state where at least n − k + 2 of the
numbers on the blackboard are all simultaneously divisible by k.

10