Sequence with infinite primes which we see again and again and again

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

6 users

TOPICS

No tags match your search

M

No tags match your search

M

Sequence with infinite primes which we see again and again and again

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: Balkan MO Shortlist 2024 N6

The post below has been deleted. Click to close.

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

1361 posts

#1 h Apr 27, 2025, 1:08 PM

Y by

Let $c$ be a positive integer. Prove that there are infinitely many primes, each of which divides at least one term of the sequence $a_1 = c$ , $a_{n+1} = a_n^3 + c$ .

This post has been edited 1 time. Last edited by Assassino9931, Apr 27, 2025, 1:08 PM

Z K Y

The post below has been deleted. Click to close.

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

79 posts

#2 h Apr 27, 2025, 2:22 PM

Y by

We prove the generalization (I'm not quite sure which contest this problem is from):
Let $P(x)$ be a non-constant monic polynomial with non-negative integer coefficients such that $P'(0) = 0$ . Let ${a_n}$ be a sequence such that $a_0=0$ and $P(a_n)=a_{n+1}$ . Prove that for every $n$ , there exists a prime $r$ such that $r|a_n$ but $r \not | a_1 \cdots a_{n-1}$ .
Claim: for all prime $q$ and integers $m,n$ , $v_q(a_n)=v_q(a_{mn})$
Proof: Let $v_q(a_n) = \alpha$ . Since $P'(0)=0$ , we get $a_{n+i} = P^i(a_n) \equiv P^i(0) = a_i \mod q^{2\alpha} \Rightarrow a_{mn} \equiv a_n \mod q^{2\alpha} \Rightarrow v_q(a_{mn})=v_q(a_n)$ Suppose that for some $m$ , and each $r$ dividing $a_m$ , there exists $i$ such that $r|a_i$ . Then from the claim we get $v_r(a_m) = v_r(a_{mi}) = v_r(a_i) \Rightarrow a_m | a_1 \cdots a_{m-1}$ But we have $a_m > a_{m-1}^2 > a_{m-1}a_{m-2}^2 > \cdots > a_{m-1}\cdots a_1$ which is a contradiction.
And so for every $n$ , there exists a prime $r$ such that $r|a_n$ but $r \not | a_1 \cdots a_{n-1}$ .

The problem is simply letting $P(x)= x^3+c$ .

This post has been edited 1 time. Last edited by Parsia--, Apr 27, 2025, 2:31 PM

Z K Y

The post below has been deleted. Click to close.

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

1361 posts

#3 h Apr 27, 2025, 2:32 PM • 1 Y

Y by ehuseyinyigit

Parsia-- wrote:

We prove the generalization (I'm not quite sure which contest this problem is from)

The thing you proved: Bulgaria National Round 2018

The given problem posted: here

See also: China IMO TST 2016 , IMO Shortlist 2014 N7, Silk Road 2023

This post has been edited 1 time. Last edited by Assassino9931, Apr 27, 2025, 2:44 PM

Z K Y

The post below has been deleted. Click to close.

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

1427 posts

#4 h Apr 30, 2025, 10:11 PM

Y by

Easier (though less general) solution: It's well-known that $x\mapsto x^3$ is injective modulo $p$ for any $p\equiv 5\pmod{p}$ prime (e.g., see my solution to a 1999 Balkan problem).

We now prove any such prime works. Note that there exists $(i,j)$ such that $a_i\equiv a_j\pmod{p}$ . Take such a pair $j>i\ge 1$ with the smallest coordinate sum and assume $i>1$ . Then, $a_j=a_{j-1}^3+c\equiv a_{i-1}^3+c\pmod{p}$ forces $a_{j-1}\equiv a_{i-1}$ , contradicting with minimality of $(i,j)$ . So, $i=1$ . But then, there is a $j>2$ such that $a_j=a_{j-1}^3+c\equiv c\pmod{p}$ , forcing $p\mid a_{j-1}$ .

This post has been edited 1 time. Last edited by grupyorum, Apr 30, 2025, 10:12 PM

Z K Y

The post below has been deleted. Click to close.

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

SimplisticFormulas

119 posts

SimplisticFormulas

#5 h May 2, 2025, 4:21 PM • 1 Y

Y by L13832

sol

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a