Long polynomial factorization

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

Long polynomial factorization

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: 2025 Vietnam IMO TST - Problem 6

The post below has been deleted. Click to close.

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

311 posts

#1 h Mar 26, 2025, 7:33 AM • 2 Y

Y by ehuseyinyigit, Funcshun840

For each prime $p$ of the form $4k+3$ with $k \in \mathbb{Z}^+$ , consider the polynomial $Q(x)=px^{2p} - x^{2p-1} + p^2x^{\frac{3p+1}{2}} - px^{p+1} +2(p^2+1)x^p -px^{p-1}+ p^2 x^{\frac{p-1}{2}} -x + p.$ Determine all ordered pairs of polynomials $f, g$ with integer coefficients such that $Q(x)=f(x)g(x)$ .

This post has been edited 1 time. Last edited by wassupevery1, Mar 26, 2025, 9:54 AM

Z K Y

The post below has been deleted. Click to close.

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

97 posts

#2 h Mar 26, 2025, 12:10 PM

Y by

It is not hard to notice that $f(x) = x^p + p x^{\frac{p+1}{2}} - x + p, g(x) = px^p - x^{p - 1} + p x^{\frac{p-1}{2}} + 1$ is a valid factorization.

This post has been edited 1 time. Last edited by Photaesthesia, Mar 26, 2025, 12:10 PM

Z K Y

The post below has been deleted. Click to close.

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

15 posts

#3 h Mar 26, 2025, 2:23 PM • 2 Y

Y by ehuseyinyigit, Funcshun840

It is really funny to see that the hard part of a P6 TST is factoring the polynomial itself. After one manages to factorize it, proving irreducibility is fairly simple. :oops:

:oops:

EDIT: I misread the polynomials. Oops. Turns out proving irreducibility is NOT fairly simple. I don't have any guesses on how one could easily prove that $f(x) = x^p + px^{\frac{p+1}{2}} - x + p$ is irreducible over the integers, but once that is proven, then $g(x)$ is irreducible too since it is just $x^p f\left(\frac{1}{x}\right)$ .

EDIT 2: wassupevery1 on Discord and @2below gives this paper which trivializes the question. (see page 4)

This post has been edited 3 times. Last edited by b1zmark, Thursday at 3:30 PM

Z K Y

The post below has been deleted. Click to close.

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

4 posts

#4 h Mar 26, 2025, 5:01 PM

Y by

b1zmark wrote:

It is really funny to see that the hard part of a P6 TST is factoring the polynomial itself. After one manages to factorize it, proving irreducibility is fairly simple. :oops:

:oops:

Could you give the proof of the irreducibility? I do not see how it is simple.

Z K Y

The post below has been deleted. Click to close.

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

1 post

The5

#5 h Thursday at 2:57 PM

Y by

See in Berend Ringeling, On Lehmer’s question for integer-valued polynomials.

Z K Y

The post below has been deleted. Click to close.

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

4 posts

#6 h 10 minutes ago

Y by

b1zmark wrote:

It is really funny to see that the hard part of a P6 TST is factoring the polynomial itself. After one manages to factorize it, proving irreducibility is fairly simple. :oops:

:oops:

EDIT: I misread the polynomials. Oops. Turns out proving irreducibility is NOT fairly simple. I don't have any guesses on how one could easily prove that $f(x) = x^p + px^{\frac{p+1}{2}} - x + p$ is irreducible over the integers, but once that is proven, then $g(x)$ is irreducible too since it is just $x^p f\left(\frac{1}{x}\right)$ .

EDIT 2: wassupevery1 on Discord and @2below gives this paper which trivializes the question. (see page 4)

Please check your work and think before you speak. It is a very difficult problem. It is not just "Not fairly simple" as you said.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a