Polynomials that divide factorials

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Polynomials that divide factorials

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: 2023 Thailand Mock IMO P4

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

49 posts

psi241

#1 h Jun 1, 2023, 8:06 AM

Y by

Find all polynomials $P(x)$ with integer coefficients for which there exists an integer $M$ such that $P(n)$ divides $(n+2023)!$ for all positive integers $n>M$ .

Pitchayut Saengrungkongka

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

800 posts

#2 h Jun 1, 2023, 9:39 AM • 2 Y

Y by GeoKing, duotran

psi241 wrote:

Find all polynomials $P(x)$ with integer coefficients for which there exists an integer $M$ such that $P(n)$ divides $(n+2023)!$ for all positive integers $n>M$ .

Pitchayut Saengrungkongka

Quite similar in taste to USAMO 2006 P3, unless I am mistaken. I apologize if I was rude at some point of this solution, or if my solution is wrong (I dont want to get flamed lol).

Let us first consider a somewhat "weaker" version of the problem:

Quote:

Let $p(m)$ be the largest prime factor of $m$ where $m$ is an integer, and let $p(\pm1)=1$ , and $p(0)=\infty$ . Find all polynomials $f\in\mathbb{Z}[x]$ such that the sequence $\{p \left( f \left( n\right) \right) - n \}_{n \geq 0}$ is bounded above.

As in the solution to USAMO 2006 P3, let us assume that $f$ is an irreducible polynomial over $\mathbb{Z}[x]$ .

First things first, if $p\mid f(n)$ for some positive integer $n$ , we can conclude that $p\mid f(r)$ where $r$ is the remainder of $n$ when it's divided upon $p$ . Back to the problem, from schur's theorem, we have that infinitely many odd primes divide $f(n)$ , so picking one of them, say $p$ , if $p\mid f(n)$ , we can, without losing generality assume that $1\leq n\leq p$ . That means, if $q = p(f(n))$ , then as $q\geq p\geq n$ , we have that $q$ is in between $n$ and $n+2023$ .

We now proceed as follows: for each prime number $q$ which is among the infinite sequence of primes dividing $f(n)$ and is sufficiently large, set $q'$ to be that positive integer such that $q$ is the largest prime divisor of $f(q')$ and that $1\leq q'\leq q$ . Since $q$ is also at most $q+T$ where T is a fixed constant for all such $q'$ , we can conclude the existence of an integer $0\leq \lambda\leq T$ so that $q=q'+\lambda$ for infinitely many $q'$ , which means that $q = q'+\lambda$ divides $f(q')$ for infinitely many $q'$ , and therefore, we can conclude that $n+\lambda$ divides $f(n)$ for all integers $n$ . Since we assumed that $f$ is irreducible over $\mathbb{Z}[x]$ , we can conclude that $f(n)=n+\lambda$ for all positive integers $n$ . Freeing the irreducibility condition, we can conclude that $f$ is a product of linear polynomials.

Now getting back to the strengthened version of the problem, we know clearly that $P(n)$ is of the form $a(n+a_1)\hdots(n+a_m)$ . Clearly none of these $a_i$ can exceed $2023$ , as otherwise, we can pick $n$ so that $n+a_i$ is prime, defying the hypothesis of the problem. Assume now that $a_i=a_j$ for some $1\leq i,j\leq m$ . Then, $(n+a_i)^2\mid (n+2023)!$ , but choosing $n$ extremely large so that $n+a_i$ is prime, rises a contradiction, since if $n+a_i$ as a prime occurs twice in the contiguous sequence from $1$ to $n+2023$ , then $2n+2a_i$ must occur in that sequence as well, impossible.

I claim now that all polynomials $P$ that can be decomposed into the form $a(n+a_1)\hdots(n+a_m)$ work, where $a_i\leq 2023$ for all $1\leq i\leq m$ and no two $a_i$ are equal. Indeed, choose M so that $M > \max_{1\leq i\leq m}{\lvert a_i\rvert} + a$ , then as $a,n+a_1,\hdots, n+a_m$ are all in between $1$ and $n+2023$ for all $n>M$ , their product must divide $(n+2023)!$ , solving the problem.

Conclusively, all solutions are of the form $f(n)=a(n+a_1)\hdots(n+a_m)$ where $a_i\leq 2023$ for each $1\leq i\leq m$ , no two $a_i$ are equal, where $m$ is any positive integer.

This post has been edited 2 times. Last edited by rama1728, Jun 1, 2023, 9:41 AM
Reason: .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1184 posts

L567

#3 h Jun 1, 2023, 9:55 AM

Y by

Suppose $P(x)$ has a factor without any integral roots . Then there exist infinitely many primes that divide some term of the form $P(n)$ , but also do not divide $P(0), P(-1), P(-2), \cdots, P(-2023)$ as well as $P(1), P(2), \cdots, P(M)$ . Let $q$ be such a prime much larger than $M$ and say $q \mid P(r)$ with $r$ minimal. Note that it is impossible that there exists $n$ such that $n \equiv r \pmod{q}$ and $n + 2023 < q$ . Therefore, we must have that $r + k = q$ for some $k \in \{1,2,\cdots,2023\}$ or that $r < M$ . By PHP, for some $k$ , there are infinitely many such primes. This means that $P(-k) \equiv P(r) \equiv 0 \pmod{q}$ for infinite primes $q$ , implying $P(-k) = 0$ , contradiction.

So all factors are of the form $n + C$ . Note that $C \geqslant 2024$ cannot happen by picking $n$ such that $n+C$ is a large prime. Further, note that no root can be repeated, as if $(n+C)^2 \mid P(n) \mid (n+2023)!$ , picking $n+C$ to be a large enough prime gives a contradiction as $p^2 \mid (n+C)^2$ but $p^2 \nmid (n+2023)!$ .

This gives the solution set that given an integer $\ell$ and distinct integers $a_1, a_2, \cdots, a_k$ all at most $2023$ , then $P(x) = \ell \cdot \prod_{i=1}^k(x+a_i)$ which can easily be seen to work, so done. $\blacksquare$

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a