Let $d \geq 2$ be a positive integer. Define the sequence $a_1,a_2,\dots$ by $$a_1=1 \ \text{and} \ a_{n+1}=a_n^d+1 \ \text{for all }n\geq 1.$$Determine all pairs of positive integers $(p, q)$ such that $a_p$ divides $a_q$.
Problem
Source: 2022 Thailand MO Day 2 P7
Tags: number theory, Sequence
Mathlover_1
16.04.2023 22:17
Quidditch wrote: Let $d \geq 2$ be a positive integer. Define the sequence $a_1,a_2,\dots$ by $$a_1=1 \ \text{and} \ a_{n+1}=a_n^d+1 \ \text{for all }n\geq 1.$$Determine all pairs of positive integers $(p, q)$ such that $a_p$ divides $a_q$. Any solution
starchan
16.04.2023 22:48
Doesn't #2 literally kill it?
Mathlover_1
16.04.2023 23:35
starchan wrote: Doesn't #2 literally kill it? How?
starchan
17.04.2023 09:14
Well, set $P(x) = x^d+1$. Define a sequence $a_0 = 0, a_i = P(a_i)$ for all $i > 0$. We want to know when $a_p \mid a_q$ for positive integers $p, q$. Using standard polynomial divisiblities, we know that $a_p \mid a_q$ if and only if $a_p \mid a_r$ where $r$ is remainder of $q$ modulo $p$. But since $r < p$ we have $a_r < a_p$ which forces $a_r = 0$ and $r = 0$. Hence $a_p \mid a_q$ happens iff $p \mid q$.