Poly with sequence give infinitely many prime divisors

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

w

7 users

TOPICS

No tags match your search

M

No tags match your search

M

Poly with sequence give infinitely many prime divisors

G H J

Reveal topic tags

national olympiad

Integer Polynomial

prime factorization

L

G H BBookmark kLocked kLocked NReply

Source: Bulgaria National Olympiad 2025, Day 1, Problem 3

The post below has been deleted. Click to close.

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

1324 posts

#1 h Apr 8, 2025, 1:51 PM • 1 Y

Y by cubres

Let $P(x)$ be a non-constant monic polynomial with integer coefficients and let $a_1, a_2, \ldots$ be an infinite sequence of positive integers. Prove that there are infinitely many primes, each of which divides at least one term of the sequence $P(n)^{a_n} + 1$ .

This post has been edited 1 time. Last edited by Assassino9931, May 3, 2025, 4:59 PM

Z K Y

The post below has been deleted. Click to close.

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

719 posts

#3 h Apr 8, 2025, 3:09 PM • 2 Y

Y by cubres, internationalnick123456

Suppose that $\{p_1,\dots,p_x\}$ is the set of prime divisors of $\{b_i\}$ .

Lemma: Let be a prime. If $d$ is the smallest positive integer such that $p|t^d+1$ and $p|t^{dm+r}+1$ , where $0\leq r<d$ , then $r=0$ .
Proof: Suppose that $r\neq 0$ . We have $p|(-1)^mt^r+1$ and if $m$ is even, $r<d$ would give a contradiction. For odd $m$ , we get $p|t^r-1$ thus, $ord_p(t)|r$ but then $p|t^{d-ord_p(t)}+1$ where $d-ord_p(t)>0$ which results in a contradiction.

Let $p_1|P(1)^{d_1}+1,\dots, p_k|P(1)^{d_k}+1$ . We see that for $n\equiv 1(mod \ p_1\dots p_x)$ , we have $p_i|P(n)^{d_i}+1$ and $p_i\not | P(n)^{l}+1$ for $l<d_i$ positive integer. Pick $n$ sufficiently large. If $p_i^{\theta_i}||P(1)^{d_i}+1$ , then $n\equiv 1(mod \ p_i^{\theta_i+1})$ in order to get $p_i^{\theta_i}||P(n)^{d_i}+1$ .
Assume that $rad (P(n)^{a_n}+1)=p_1\dots p_k$ . Let $a_n=p_1^{\beta_1}\dots p_k^{\beta_k}m$ for $\beta_j\geq 0$ .
$\nu_{p_i}(P(n)^{a_n}+1)\leq \nu_{p_i}((P(n)^{d_i})^{p_1^{\beta_1}\dots p_k^{\beta_k}m}+1)=\nu_{p_i}(P(n)^{d_i}+1)+\beta_i=\nu_{p_i}(P(1)^{d_i}+1)+\beta_i=\beta_i+\theta_i$ $P(n)^{p_1^{\beta}\dots p_k^{\beta_k}m}+1\leq p_1^{\beta_1+\theta_1}\dots p_k^{\beta_k+\theta_k}=(p_1^{\beta_1}\dots p_k^{\beta_k})(p_1^{\theta_1}\dots p_k^{\theta_k})$ Let $p_1^{\beta_1}\dots p_k^{\beta_k}=\ell$ and note that $p_1^{\theta_1}\dots p_k^{\theta_k}=c$ is a constant. We have $|P(n)^{\ell}+1|\leq |P(n)^{m\ell}+1|\leq |c\ell|$ . Since $P$ is non-constant and monic, $P(n)$ is unbounded above. $P(n)>5c$ exists hence $cl\geq 5^{\ell}.c^{\ell}$ does not hold. Hence we get contradiction as desired. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

77 posts

Haris1

#4 h Apr 9, 2025, 11:05 AM • 1 Y

Y by cubres

Nice problem , my solution is similar to bin_sherlo besides that i proved that if there are finite primes then $P(0)=0$ which is contradiction, good problem.

Z K Y

The post below has been deleted. Click to close.

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

16 posts

#5 h Apr 9, 2025, 12:55 PM • 1 Y

Y by cubres

bin_sherlo wrote:

Let $p_1|P(1)^{d_1}+1,\dots, p_k|P(1)^{d_k}+1$ . We see that for $n\equiv 1(mod \ p_1\dots p_x)$ , we have $p_i|P(n)^{d_i}+1$ and $p_i\not | P(n)^{l}+1$ for $l<d_i$ positive integer. Pick $n$ sufficiently large. If $p_i^{\theta_i}||P(1)^{d_i}+1$ , then $n\equiv 1(mod \ p_i^{\theta_i+1})$ in order to get $p_i^{\theta_i}||P(n)^{d_i}+1$ .

Why does such $d_i$ 's exsist? What if $p_i\mid P(1)$ or like the situation when $t=2,p=7$ ? I'm confused.

Z K Y

The post below has been deleted. Click to close.

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

719 posts

#6 h Apr 9, 2025, 1:38 PM • 1 Y

Y by cubres

DinDean wrote:

bin_sherlo wrote:

Let $p_1|P(1)^{d_1}+1,\dots, p_k|P(1)^{d_k}+1$ . We see that for $n\equiv 1(mod \ p_1\dots p_x)$ , we have $p_i|P(n)^{d_i}+1$ and $p_i\not | P(n)^{l}+1$ for $l<d_i$ positive integer. Pick $n$ sufficiently large. If $p_i^{\theta_i}||P(1)^{d_i}+1$ , then $n\equiv 1(mod \ p_i^{\theta_i+1})$ in order to get $p_i^{\theta_i}||P(n)^{d_i}+1$ .

Why does such $d_i$ 's exsist? What if $p_i\mid P(1)$ or like the situation when $t=2,p=7$ ? I'm confused.

Such $d_i$ does not have to exist, but if $p_i|P(n)^{a_n}+1$ for some $i$ , then there must be a minimum for $p_i|P(n)^{d_i}+1$ .

Z K Y

The post below has been deleted. Click to close.

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

1324 posts

#7 h Apr 9, 2025, 8:59 PM

Y by

A nice problem in the spirit of Sledgehammers in Number Theory, particularly Schur context for the bounded sequence case.

We consider separately the cases when the sequence $(a_n)$ is unbounded and when it is bounded.

First approach, unbounded

Second approach, unbounded

First approach, bounded

Second approach, bounded

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a