Let $c,d \geq 2$ be naturals. Let $\{a_n\}$ be the sequence satisfying $a_1 = c, a_{n+1} = a_n^d + c$ for $n = 1,2,\cdots$. Prove that for any $n \geq 2$, there exists a prime number $p$ such that $p|a_n$ and $p \not | a_i$ for $i = 1,2,\cdots n-1$.
Problem
Source: China 2016 TST Day 2 Q4
Tags: number theory, Sequence, prime numbers
fattypiggy123
16.03.2016 07:15
This is very similar to ISL 2014 N7 . In fact, the same method works here and is much easier to see since the recursion contains only one $a_n$ term while it is more complicated for the N7.
fractals
16.03.2016 07:37
Lemma. If $p^k|a_x$, then $p^{dk}|a_{xy} - a_x$.
Proof:
Then $a_{x + 1} = a_x^d + c \equiv c \equiv a_1 \pmod{p^{dk}}$ and then easy induction shows that $a_{x + t} \equiv a_t \pmod{p^{dk}}$ always when $t \ge 1$, so $a_{xy} \equiv a_{x(y - 1)} \equiv \cdots \equiv a_x \pmod{p^{dk}}$ and we are done.
Corollary: $v_p(a_{xy}) = v_p(a_x)$ if $p|a_x$.
Prove this using $d > 1$.
Now if $t|a_m, a_n$ then $a_n = a_{n - 1}^d + c = (a_{n - 2}^d + c)^d + c = \cdots = ((\cdots(a_m^d + c)^d\cdots + c)^d + c)^d + c \equiv a_{n - m} \pmod{t}$, so $t|a_{m - n}$. This lays the foundation for a Euclidean algorithm on the indices, which leads to $t|a_{\gcd(m, n)}$.
So if $p|a_m, a_n$ then $p|a_{\gcd(m, n)}$ so $v_p(a_n) = v_p(a_{\gcd(m, n)})$, the last step by $\gcd(m, n)|n$ and the above corollary.
Should we ever have an $n \ge 2$ with no primitive prime factor, then $a_n \le a_{n - 1}a_{n - 2}\cdots a_1$ since each of its prime power factors can then be attributed to a term $a_d$, where $d|n$ (this is a very terrible bound, actually).
But $a_n > a_{n - 1}^d = a_{n - 1}\cdot a_{n - 1}^{d - 1} > a_{n - 1}\cdot a_{n - 2}^{d(d - 1)} > \cdots > a_{n - 1}a_{n - 2}\cdots a_1\cdot a_1^k$ for some $k \ge 0$, as $d > 1$. This is a contradiction!
bobthesmartypants
10.04.2016 01:36
Let $f(x)=x^d+c$, then $f^n(0)=a_n$.
Now I will use strong induction to prove that if $v_p(f^k(0))=\ell > 0$, then $v_p(f^{km}(0))=\ell$. Thus, we suppose $v_p(f^{ki}(0))=\ell >0$ for $1\le i \le m-1$. Let $f^{k(m-1)}(0)\equiv x\pmod{p^{\ell+1}}$ where $v_p(x)=\ell$. Then $$f^{km}(0)=f^k(f^{k(m-1)}(0))\equiv f^k(x) = f^{k-1}(x^d+c) \stackrel{d\ge 2}{\equiv} f^{k-1}(c)=f^{k}(0)\pmod{p^{\ell +1}}$$However since $v_p(f^k(0))=\ell$, it follows that $v_p(f^{km}(0))=\ell$ and the induction is complete. $\blacksquare$
It follows that for all prime factors $p$ that $a_n$ introduces that aren't new, $v_p(a_n) = v_p(a_k)$ for $k\mid n$ so the multiplicity of the prime $p$ in $a_n$ is not greater than previous instances. Thus if there are no new primes in $a_n$ we must have $\displaystyle\prod_{i=1}^{n-1}\gcd(a_i,a_n) > a_n$. However, $\displaystyle\prod_{i=1}^{n-1}\gcd(a_i,a_n)\le \displaystyle\prod_{i=1}^{n-1}a_i < a_n$ where the last inequality follows inductively: obviously $c< c^d+c$ and by induction, $\displaystyle\prod_{i=1}^{n-1}a_i < a_{n-1}^2 \stackrel{d\ge 2}{<} a_n$. Thus we have a contradiction and so there must be a new prime introduced.
pavel kozlov
17.04.2016 14:56
Let us introduce $b_n=a_n/c$ with recurrent $b_{n+1}=b_n^dc^{d-1}+1$, $b_1=1$. It is evident that $(b_n,c)=1$,so it is sufficient to prove that $(b_n,b_m)=1$ for $n\not =m$. It follows by induction from the next lemma: Lemma. $b_n \equiv b_{n-m} \mod b_m$ for positive integers $n>m$. Proof: Let us prove this assertion by induction by $n$. Base is evident, let us assume that $b_{n-1} \equiv b_{n-m-1} \mod b_m$ (here we define $b_0=0$ naturally). Then $b_n=b_{n-1}^dc^{d-1}+1 \equiv b_{n-m-1}^dc^{d-1}+1=b_{n-m} \mod b_m$, Q.E.D.
liorz2000
13.05.2017 12:14
But according the lemma bm|b2m , and it is a contradiction to gcd(bm,b2m)=1
reveryu
25.10.2017 17:09
pavel kozlov wrote: Let us introduce $b_n=a_n/c$ with recurrent $b_{n+1}=b_n^dc^{d-1}+1$, $b_1=1$. It is evident that $(b_n,c)=1$,so it is sufficient to prove that $(b_n,b_m)=1$ for $n\not =m$. It follows by induction from the next lemma: Lemma. $b_n \equiv b_{n-m} \mod b_m$ for positive integers $n>m$. Proof: Let us prove this assertion by induction by $n$. Base is evident, let us assume that $b_{n-1} \equiv b_{n-m-1} \mod b_m$ (here we define $b_0=0$ naturally). Then $b_n=b_{n-1}^dc^{d-1}+1 \equiv b_{n-m-1}^dc^{d-1}+1=b_{n-m} \mod b_m$, Q.E.D. Wrong. $(b_n,b_m)=1$ isn't true. it can be proved that ,such as,$ b_2|b_4$ or take$ c=d=2$ you can see $ b_2|b_4$.
Sprites
15.09.2021 18:21
fattypiggy123 wrote: Let $c,d \geq 2$ be naturals. Let $\{a_n\}$ be the sequence satisfying $a_1 = c, a_{n+1} = a_n^d + c$ for $n = 1,2,\cdots$. Prove that for any $n \geq 2$, there exists a prime number $p$ such that $p|a_n$ and $p \not | a_i$ for $i = 1,2,\cdots n-1$.
FTSOC,assume that no such prime exists.Let $a_j$ be the smallest term with $p|a_j$
Claim: $a_j \equiv a_{kj+m} \pmod p$
Proof: This is obvious.
Claim: $\nu_p(a_n)=\nu_p(a_j)$
Proof: Let $r=\nu_p(a_j)$,then $a_{j+1}=a_j^d+c\equiv c=a_1 \pmod p$
Since $j|n$ and by induction,$a_n \equiv a_j \pmod p^{dr}$ and $\nu_p(a_j)=r<dr$ this gives $\nu_p(a_n)=r$
Observe that this implies that for every prime $p<n$ we can find $a_{j_p}$ with $p|a_{j_p}$ or $a_n|a_{n-1}........a_1$, contradiction since $a_n>a_{n-1}..........a_1$ by induction so we are done.$\blacksquare$
laikhanhhoang_3011
13.12.2021 03:33
Induction goes goes bruh bruh
Assume done for $n-1$, let's prove the statement is true for $n$
Let $p$ be a prime: $p|a_{n}$
We have a number $m<n: p|a_m$
So $a_n=((...(a_m+c)^d)...+c)^d...+c)^d+c \equiv a_{n-m} \, (mod \, p)$ $ \rightarrow \vdots p|a_{n-m}$
Easily seeing $a_{xn-ym} \vdots p$ for all positive integer $x,y$
So $a_{(n.m)} \vdots p$
Now let's check $v_p(a_{n})$
Claim 1: If $p^k|a_x$ then $a_{xy}-a_y \vdots p^{dk}$
Proof: We have $a_{x+1}=a_n^{d}+c \equiv c \equiv a_1$ $(mod$ $p^{dk})$. The rest is trivial by induction
Claim 2: $v_p(a_x)=v_p(a_{xy})>0$ for all $y \in N^*$
Proof: Trivial by Claim 1
Because $m<n$, $(n,m) \leq m <n$ and $(m,n)|n$ so $v_p(a_{(n,m)})=v_p(a_n) $
$ \Rightarrow a_n < a_1.a_2...a_{n-1}$
But $a_n>a_{n+1}^d=a_{n-1}.a_{n-1}^{d-1}>a_{n-1}a_{n-2}^{d-1}>....>a_{n-1}a_{n-2}...a_1$, a contradiction
Q.E.D
Afternonz
04.05.2022 21:23
Claim 1: For each $n\in\mathbb{N}$, $a_1a_2\dots a_n<a_{n+1}$.
Proof. Induct on $n$, base case trivial. If $a_1a_2\dots a_n<a_{n+1}$, then $a_1a_2\dots a_{n+1}<a_{n+1}^2<a_{n+1}^d+c=a_{n+2}$.
Claim 2: $\gcd(a_i,a_j)=a_{\gcd(i,j)}$
Proof. It is enough to show $\gcd(a_i,a_j)=\gcd(a_i,a_{j-i})$ for any $i<j$. Let $d_1=\gcd(a_i,a_j),d_2=\gcd(a_i,a_{j-i})$. We have
\begin{align*}
&a_{i+1}\equiv a_i^d+c \equiv c\equiv a_1 \pmod {d_1}\\
&a_{i+2}\equiv a_{i+1}^d+c \equiv a_1^d+c\equiv a_2 \pmod {d_1}\\
&\vdots\\
&a_j\equiv a_{j-1}^d+c\equiv a_{j-i-1}^d+c\equiv a_{j-i} \pmod {d_1}
\end{align*}Hence, $d_1\mid a_{j-i}$ and $d_1\mid a_i$ so $d_1\mid d_2$. Similarly, $d_2\mid d_1$ so $d_1=d_2$.
Claim 3: For each $m\mid n$, $v_p(a_n)=v_p(a_m)$ for all primes $p\mid a_m$.
Proof: We have
\begin{align*}
&a_{m+1}\equiv a_m^d+c \equiv c\equiv a_1 \pmod {a_m^2}\\
&a_{m+2}\equiv a_{m+1}^d+c \equiv a_1^d+c\equiv a_2 \pmod {a_m^2}\\
&\vdots\\
&a_{2m}\equiv a_{2m-1}^d+c \equiv a_{m-1}^d+c\equiv a_m \pmod {a_m^2}\\
&a_{2m+1}\equiv a_{2m}^d+c \equiv c\equiv a_1 \pmod {a_m^2}\\
&\vdots\\
&a_j\equiv a_{j-1}^d+c\equiv a_{j-i-1}^d+c\equiv a_{j-i} \pmod {a_m^2}
\end{align*}which implies the claim.
Thus, for each $n\ge 2$, any common prime divisor $p$ of $a_n$ and $a_1a_2\dots a_{n-1}$ is a divisor of $P=\prod_{i\mid n, i\neq n} a_i$ and $v_p(P)\ge v_p(a_n)$. The part of $a_n$ having no common prime factor with $a_1a_2\dots a_{n-1}$ is then at least $\frac{a_n}{P}\ge\frac{a_n}{a_1a_2\dots a_{n-1}}>1$, as needed.
EthanWYX2009
01.04.2023 16:18
运用反证法, 假设某个 ${n}\in\mathbb N_+$ 满足 $a_n$ 的所有素因子均为 $\prod\limits_{k=1}^{n-1}a_k$ 的因子. 取 $a_n$ 的一个素因子 ${p}$, 则 $\exists 1\leq j\leq n-1$, 满足 $p\mid a_j$. 取最小满足的 ${j}$, 我们来证明 $j\mid n$. 通过 $a_{j+1}\equiv a_j^d+c\equiv c=a_1\pmod p$, 不难运用数学归纳法证明对 $\forall u\in\mathbb N_+$, $a_{j+u}\equiv a_u\pmod p$. 因此数列 $\{a_n\}$ 在模 ${p}$ 意义下以 ${j}$ 为周期. 记 $a_n=qj+r$, 其中 $j\in\mathbb Z$ 且 $0< r\leq j$. 故 $a_n\equiv a_r\pmod p$, 由 ${j}$ 的最小性知 $r=j$, 即 $j\mid n$. 我们再证明 $v_p(a_n)=v_p(a_j)$. 记 $v_p(a_n)=r$, 则 $a_{j+1}=a_j^d+c\equiv c=a_1\pmod{p^{rd}}$. 不难运用数学归纳法证明对 $\forall u\in\mathbb N_+$, $a_{j+u}\equiv a_u\pmod {p^{rd}}$. 因此 $a_n\equiv a_j\pmod {p^{rd}}$. 但 $v_p(a_j)=r<rd$, 从而必有 $v_p(a_n)=v_p(a_j)$. 故对于 $a_n$ 的所有素因子 ${p}$, $v_p(a_n)\leqslant v_p\left(\prod\limits_{k=1}^{n-1}a_k\right)$, 从而 $a_n\mid\prod\limits_{k=1}^{n-1}a_k$, 因此 $a_n\leqslant\prod\limits_{k=1}^{n-1}a_k$. 但当 $n=2$ 时, $a_2=a_1^d+c>a_1$, 我们可运用数学归纳法, 通过 $n-1$ 时 $a_{n-1}>\prod\limits_{k=1}^{n-2}a_k$, 得到 $a_n>a_{n-1}^2>\prod\limits_{k=1}^{n-1}a_k$. 这证明了对于 $\forall n\in\mathbb N_+$ 均有 $a_n>\prod\limits_{k=1}^{n-1}a_k$, 矛盾! 故存在 $a_n$ 的素因子 ${p}$ 满足 $p\nmid\prod\limits_{k=1}^{n-1}a_k$.$\blacksquare$
Cali.Math
01.03.2024 19:35
We uploaded our solution https://calimath.org/pdf/ChinaTST2016-1-4.pdf on youtube https://youtu.be/TapKwmarZXA.