Polynomials in Number Theory

Kazi Aryan Amin

INMOTC West Bengal, January 5th, 2024

Contents

1 Basic Properties 2
1.1 a ´ b | P paq ´ P pbq . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Prime Divisors of Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2 Factorization of Polynomials 3
2.1 Euclidean Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 Greatest Common Divisors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.3 Gauss Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

3 Hensel Lifting Lemma 5

4 Examples 6

5 Problems 9

6 Solutions to Examples 13
6.1 Example 4.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
6.2 Example 4.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
6.3 Example 4.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
6.4 Example 4.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
6.5 Example 4.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
6.6 Example 4.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
6.7 Example 4.7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
6.8 Example 4.8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
6.9 Example 4.9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
6.10 Example 4.10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
6.11 Example 4.11 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

1
1 Basic Properties
The goal of the handout is to investigate number-theoretic properties of integer-coefficient polynomials.

Notation 1.1
Define ZrXs to be the set of all integer coefficient polynomials. Similarly, let QrXs denote the set of all
rational coefficient polynomials.

1.1 a ´ b | P paq ´ P pbq

One of the most useful facts about polynomials is that they are "mod n"-preserving. In other words, we
have:

Theorem 1.2
Let P P ZrXs. Then, for integers a, b, we have a ´ b | P paq ´ P pbq.
Another way to state this is as follows. Let n be a positive integer and let a and b be integers such
that a ” b pmod nq. Then P paq ” P pbq pmod nq.

Proof. This follows directly from the fact that a ´ b | ai ´ bi for all positive integers i .

Remark 1.3. The above is a very important result as it tells us that P pnq is "periodic" mdoulo p with period
p.
Here’s another useful lemma to keep in mind:

Lemma 1.4
P pnq | P pn ` kP pnqq for all integers n, k.

Proof. Take a “ n ` kP pnq and b “ n in the above theorem.

1.2 Prime Divisors of Polynomials

Definition 1.5
Given a polynomial P P ZrXs, we say a prime p is a prime divisor of P , if p | P pnq for some n P Z.
Denote the set of prime divisors of P by SP .

Exercise 1.6
Given a polynomial P P Z, consider two primes p, q such that p P SP and q R SP . Find polynomials P`
and P´ such that:
‚ SP` “ SP Y tqu
‚ SP´ “ SP ztpu

2
 Theorem 1.7 (Schur’s Theorem)
SP is infinite for all non constant polynomials P .

Proof. Note that if P p0q “ 0, then there is nothing to prove. Now, we first deal with the case when
P p0q “ 1. Consider all numbers of the form P pn!q, where n is a large positive integer. Note that P pn!q ” 1
pmod nq. Thus, if p is the largest prime divisor of n, then taking n " p leads to a contradiction.
P pxP p0qq
To reduce to the previous case, define Qpxq “ P p0q . Clearly Qpxq P ZrXs and Qp0q ” 1. Now apply
the previous part to Q.

2 Factorization of Polynomials

2.1 Euclidean Algorithm

Just like we have an Euclidean Algorithm for integers, we have one for polynomials in ZrXs and QrXs. Here
is the theorem, stated without proof

Theorem 2.1
Given polynomials P, Q P QrXs, there exists polynomials R, S P QrXs such that

P “Q¨R`S

and either S “ 0 or deg S ă deg Q. We call S the remainder of P and Q.

2.2 Greatest Common Divisors

Definition 2.2
We say a polynomial f P ZrXs is irreducible, if whenever f ” gh for g, h P ZrXs, then either g ” 1 or
f ” 1. Similarly for QrXs, we define f to be irreducible if g ” q or h ” q, for q P Q.

Remark 2.3. Note that with the above definition, 2x is NOT irreducible in ZrXs. Mostly in contests, you
will be told something "cannot be written as the product of two non-constant polynomials" rather than
irreducible.

Just like Z or Q, we have unique factorization for both ZrXs and QrXs.

Theorem 2.4
Every polynomial in QrXs can be factored uniquely as a product of irreducible polynomials.

3
 Definition 2.5 (GCD)
For polynomials P, Q P QrXs, their greatest common divisor, denoted gcdpP, Qq, is the polynomial
R P QrXs of greatest degree which divides both P, Q.

Proposition 2.6
The Euclidean algorithm says, that when R is the remainder of Q mod P , we have

gcdpP, Qq “ gcdpP, Rq

Theorem 2.7 (Bezout for polynomials)

If P, Q P QrXs, then there exist A, B P QrXs such that

A ¨ P ` B ¨ Q “ gcdpP, Qq

Here’s an interesting lemma to keep in mind.

Lemma 2.8
Let P pnq, Qpnq be relatively prime polynomials with integer coefficients. Then, the sequence defined by
an “ gcdpP pnq, Qpnqq is bounded (actually it’s periodic), as n varies over the positive integers.

Proof. By the previous theorem, there exists polynomials A, B, such that AP ` BQ “ k for some k P N.
Thus an | k for all n ě 1. Hence an is bounded.
We will show that an | an`k . Note that P pn ` kq ” P pnq pmod kq, and since an | k and P pnq, it divides
P pn ` kq as well. Similarly an | Qpn ` kq, so an | an`k . But the same relations imply that an`k | an , so they
are equal. Hence, the sequence is periodic, as desired.

2.3 Gauss Lemma

Definition 2.9
A polynomial f P ZrXs is said to be primitive if the gcd of all its coefficients is 1.

Theorem 2.10 (Gauss Lemma)

The product of two primitive polynomials is primitive.

Proof. Let f , g P ZrXs be primitive, and suppose f g “ h. Assume h is not primitive, then there exists some
prime p such that p divides all the coefficients in p. Then, working in Fp , we have f g “ 0, so one of f or g
must have all coefficients divisible by p, and we have our desired contradiction.

4
 Lemma 2.11
Let ppxq, qpxq P ZrXs be primitive polynomials. If ppxqr pxq “ qpxq for some r pxq P QrXs, then actually,
r pxq P ZrXs and is primitive.

a
Proof. Let r pxq “ b r0 pxq, where a, b P N, and r0 P ZrXs, such that gcdpa, bq “ 1 and r0 is primitive.
So we have appxqr0 pxq “ bqpxq. Now by Gauss Lemma, ppxqr0 pxq is primitive. But b must divide all the
coefficients of ppxqr0 pxq. Thus, b “ 1. Similarly a divides all the coefficients of qpxq and hence must equal
1, as desired.

Gauss Lemma leads to the theorem:

Theorem 2.12
If f is a primitive polynomial in ZrXs, then it is irreducible in ZrXs, iff it is irreducible in QrXs.

Proof. Here’s a brief sketch of rthge Suppose f pxq is reducible in QrXs and is primitive. Write f pxq “
ApxqBpxq, where A, B P QrXs, and neither are constant. Clearing denominators, we get df pxq “ A1 pxqB1 pxq
for some d P N, where A1 , B1 P ZrXs.
For the other direction, use the previous lemma.

3 Hensel Lifting Lemma

The Hensel-Lifting lemma, allows us to lift congruences from pmod pq to pmod p k q.

Theorem 3.1 (Hensel Lifting Lemma)

Let f be a polynomial with integer coefficients and let p be a prime. Suppose n is an integer such that
p ∤ f 1 pnq, but p | f pnq. Then there exists a sequence of integers pnk qkě1 such that:

‚ n1 “ n.
‚ nk`1 ” nk pmod p k q.
‚ p k | f pnk q.

Proof. Proceed inductively. Suppose we have found ni . We set ni`1 “ ni ` b ¨ p i , such that p i`1 | f pni`1 q.
Since 2i ě i ` 1, the binomial formula gives

f pni ` b ¨ p i q ” f pni q ` bp i f 1 pni q pmod p i`1 q

Let f pni q “ cp i for some integer c. Because ni ” n pmod pq, and f 1 pni q ” f 1 pnq pmod pq, hence f 1 pni q is
invertible modulo p, whence taking b “ ´rf 1 pni qs´1 ¨ c works.

Here’s an important lemma:

5
 Lemma 3.2
Let f pxq P Zrxs be an irreducible polynomial. Then if p is prime and p ą Cf ,f 1 for an appropriate
constant Cf ,f 1 and f has root in Fp , then there exists x with νp pf pxqq “ 1.

Proof. Since f is irreducible, hence f , f 1 are coprime to each other. Thus, there exists A, B P ZrXs such
that Af ` Bf 1 “ c for c P N. Consider a prime p ě c and suppose f has a root pmod pq. So there is
some n such that p | f pnq. The choice of p ensures that p ∤ f 1 pnq. Now note that p | f pn ` pq as well.
Furthermore, we have
f pn ` pq “ f pnq ` pf 1 pnq pmod p 2 q

So at least one of f pn`pq and f pnq must have νp p‚q “ 1, else p | f 1 pnq is forced. This proves the lemma.

Having done most of the theory, we move towards example problems.

4 Examples

Example 4.1 (classic)

Prove that for any polynomial P P ZrXs, there exists infinitely many n such that |P pnq| is composite.

By Schur, you can find a prime p | P pcq for some c. But p | P pc ` kpq for k ě 1 as well. Conclude by
size reasons.

Example 4.2 (ELMO 2016 P4)

Consider a polynomial P with integer coefficients such that n divides P p2n q for every positive integer n.
Show that P must be the zero polynomial.

Working with n “ pq, for odd primes p, q, we get that p | P p2p qq, so p | p2q q(why?). Conclude by
taking p arbitarily large.

Example 4.3 (ELMO SL 2014 N1)

Does there exist a strictly increasing infinite sequence of perfect squares a1 , a2 , a3 , ... such that for all
k P Z` we have that 13k | ak ` 1?

This is basically a direct Hensel problem. Find a x such that 13 | x 2 ` 1 and show that for this choice
13 ∤ 2x. You’re done by Hensel.

Example 4.4 (classic)

Does there exist a non-constant polynomial P pxq P ZrXs such that it takes only squarefree values ?

It suffices to consider P to be irreducible. By Hensel, we know that p | P pnq implies p | P 1 pnq. So by

Schur, gcdpP pnq, P 1 pnqq is unbounded, contradiction.

6
 Example 4.5 (Canada 2016 P3)
Find all polynomials P pxq with integer coefficients such that P pP pnq ` nq is a prime number for infinitely
many integers n.

You know that P pn ` P pnqq is divisible by P pnq, so it must equal ˘P pnq. Use size stuff now.

Example 4.6 (me)

Find all polynomials P pxq P ZrXs such that P pxq is surjective modulo all sufficiently large primes .
In other words , for every sufficiently large prime p and a positive integer k , there exists a n such
that p | P pnq ´ k

The main idea is to show that we actually have p | m ´ n ðñ p | f pmq ´ f pnq. Now, use Schur on
P px ` 1q ´ P pxq.

Example 4.7 (IberoAmerican 2019 P6)

Let a1 , a2 , . . . , a2019 be positive integers and P a polynomial with integer coefficients such that, for every
positive integer n,
P pnq divides a1n ` a2n ` ¨ ¨ ¨ ` a2019
n
.

Prove that P is a constant polynomial.

The main idea is the P pnq is periodic pmod pq, with period p, while an is periodic pmod pq, with period
p ´ 1. Call the RHS expression f pnq. Show that p | f pnq means p | f pn ` 1q. Choose n suitably, and take p
large.

Example 4.8 (USA TST 2010 P1)

Let P be a polynomial with integer coefficients such that P p0q “ 0 and

gcdpP p0q, P p1q, P p2q, . . .q “ 1.

Show there are infinitely many n such that

gcdpP pnq ´ P p0q, P pn ` 1q ´ P p1q, P pn ` 2q ´ P p2q, . . .q “ n.

This is a very Hensel-flavored problem. Take n “ p ą |P 1 paq| for some a ě 1. Then show that the gcd
must be a power of p. p divides the gcd for obvious reasons. If some other prime q divides it, then q divides
P ppq and hence all of P pjpq for j ě 1. But p and q are coprime, so this implies that q | P pnq for all n,
contradiction. Show that the gcd is exactly p by a Hensel-like arguement.

7
 Example 4.9 (2020 USMCA National Championship Premier P6)
Let P be a non-constant polynomial with integer coefficients such that if n is a perfect power, so is
P pnq. Prove that P pxq “ x or P is a perfect power of a polynomial with integer coefficients.
A perfect power is an integer nk , where n P Z and k ě 2. A perfect power of a polynomial is a
polynomial P pxqk , where P has integer coefficients and k ě 2.

I really like this problem, because it shows it brings together all the lemmas developed till now.
Wlog P is monic and let P “ i fi ei be its factorization into irreducibles. We show that the ei ’s have
ś

gcd ą 1, which finishes.

Pick huge primes pi such that νpi fi pni q “ 1 for some ni . (Why can you do this?). We may choose pi
such that pi ∤ fj pnj q for i ‰ j.(why?) Now build a perfect power N such that νpi fi pNq “ 1 (think CRT).
Look at νpi f pNq for all i and conclude.

Example 4.10 (India TST 2019 Test 4 P1)

Determine all non-constant monic polynomials f pxq with integer coefficients for which there exists a
natural number M such that for all n ě M, f pnq divides f p2n q ´ 2f pnq .

Let p | f pnq, so p | f p2n q ´ 2f pnq . Now, shift n ÞÑ n ` p to get that p | f p2n`1 q ´ 2f pn`1q . Thus
p | f p2n q ´ 2f pnq for all n(why?). Take p to be big to show that 2f pnq “ f p2n q for all n ě 1. Show that f
has degree 1 due to size reasons, and conclude.

Example 4.11
For a nonnegative integer n define radpnq “ 1 if n “ 0 or n “ 1, and radpnq “ p1 p2 ¨ ¨ ¨ pk where
p1 ă p2 ă ¨ ¨ ¨ ă pk are all prime factors of n. Find all polynomials f pxq with nonnegative integer
coefficients such that radpf pnqq divides radpf pnradpnq qq for every nonnegative integer n.

Note that radpnk q “ radpnq. So note that if p ∤ n and p | f pnq then p | npp´1q rad n ´ 1, and show that
this implies p | f pn? q ´ f p1q. Choose the power carefully, so that f pn? q “ f pnq pmod pq. So this implies
f p1q “ 0 and you have a contradiction.

8
5 Problems
Problem 5.1 (ELMO 2019 P1). Let P pxq be a polynomial with integer coefficients such that P p0q “ 1,
and let c ą 1 be an integer. Define x0 “ 0 and xi`1 “ P pxi q for all integers i ě 0. Show that there are
infinitely many positive integers n such that gcdpxn , n ` cq “ 1.

Problem 5.2. Find all polynomials f pxq P ZrXs, such that whenever m, n P Z are coprime, so is f pmq, f pnq.

Problem 5.3. Find all polynomials f pxq P ZrXs, such that for all n ě 1, f pnq | nn´1 ´ 1

Problem 5.4. Find all polynomials f pxq P ZrXs, such that for all n ě 1, f pnq | 2n ´ 1

Problem 5.5 (ISL 1995 N1). Let k be a positive integer. Show that there are infinitely many perfect squares
of the form n ¨ 2k ´ 7 where n is a positive integer.

Problem 5.6 (Thailand MO 2020). Determine all polynomials P pxq with integer coefficients which satisfies
P pnq | n! ` 2 for all postive integer n.

Problem 5.7 (Balkan MO 2017 P3). Find all monic polynomials f with integer coefficients satisfying the
following condition: there exists a positive integer N such that p divides 2pf ppq!q ` 1 for every prime p ą N
for which f ppq is a positive integer.

Problem 5.8 (RMM SL 2018 N1). Determine all polynomials f with integer coefficients such that f ppq is
a divisor of 2p ´ 2 for every odd prime p.

Problem 5.9 (APMO 2021 P2). For a polynomial P and a positive integer n, define Pn as the number
of positive integer pairs pa, bq such that a ă b ď n and |P paq| ´ |P pbq| is divisible by n. Determine all
polynomial P with integer coefficients such that Pn ď 2021 for all positive integers n.

Problem 5.10 (USAMO 2006 P3). For integral m, let ppmq be the greatest prime divisor of m. By con-
vention, we set pp˘1q “ 1 and pp0q “ 8. Find all polynomials f with integer coefficients such that the
sequence
` ` ˘˘
tp f n2 ´ 2nuně0
` ˘
is bounded above. (In particular, this requires f n2 ‰ 0 for n ě 0.)

Problem 5.11 (USAMO 1995). Suppose q0 , q1 , q2 , . . . is an infinite sequence of integers satisfying the
following two conditions:
1. m ´ n divides qm ´ qn for m ą n ě 0,

2. there is a polynomial P such that |qn | ă P pnq for all n

Prove that there is a polynomial Q such that qn “ Qpnq for all n.

Problem 5.12 (USA TSTST 2018 P1). As usual, let Zrxs denote the set of single-variable polynomials in
x with integer coefficients. Find all functions θ : Zrxs Ñ Z such that for any polynomials p, q P Zrxs,
‚ θpp ` 1q “ θppq ` 1, and
‚ if θppq ‰ 0 then θppq divides θpp ¨ qq.

9
Problem 5.13 (Balkan SL 2018 N4). Let P pxq “ ad x d ` ¨ ¨ ¨ ` a1 x ` a0 be a non-constant polynomial with
non-negative integer coefficients having d rational roots.Prove that
ˆ ˙
n
lcm pP pmq, P pm ` 1q, . . . , P pnqq ě m
m

for all n ą m

Problem 5.14 (Generalised Hensel). Let f pxq P ZrXs and a P Z. Let p be a prime, and let m “ νp pf 1 paqq.
If p 2m`1 | f paq, prove that f has exactly one root b pmod p k q which is congruent to a pmod p m`1 q for all
k ě 2m ` 1.

Problem 5.15 (Balkan 2023 P3). For each positive integer n, denote by ωpnq the number of distinct prime
divisors of n (for example, ωp1q “ 0 and ωp12q “ 2). Find all polynomials P pxq with integer coefficients,
such that whenever n is a positive integer satisfying ωpnq ą 20232023 , then P pnq is also a positive integer
with
ωpnq ě ωpP pnqq.

Problem 5.16. Determine all non-constant monic polynomials P pxq P ZrXs such that no prime p ą 102024
divides any number of the form P p2n q.

Problem 5.17 (Putnam 2008 N4). Let p be a prime number. Let hpxq be a polynomial with integer
coefficients such that hp0q, hp1q, . . . , hpp 2 ´ 1q are distinct modulo p 2 . Show that hp0q, hp1q, . . . , hpp 3 ´ 1q
are distinct modulo p 3 .

Problem 5.18 (China TST 2021). Let f pxq, gpxq be two polynomials with integer coefficients. It is known
that for infinitely many prime p, there exist integer mp such that

f paq ” gpa ` mp q pmod pq

holds for all a P Z. Prove that there exists a rational number r such that

f pxq “ gpx ` r q.

Problem 5.19 (Canada 2010 P5). Let P pxq and Qpxq be polynomials with integer coefficients. Let an “
P pan q P pnq
n! ` n. Show that if Qpan q is an integer for every n, then Qpnq is an integer for every integer n such that
Qpnq ‰ 0.

Problem 5.20 (IMO SL 2011 N6). Let P pxq and Qpxq be two polynomials with integer coefficients, such
that no nonconstant polynomial with rational coefficients divides both P pxq and Qpxq. Suppose that for
every positive integer n the integers P pnq and Qpnq are positive, and 2Qpnq ´ 1 divides 3P pnq ´ 1. Prove that
Qpxq is a constant polynomial.

Problem 5.21 (USEMO 2019 P5). Let Zrxs denote the set of single-variable polynomials in x with integer
coefficients. Find all functions θ : Zrxs Ñ Zrxs (i.e. functions taking polynomials to polynomials) such that
‚ for any polynomials p, q P Zrxs, θpp ` qq “ θppq ` θpqq;
‚ for any polynomial p P Zrxs, p has an integer root if and only if θppq does.

10
Problem 5.22 (USA TST 2020 P5). Find all integers n ě 2 for which there exists an integer m and a
polynomial P pxq with integer coefficients satisfying the following three conditions:
‚ m ą 1 and gcdpm, nq “ 1;
‚ the numbers P p0q, P 2 p0q, . . ., P m´1 p0q are not divisible by n; and
‚ P m p0q is divisible by n.
Here P k means P applied k times, so P 1 p0q “ P p0q, P 2 p0q “ P pP p0qq, etc.

Problem 5.23 (IMO SL 2005 N7). Let P pxq “ an x n ` an´1 x n´1 ` . . . ` a0 , where a0 , . . . , an are integers,
an ą 0, n ě 2. Prove that there exists a positive integer m such that P pm!q is a composite number.

Problem 5.24 (USA TST 2008 P6). Let n be a positive integer. Given an integer coefficient polynomial
f pxq, define its signature modulo n to be the (ordered) sequence f p1q, . . . , f pnq modulo n. Of the nn such
n-term sequences of integers modulo n, how many are the signature of some polynomial f pxq if
1. n is a positive integer not divisible by the square of a prime.

2. n is a positive integer not divisible by the cube of a prime.

Problem 5.25 (ELMO 2022 P2). Find all monic nonconstant polynomials P with integer coefficients for
which there exist positive integers a and m such that for all positive integers n ” a pmod mq, P pnq is nonzero
and
pn ` 1qn`1 ´ nn
2022 ¨
P pnq
is an integer.
řt qp u p´1
Problem 5.26 (RMM SL 2016). Given a prime p, prove that the sum k“1 k is not divisible by q for
all but finitely many primes q.

Problem 5.27 (China MO 2016 P3). Let p be an odd prime and a1 , a2 , ..., ap be integers. Prove that the
following two conditions are equivalent:
p´1
1. There exists a polynomial P pxq with degree ď 2 such that P pi q ” ai pmod pq for all 1 ď i ď p
p´1
2. For any natural d ď 2 ,
p
ÿ
pai`d ´ ai q2 ” 0 pmod pq
i“1

where indices are taken pmod pq

Problem 5.28 (ELMO 2018 SL N5). Say a positive integer n ą 1 is d-coverable if for each non-empty
subset S Ď t0, 1, . . . , n ´ 1u, there exists a polynomial P with integer coefficients and degree at most d
such that S is exactly the set of residues modulo n that P attains as it ranges over the integers. For each
n, find the smallest d such that n is d-coverable, or prove no such d exists.

Problem 5.29 (RMM 2010 P6). Given a polynomial f pxq with rational coefficients, of degree d ě 2, we
define the sequence of sets f 0 pQq, f 1 pQq, . . . as f 0 pQq “ Q, f n`1 pQq “ f pf n pQqq for n ě 0. (Given a set
S, we write f pSq for the set tf pxq | x P Suq. Let f ω pQq “ 8 n
Ş
n“0 f pQq be the set of numbers that are in all
of the sets f n pQq, n ě 0. Prove that f ω pQq is a finite set.

11
Problem 5.30. Find all pairs of integers pc, dq, both greater than 1, such that the following holds:
For any monic polynomial Q of degree d with integer coefficients and for any prime p ą cp2c ` 1q, there
` ˘
exists a set S of at most 2c´1
2c`1 p integers, such that
ď
ts, Qpsq, QpQpsqq, QpQpQpsqqq, . . . u
sPS

contains a complete residue system modulo p (i.e., intersects with every residue class modulo p).

Problem 5.31 (Korea 2016). ppxq is an irreducible polynomial with integer coefficients, and q is a fixed
prime number. Let an be a number of solutions of the equation ppxq ” 0 mod q n .
Prove that we can find M such that tan uněM is constant.

Problem 5.32 (Korea 2019). Find all polynomials P pxq with integer coefficients such that for all positive
number n and prime p satisfying p ∤ nP pnq, we have or dp pnq ě or dp pP pnqq.

12
6 Solutions to Examples

6.1 Example 4.1

Since P is non-constant, pick c such that P pcq ‰ ˘1. Then for any d “ c pmod pq, p | P pdq as well. If d
is sufficiently large, |P pdq| ą p, so it is composite, as required.

6.2 Example 4.2

(Solution by Ankoganit on aops) Let p and q be two odd primes. Note that pq|P p2pq q ùñ p|P p2pq q ùñ
P p2pq q ” 0 pmod pq. Now we have by Fermat’s little theorem 2pq ” p2q qp ” 2q pmod pq, so using a
well-known property of integer polynomials, we have

0 ” P p2pq q ” P p2q q pmod pq ùñ p|P p2q q .

Now in the last divisibility relation, taking p large enough forces P p2q q “ 0. But this is true for arbitrary
odd prime q, so P pxq “ 0 for infinitely many x. This forces that P is identically zero, as desired.

6.3 Example 4.3

Write ak “ bk2 . Take b1 “ 5, so that 13 | b12 ` 1. Next note that 13 ∤ 2 ¨ 5 “ 10, so by Hensel’s lemma,
there exists a sequence bk satisfying 13k | bk2 ` 1, and bk`1 ” bk pmod p k q. It is easy to see that we may
choose the bi to be increasing.

6.4 Example 4.4

Assume P is non-constant, then there exists a large odd prime p dividing P pnq for some n. Then, note that,
if p | P 1 pnq, then Hensel causes a problem. So whenever p | P pnq, p | P 1 pnq as well. Thus gcdpP pnq, P 1 pnqq
is unbounded. But P can not have a double root, so P, P 1 are coprime. Contradiction.

6.5 Example 4.5

(solution by Assassino9931 on aops) If P is constant, it can only be any fixed prime, suppose P is non-
constant.
Having in mind the classical lemma A ´ B | P pAq ´ P pBq for any integers A and B, setting A “ P pnq ` n
and B “ n in it yields that P pnq divides P pP pnq ` nq ´ P pnq, i.e. P pnq divides P pP pnq ` nq. Therefore (as
P pnq “ ˘1 for finitely many n, since a non-zero polynomial has finitely many roots) P pP pnq ` nq “ ˘P pnq
for infinitely many n and hence at least one of P pP pnq ` nq “ P pnq and P pP pnq ` nq “ ´P pnq holds for
infinitely many n.
If deg P “ k ě 1, then supposing k ě 2 would yield degpP pnq ` nq “ k, deg P pP pnq ` nq “ k 2 and so
k 2 “ k, contradiction.

13
 Finally, if k “ 1, i.e. P pnq “ an ` b with a ‰ 0, then going back to the problem condition P pP pnq ` nq “
P ppa ` 1qn ` bq “ apa ` 1qn ` ab ` b “ pa ` 1qpan ` bq. Since |an ` b| ą 1 when n is large, we must have
a ` 1 “ ˘1, thus a “ ´2 (as a ‰ 0); conversely, if P pnq “ ´2n ` b, then P pP pnq ` nq “ ´2n ` b and this
is prime infinitely often only when b is odd (the equality ´2n ` b “ ´p for a large prime p is achievable by
b`p
n“ 2 ).

6.6 Example 4.6

We claim that only linear polynomials work. It is easy to see that they do . We now prove that they are the
only ones that satisfy the property.
First, we prove a claim.

Claim 6.1. If p is a large prime and integer m, n satisfy p | P pmq ´ P pnq, then p | m ´ n.

Proof : Consider P p0q, P p1q, . . . , P pp ´ 1q modulo p. (It is enough to consider these because p |
P pn ` pq ´ P pnq.) We are told that this list contains all residues mod p. Since our list is p numbers long,
each residue appears exactly once. Thus, if P pmq ” P pnq pmod pq, then m ” n pmod pq, as desired.
def
Set Qpxq :“ P px ` 1q ´ P pxq . Assuming Qpxq to be non-constant , note that if a large prime p | Qpkq
for some k then p | pk ` 1q ´ k “ 1 , absurd . Hence Qpxq does not have a root modulo all sufficiently large
primes. However this violates Schur’s theorem , so Qpxq is a constant polynomial.
Hence P px ` 1q ´ P pxq “ c ùñ P is linear

6.7 Example 4.7

(solution by pad on aops) Assume P is nonconstantWe know by Schur’s lemma that infinitely many primes
p divide P pnq as we vary n. So let p | P pnq for some n such that p ∤ a1 , . . . , a2019 . We have

p | P pnq | a1n ` ¨ ¨ ¨ ` a2019

n
ùñ a1n ` ¨ ¨ ¨ ` a2019
n
”0 pmod pq.

But p | P pnq, so p | P pn ` pq as well, hence

n`p
p | P pn ` pq | a1n`p ` ¨ ¨ ¨ ` a2019 .

However,
0 ” a1n`p ` ¨ ¨ ¨ ` a2019
n`p
” a1n`1 ` ¨ ¨ ¨ ` a2019
n`1
pmod pq.

Continuing in this logic, we get a1N `¨ ¨ ¨`a2019

N ” 0 pmod pq for any N ě n. Now plug in N “ 100npp´1q ą n
100npp´1q
into the aforementioned assertion, and we get aiN “ ai ” 1 pmod pq by FLT, since we assumed
ai ı 0 pmod pq for any i . Hence 0 ” 2019 pmod pq, which means there are finitely many possibilities for p,
contradicting Schur’s lemma. Therefore, P is constant.

6.8 Example 4.8

(solution by anantmudgal09 on aops) All prime numbers n “ p ą |P 1 paq| ą 0 satisfy the condition, where a
is some positive integer.

14
 First, n | P pn ` kq ´ P pkq for all k ě 1 so n is a factor of that gcd, say, gn . If q | gn is a prime and q ∤ n
then we have
P pjnq ” P ppj ´ 1qnq ” ¨ ¨ ¨ ” P p0q “ 0 pmod qq.

However, tjnujě1 spans all residues mod q so q divides all values P takes over inputs from N, contradiction!
Also, if p 2 | gn then we have, by Taylor’s expansion,

0 ” P pn ` aq ´ P paq ” nP 1 paq pmod p 2 q,

which fails due to size conditions on n. Hence, infinitely many n satisfy this condition.

6.9 Example 4.9

(solution by amuthup on aops)

Claim. For every positive integer n, all residues relatively prime to n are perfect powers modulo n.

Proof: Write n “ p1e1 p2e2 . . . pkek . Pick m such that gcdpm, ϕppiei qq “ 1 for all i . It follows that x m is
surjective (among coprime residues) for all prime powers dividing n, so we are done. ■

Claim. If f P Zrxs is irreducible, then for infinitely many primes p, there exists n such that νp pf pnqq “ 1.

Proof: Since f is irreducible, f , f 1 have no common factors. Therefore, by Bezout, there exist P, Q P Zrxs
and R P Z such that P f ` Qf 1 “ R. Now, by Shortlist 2009 N3, we may pick a prime p ą |R| dividing f pnq
for some n. We may assume WLOG that νp pf pnqq ą 2, and since p ∤ R, we know p ∤ f 1 pnq.

To finish, note that by the Binomial Theorem, f pn ` pq ” f pnq ` pf 1 pnq ” pf 1 pnq pmod p 2 q. This im-
plies that νp pf pn ` pqq “ 1, so we are done. ■

Claim. Suppose f , g P Zrxs have no common factors. Then, for sufficiently large primes p, there is no n
such that f pnq ” gpnq ” 0 pmod nq.

Proof: We can find the greatest common factor of f , g in both Fp rxs and Zrxs using the Euclidean
Algorithm, which takes only finitely many steps. Therefore, if we take p to be larger than all coefficients
that appear in this process, the greatest common factor of f , g in Fp rxs will be the same as it is in Zrxs.

Therefore, for sufficiently large primes, f , g share no common factors in Fp rxs, which gives the desired
statement. ■

śk
Now write P pxq “ cx e i“1 fi pxq
ei for irreducible f1 , f2 , . . . , fk P Zrxs, nonnegative e, and positive e1 , e2 , . . . , ek .

Choose sufficiently large primes p1 , p2 , . . . , pk , and choose n1 , n2 , . . . , nk such that νpi pfi pni qq “ 1 (this

15
is possible by Claim 2). Since we can choose pi ą |fi p0q| for all i , we know that pi ∤ ni for all i . Therefore, by
Claim 1 and CRT, we can choose a perfect power N such that N ” ni pmod pi2 q for all i . Finally, by Claim
3, at most one of f1 pNq, f2 pNq, . . . , fk pNq can be divisible by any given p P tp1 , p2 , . . . , pk u.

Thus, νpi pf pNqq “ ei for all i . This implies that gcdpe1 , e2 , . . . , ek q “ d ą 1. Now it is easy to check
that we must have d | e and c “ 1, as desired.

6.10 Example 4.10

(solution by TheDarkPrince on aops) As f is non-constant polynomial and M is finite, number of primes
dividing one of f pMq, f pM ` 1q, . . . is infinite from Schur’s theorem. Say p is a prime from one of the primes.
We have
p | f pnq ùñ p | f pn ` pq | f p2n`p q ´ 2f pn`pq ” f p2n`1 q ´ 2f pn`1q pmod pq.

This gives us p | f p2n`k q ´ 2f pn`kq for all naturals k. Further taking the modulo again gives us p |
f p2n`k pmod p´1q q ´ 2f pn`k pmod p´1qq , so p | f p2n q ´ 2f pnq for all n. Therefore we get f p2n q “ 2f pnq for all
non-negative integers n.
Now we have 2k | 2k`n | f p2k`n q ´ f p0q “ 2f pk`nq ´ f p0q for all non-negative integers n, k. Now for any
given k, as f has leading term positive and f is non-constant, we can pick a sufficiently large n such that
f pn ` kq ą k. Therefore 2k | 2f pn`kq ´ f p0q, so 2k | f p0q for all k which gives us f p0q “ 0. Now using this
in f p2n q “ 2f pnq , we get f p2n q “ 2n . As f is polynomial this gives us f pxq “ x is the only solution.

6.11 Example 4.11

(solution by IndoMathXDZ on aops, slightly edited)
We’ll use the following fact throughout the entire solution:

radpnk q “ radpnq

Now, notice that if p|n and p|f pnq, then we have p|n|f pnq ´ f p0q, which gives us f p0q “ 0. Otherwise, if
p ∤ n and p|f pnq, we have

p|npp´1qradpnq ´ 1|f pnpp´1qradpnq q ´ f p1q “ f pnradpnq q ´ f p1q “ f pnradpnqk q ´ f p1q

Taking n ÞÑ n ` r p if required, and picking k suitably such that p ´ 1 | trad f pnquk ´ 1, then this gives us
p|f p1q, since
p|radpf pnqq|radpf pnradpnq q

Now, consider f pxq “ x n gpxq for some nonzero integer n, such that pgpxq, xq “ 1. Since gp0q is a nonzero
constant, then we can have infinitely many primes p ∤ gp0q but p|gpnq if g is nonconstant. This gives us
f p0q ­“ 0, but f p1q “ 0, a contradiction as f is a nonnegative integer coefficient polynomial. Thus, g must
be a constant and therefore, we have the solution

f pnq “ cnd where c, d P Zě 0

16