Integer Coefficient Polynomial with order

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

Integer Coefficient Polynomial with order

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: 2019 Korea Winter Program Practice Test 1 Problem 3

The post below has been deleted. Click to close.

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

644 posts

#1 h Jan 12, 2019, 11:36 AM • 2 Y

Y by Superguy, Adventure10

Find all polynomials $P(x)$ with integer coefficients such that for all positive number $n$ and prime $p$ satisfying $p\nmid nP(n)$ , we have $ord_p(n)\ge ord_p(P(n))$ .

This post has been edited 1 time. Last edited by MNJ2357, Jan 12, 2019, 10:17 PM

Z K Y

The post below has been deleted. Click to close.

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

894 posts

#2 h Jan 15, 2019, 4:07 PM • 2 Y

Y by Adventure10, Mango247

Wrong, thanks to post below for pointing out :stretcher:

:stretcher:

This post has been edited 3 times. Last edited by stroller, Jan 16, 2019, 2:00 AM

Z K Y

The post below has been deleted. Click to close.

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

615 posts

#3 h Jan 15, 2019, 11:37 PM • 2 Y

Y by stroller, Adventure10

stroller wrote:

The given condition translates to $p | n- \omega_k \implies p | P(n)^k -1$

Shouldn't this be $p \mid P(n)^m - 1$ for some $m \leq k$ ?

Z K Y

The post below has been deleted. Click to close.

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

894 posts

#4 h Jan 16, 2019, 1:10 AM • 1 Y

Y by Adventure10

fattypiggy123 wrote:

stroller wrote:

The given condition translates to $p | n- \omega_k \implies p | P(n)^k -1$

Shouldn't this be $p \mid P(n)^m - 1$ for some $m \leq k$ ?

Sorry my mistake; I misread the problem as $\text{ord}_p(P(n))|\text{ord}_p(n)$

Z K Y

The post below has been deleted. Click to close.

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

894 posts

#5 h Jan 16, 2019, 1:52 AM • 2 Y

Y by Adventure10, Mango247

My fix for the error pointed out in post #3.

What I was most concerned about being incorrect

This post has been edited 1 time. Last edited by stroller, Jan 16, 2019, 1:55 AM

Z K Y

The post below has been deleted. Click to close.

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

615 posts

#6 h Jan 16, 2019, 3:12 AM • 4 Y

Y by Kayak, stroller, Adventure10, Mango247

Yes your solution has a few points of contention, for instance $\omega_k$ starts off life as an element of $\mathbb{F}_p$ but somehow becomes an actual complex root of unity halfway through. All of this can be fixed/made rigorous by some algebraic number theory. I will post more on it when I am free.

Z K Y

The post below has been deleted. Click to close.

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

615 posts

#7 h Jan 16, 2019, 9:06 AM • 7 Y

Y by Loppukilpailija, stroller, MNJ2357, Gaussian_cyber, Superguy, Adventure10, Mango247

The main idea to stroller's solution is to attempt to lift the local conditions, $P(u_p) \equiv v_p \pmod p$ where $u_p,v_p$ are integers satisfying $u_p^k , v_p^m \equiv 1 \pmod p$ , into a global condition $p \mid P(x) - y$ for some numbers $x,y$ to deduce that $P(x) - y = 0$ since it cannot have infinitely many distinct prime factors. For instance if $k = m = 1$ , then we can simply choose $x = y = 1$ . The problem comes when $k$ and $m$ are larger than $2$ and one cannot find any integer $x$ such that $x^k \equiv 1 \pmod p$ for infinitely many primes $p$ where $x \not = 1$ . As indicated in stroller's solution, we should bring in the complex primitive roots of unity $\omega_k$ and $\omega_m$ . For simplicity, I will just assume $m = k$ .

Now there is a natural place (but not the only one!) to do arithmetic with $\omega_k$ . The field $\mathbb{Q}(\omega_k)$ is a number field and so its ring of integers is a Dedekind domain. When working beyond $\mathbb{Z}$ , it is known that we cannot hope for unique factorization of integers to continue to hold. What one can achieve however is unique factorization into ideals, which is a property that Dedekind domains possess (and can also be taken as its defining property) and so makes Dedekind domains a nice place to do arithmetic in. In the case of $\mathbb{Q}(\omega_k)$ , its ring of integers is simply $\mathbb{Z}[\omega_k]$ , which is just sums of $\omega_k^i$ with $\mathbb{Z}$ -coefficients.

For a prime $p$ , let $\mathbb{F}_q$ be the smallest field extension of $\mathbb{F}_p$ where you have a primitive $k^{th}$ root of unity. This always exists if say $p \nmid k$ . Then just like how in the usual integers $\mathbb{Z}$ , we have the "reduction mod p" maps from $\mathbb{Z}$ to $\mathbb{F}_p$ , there will exist reduction maps from $\mathbb{Z}[\omega_k]$ to $\mathbb{F}_q$ for each such $q$ where $\omega_k$ is sent to one of the primitive $k^{th}$ roots of unity in $\mathbb{F}_q$ . When $p \nmid k$ , the ideal $(p)$ in $\mathbb{Z}[\omega_k]$ factors as a product of distinct prime ideals $\mathfrak{p}_1 \cdots \mathfrak{p}_g$ . These reduction maps then arise from reducing modulo $\mathfrak{p}_i$ instead of just mod $p$ .

For example, if we work over the Gaussain integers $\mathbb{Z}[i]$ instead then we are looking at field extensions $\mathbb{F}_q$ where $x^2 = -1$ has a solution. For $p = 3$ , there are no solutions within $\mathbb{F}_3$ itself and so we have to extend to $\mathbb{F}_9$ , the field with $9$ elements. Correspondingly, the element/ideal $(3)$ is prime in $\mathbb{Z}[i]$ and so the map $\mathbb{Z}[i] \to \mathbb{F}_9$ arises from $a + bi \mapsto a \pmod 3 + b \pmod 3 i$ . You can check that there are then $9$ elements just like $\mathbb{F}_9$ . Howeverfor $p = 5$ , within $\mathbb{F}_5$ there is already a solution to $x^2 = -1$ and so $\mathbb{F}_q = \mathbb{F}_5$ . Our map $\mathbb{Z}[i] \to \mathbb{F}_5$ can't be just reducing mod $5$ then as that will give us $25$ elements instead. Instead one should factor $(5) = (2+i)(2-i)$ and then reduce mod $(2+i)$ or $(2-i)$ . Since $x^2 + 1 = 0$ has two solutions in $\mathbb{F}_5$ , there are two possible elements one can map $i$ to and each mod corresponds to one of them.

As a result, we can lift the local conditions to get for each $p \equiv 1 \pmod k$ , there is one prime ideal factor $\mathfrak{p}$ of the ideal $(p)$ that divides $P(\omega_k) - \omega_k^m$ which implies that it must be $0$ by unique factorization of ideals.

Z K Y

The post below has been deleted. Click to close.

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

1595 posts

#8 h Jan 21, 2019, 6:21 AM • 3 Y

Y by stroller, Gaussian_cyber, Adventure10

Here is alternative way to make stroller's solution rigorous, using elementary method. We will prove that $P(\omega_k)^{k!}=1$ .

The key idea is to transfer from $\mathbb{Q}(\omega_k)$ to $\mathbb{Z}_p$ properly. However, the difficulty is $\omega_k$ is defined through roots of polynomials, which means we don't know the order of root. We will circumvent this issue by using symmetric polynomials instead.

Fix a positive integer $n$ and let $m=\varphi(n)$ . Let $\omega_1, \omega_2, ...,\omega_m$ be primitive $n$ -th root unity. By Newton's theorem on polynomial on symmetric polynomial, polynomial
$Q(X) = (X-P(\omega_1))(X-P(\omega_2))...(X-P(\omega_m))$ has integer coefficients.

Fix a prime $p\equiv 1\pmod n$ and working on $\mathbb{F}_p[X]$ . Let $a_1,a_2,...,a_m$ be all residues $\pmod p$ having order $n$ . We claim that

Claim 1 : Let
$Q^*(X) = (X-P(a_1))(X-P(a_2))...(X-P(a_m))$ then $Q^*(X) - Q(X)$ has all coefficients divisible by $p$ .

Proof : Let $e_1, e_2,...,e_m$ be Elementary symmetric polynomials of $m$ variables. Then in $\mathbb{F}_p[X]$ ,
$(X-a_1)(X-a_2)...(X-a_m) = \varPhi_n(X) = (X-\omega_1)(X-\omega_2)...(X-\omega_m)$ Thus comparing coefficients give $e_i(a_1,a_2,...,a_m) \equiv e_i(\omega_1,\omega_2,...,\omega_m) \pmod{p}$ for any $i=1,2,...,m$ . (Recall that both numbers are integer!). Therefore, by Newton's theorem on symmetric polynomial,
$e_i(P(a_1),P(a_2),...,P(a_m)) \equiv e_i(P(\omega_1),P(\omega_2),...,P(\omega_m)) \pmod p$ implying the result.

Claim 2 : $Q^*(X)$ divides $X^{n!}-1$ (in $\mathbb{F}_p[X]$ ).

Proof : Since $\mathrm{ord}_p(a_1) = n$ , we have $\mathrm{ord}_p(P(a_1))\leqslant n$ or $P(a_1)^{n!}\equiv 1\pmod p$ . Hence each root of $Q^*(X)$ is root of $X^{n!}-1$ , done.

Now we are ready to shift the local conditions into global conditions. Since $Q(X)$ must congruent to $Q*(X)$ in $\mathbb{F}_p[X]$ , polynomial $Q(X)$ must congruent to some divisor of $X^{n!}-1$ in $\mathbb{F}_p[X]$ .

By Pigeonhole's principle there exists infinitely many prime $q\equiv 1\pmod n$ which $Q(X)$ is congruent to same divisor $R(X)$ of $X^{n!}-1$ in $\mathbb{F}_q[X]$ . This force all coefficients of $Q(X)-R(X)$ to be divisible by infinitely many prime $q$ . Hence $Q(X) = R(X)\mid X^{n!}-1$ , implying $P(\omega_i)^{n!} = 1$ as desired.

Z K Y

The post below has been deleted. Click to close.

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

202 posts

#9 h Jan 23, 2019, 12:52 AM • 2 Y

Y by Adventure10, Mango247

Here's another elementary solution:

Fix $n$ , and let $p$ vary across all primes equivalent to $1\bmod n$ . Now, for all $x$ for which $x^n\equiv 1\bmod p$ , we have

$P(x)^{n!}\in\{0,1\}\bmod p\implies P(x)^{n!+1}-P(x).$
(we get $1$ if we can apply our condition and otherwise we get $0$ ). Let $Q(x)=P(x)^{n!+1}-P(x)$ , and write

$Q(x)=R(x)+S(x)(x^n-1)$
where $\deg(R)<n$ (we do this in $\mathbb{Z}[x]$ ). Now, for all $p\equiv 1\bmod n$ , we have that $Q(x)\equiv 0\bmod p$ if $x^n=\equiv 1\bmod p$ , which means that $R(x)\equiv 0\bmod p$ . As $R$ has $n$ roots in $\mathbb{F}_p$ and it is of degree $\leq n-1$ , we have that $R$ must be equivalent to the zero polynomial $\bmod p$ , and thus all of the coefficients of $R$ are divisible by $p$ . Now, as this holds for infinitely many $p$ , we see that $R(x)$ is identically $0$ , or that

$x^n-1\big|P(x)^{n!+1}-P(x).$
This implies that, if $x=\zeta_n$ is a primitive $n$ th root of unity,

$P(\zeta_n)=0\mathrm{\ or\ }P(\zeta_n)^{n!}=1\implies |P(\zeta_n)|=1.$
One of these two criteria must hold for infinitely many $n$ . If it is the first, then $P$ has infinitely many roots and is identically $0$ . If it is the second, then, letting $d$ be the degree of $P$ ,

$P(z)z^dP\left(\frac{1}{z}\right)=z^d$
holds for infinitely many $z$ ; as this is a polynomial equation these must be identical as polynomials. We claim the only solutions to this are of the form $\pm x^d$ . Assume we have a counterexample $P$ with minimal degree. As $P(x)/x$ would be a counterexample if $P(0)$ were equal to $0$ , we conclude that $P(0)\neq 0$ . However, as $z\to\infty$ ( $z$ real), the left side is of order $P(0)z^d(cz^d)$ ( $c$ is the leading coefficient) while the right side is $z^d$ , allowing us to conclude (as $cP(0)\neq 0$ ), that $d=0$ and $P$ is constant, which implies that if $P\equiv c$ we have $c^2=1$ , which is exactly our solution set. Now, if $P(x)=x^d$ we have a valid solution and if $P(x)=-x^d$ we have a contradiction at $n=1$ and $p=3$ , so the only solutions are $P(x)=0$ and $P(x)=x^d$ , finishing the proof.

Z K Y

The post below has been deleted. Click to close.

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

6877 posts

#10 h Apr 5, 2025, 2:44 AM • 1 Y

Y by ihategeo_1969

Solution from Twitch Solves ISL:

The answer is $P(n) = n^{d}$ only for $d \ge 0$ , which clearly works.
For the other direction, we assume $P$ is nonconstant, and let $\ell$ be a large prime, say $\ell > 100 (\deg P + 100)^2$ .

Claim: For this prime $\ell$ , we have a divisibility of ${\mathbb Z}[X]$ -polynomials $\Phi(X) \coloneqq X^{\ell-1} + X^{\ell-2} + \dots + 1 \mid P(X)^\ell - 1.$ Proof. Because $\Phi$ is irreducible and has large degree, it is coprime to both $P(n)$ and $P(n) \pm1$ . Then there exists a constant $C$ such that $\gcd(\Phi(n), P(n)(P(n)^2-1)) \le C$ for all $n$ , by Bezout.
Consider large primes $p > C$ such that

$p \not\equiv 1 \pmod q$ for any prime $3 \le q < \ell$ ,
$p \equiv 1 \pmod \ell$ .

There are infinitely many such primes by Dirichlet. For each such $p$ , we can find $n$ such that $p \mid \Phi(n)$ , simply by taking $g$ to be a primitive modulo $p$ , and choosing $n = g^{\frac{p-1}{\ell}}$ .
For that $n$ we have $p \mid n^\ell-1$ , so the order of $n$ is at most $\ell$ . Consequently, $p$ divides $P(n) \cdot (P(n)-1) \cdot (P(n)^2-1) \cdot \dots \cdot (P(n)^{\ell}-1).$ Now $p$ has to divide these factors. It doesn't divide $P(n)$ as $p > C$ . And if it divided $P(n)^k-1$ for some $k < \ell$ , then the order of $P(n)$ modulo $p$ would be a divisor of $k$ . But it should also divide $\ell-1$ , and because of constraints on $p$ this would be force the order to be at most $2$ . From $p > C$ , that's impossible too. Hence $p$ divides $P(n)^\ell-1$ , the last factor.
In other words, we have shown there are arbitrarily large primes such that $p$ divides $\Phi(n)$ and $P(n)^\ell-1$ for some $\ell$ . Hence (via the same Bezout argument) it follows $\Phi(X)$ is not coprime to $P(X)^\ell-1$ and hence divides it. $\blacksquare$
Now let $\zeta$ be a primitive $\ell$ th root of unity. Then $P(\zeta)$ is an $\ell$ th root of unity as well, so $P(\zeta) - \zeta^d = 0.$ for some integer $r$ , say $0 \le d \le \ell-1$ . However, $\Phi(X) \coloneqq X^{\ell-1} + X^{\ell-2} + \dots + 1$ is the minimal polynomial of $\zeta$ , and $\deg P \ll \ell$ . Reading the coefficients of our nonconstant $P$ , this could only happen if $P(X) = X^d$ exactly, as desired.

Remark: The last step of the argument really uses the fact we have $P(X)^\ell-1$ . It would not work if we instead had $P(X)^k-1$ for some $k < \ell$ , because then the $\operatorname{lcm}(k,\ell)$ th cyclotomic polynomial may not be so well-behaved. That's why in the proof of the claim we had to some modular condition on $p$ (with $p \not\equiv 1 \pmod q$ for all $q$ ) to rule out the possibility that $p$ divided any of the other factors. If one tries the argument at first with just generic large $p$ dividing an element in the range of $\Phi$ , one would instead get $\Phi(X) \mid P(X)^k-1$ for some $k$ depending on $\ell$ , leading to the issue above.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a