Sequence and prime factors

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

Sequence and prime factors

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: 2025 Taiwan TST Round 2 Independent Study 1-N

The post below has been deleted. Click to close.

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

540 posts

USJL

#1 h Mar 26, 2025, 6:29 AM • 1 Y

Y by MS_asdfgzxcvb

Let $a_0,a_1,\ldots$ be a sequence of positive integers with $a_0=1$ , $a_1=2$ and
$a_n = a_{n-1}^{a_{n-1}a_{n-2}}-1$ for all $n\geq 2$ . Show that if $p$ is a prime less than $2^k$ for some positive integer $k$ , then there exists $n\leq k+1$ such that $p\mid a_n$ .

Z K Y

The post below has been deleted. Click to close.

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

4 posts

#2 h Mar 31, 2025, 8:10 AM

Y by

how to solve this?????

Z K Y

The post below has been deleted. Click to close.

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

internationalnick123456

135 posts

internationalnick123456

#3 h Mar 31, 2025, 9:38 AM • 1 Y

Y by MS_asdfgzxcvb

Claim. $\nu_2(a_{n})\geq n,\forall n\in\mathbb N$ , $n$ is odd.
Now, we prove the statement by induction on $k$ .
When $k\leq 2$ , the statement is obvious. Assume the statement holds for $k-1$ . We prove it for $k$ .
Assume there exists an odd prime $p$ , $p<2^k$ , such that $p$ does not divide $a_1a_2\ldots a_{k+1}$ .
We prove $p-1\mid a_{k}a_{k-1}$ . Indeed, let $p-1=2^s q_1^{\ell_1} \ldots q_t^{\ell_t}$ where $q_1,\ldots,q_t$ are odd primes. Then, by claim, $2^s\mid a_ka_{k-1}$ . We only need to prove $q_i^{\ell_i}\mid a_ka_{k-1}$ .
Consider $m$ as the smallest integer such that $q_i\leq 2^m$ . Then $m\leq k-1$ .
By the inductive hypothesis, $q_i\mid a_j$ for some $2\leq j\leq m+1$ .
Applying the LTE lemma, we have
$\nu_{q_i}(a_{j+2}) =\nu_{q_i}\left(a_{j+1}^{a_{j+1}a_j} - 1\right) = \nu_{q_i}(a_j) + \nu_{q_i}(a_{j+1} + 1) = \nu_{q_i}(a_j)\left(1 + a_{j}a_{j-1}\right)\geq 7\nu_{q_i}(a_j)$ $\Rightarrow \nu_{q_i}(a_{j+2n})\geq 7^n\nu_{q_i}(a_j)\geq 7^n\Rightarrow \nu_{q_i}(a_ka_{k-1})\geq 7^{\left\lfloor (k-j)/2\right\rfloor}$
Moreover, $q_i^{\ell_i}\leq \frac{p-1}{2}\leq 2^{k-1}$ and $q_i>2^{m-1}$ , hence, $\ell_i\leq \frac{k-1}{m-1}\leq 7^{\left\lfloor (k-j)/2\right\rfloor}$
$\Rightarrow q_i^{\ell_i}\mid a_ka_{k-1}\Rightarrow p-1\mid a_ka_{k-1} \Rightarrow p\mid a_{k+1}$ .
Contradiction. The statement is proved.

This post has been edited 1 time. Last edited by internationalnick123456, Mar 31, 2025, 9:39 AM

Z K Y

The post below has been deleted. Click to close.

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

14 posts

#4 h Mar 31, 2025, 9:45 AM

Y by

:oops_sign:

This post has been edited 2 times. Last edited by zRevenant, Mar 31, 2025, 10:03 AM

Z K Y

The post below has been deleted. Click to close.

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

internationalnick123456

135 posts

internationalnick123456

#5 h Mar 31, 2025, 9:49 AM

Y by

@above I also thought about this approach before, however, I recognized that $\phi(\phi(p))\mid a_{n-2}a_{n-3}$ is not enough, we must also have $(\phi(p),a_{n-2}) = 1$ !

This post has been edited 1 time. Last edited by internationalnick123456, Apr 1, 2025, 3:19 PM

Z K Y

The post below has been deleted. Click to close.

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

14 posts

#6 h Mar 31, 2025, 10:00 AM • 1 Y

Y by internationalnick123456

internationalnick123456 wrote:

@above I also thought about this approach before, however, I recognized that if $\phi(\phi(p))\mid a_{n-2}a_{n-3}$ is not enough, we must also have $(\phi(p),a_{n-2}) = 1$ !

True, thx brother. Really be forgetting about this detail, cost me p2 IMO

Z K Y

The post below has been deleted. Click to close.

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

167 posts

#7 h Apr 5, 2025, 2:30 PM

Y by

USJL wrote:

Let $a_0,a_1,\ldots$ be a sequence of positive integers with $a_0=1$ , $a_1=2$ and
$a_n = a_{n-1}^{a_{n-1}a_{n-2}}-1$ for all $n\geq 2$ . Show that if $p$ is a prime less than $2^k$ for some positive integer $k$ , then there exists $n\leq k+1$ such that $p\mid a_n$ .

Before getting start, let's prove a lemma:
Lemma: $a_{n-2}^{a_{n-2}a_{n-3}}|a_n$ for all $n$
Proof: first notice that $2|a_n \iff 2\nmid n$ (which can be proved by easy induction)
$\because a_n=a_{n-1}^{a_{n-1}a_{n-2}}-1=(a_{n-2}^{a_{n-2}a_{n-3}}-1)^{a_{n-1}a_{n-2}}-1 \overset{2|a_{n-1}a_{n-2}}{\implies} (a_{n-2}^{a_{n-2}a_{n-3}}-1)^2-1|a_n \overset{(x-1)^2-1=x(x-2)}{\implies} a_{n-2}^{a_{n-2}a_{n-3}}|a_n$

Now, back to the original problem, let's induct on $k$ . For $k=0,1,2,3,4$ we can prove by easy calculation. Now suppose our claim is true for $k\ge m$ ( $m\geq 4$ ) and let’s consider $k=m+1$
From Fermat’s little theorem it’s sufficient to show that $\forall$ prime $p$ , $2^m<p<2^{m+1}$ , $\exists n\leq m+2$ such that $p-1|a_{n-2}a_{n-1}$ .
Now, for every prime divisor $q$ of $p-1$ , let’s prove that $\nu_q(p-1)\leq \nu_q(a_ma_{m+1})$
$\because p>2$ so $2|p-1$ , therefore $q\le \frac p2 \le 2^m$ . I'll split it into two cases:

for $q<2^{m-1}$ ,from induction hypothesis we know $q|a_i$ for some $i\le m-2$ and the Lemma we know at least one of $a_{m-2}$ , $a_{m-1}$ is divisible by $q$ , $\implies \nu_q(a_ma_{m+1})\ge \nu_q(a_{m-2}^{a_{m-2}a_{m-3}}a_{m-1}^{a_{m-1}a_{m-2}})\geq a_{m-2}\nu_q(a_{m-2}a_{m-1}) \geq a_{m-2}$
and since $m\geq 4$ so $a_{m-2} \geq m+1\geq log_2(2^{m+1}) > log_2(p-1)\geq \nu_q(p-1)$ , combine the two inequality we can reach our conclusion.
for $2^{m-1}<q<2^m$ , we must have $p-1=2q$ (otherwise, $p>2^{m+1}$ ) and from induction hypothesis and theLemma we know $2q=p-1| a_ma_{m+1}$

Z K Y

The post below has been deleted. Click to close.

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

1556 posts

#8 h Apr 18, 2025, 8:52 PM • 1 Y

Y by teomihai

Notice that $a_n=a_{n-1}^{a_{n-1}a_{n-2}}-1=(a_{n-2}^{a_{n-2}a_{n-3}}-1)^{a_{n-1}a_{n-2}}-1$ and since consecutive terms of $a_i$ alter in parity we must have that $a_n \equiv (-1)^{a_{n-1}a_{n-2}}-1 \equiv 0 \pmod{a_{n-2}^{a_{n-2}a_{n-3}}}$ this is more than sufficient to stablish that $\nu_2(a_n) \ge n$ for all odd $n$ (in fact it will grow faster than exponentially).
Now we will prove the statement by strong induction on $k$ where it is trivial for $k=1$ , now if it were true for $k$ we prove it for $k+1$ , so suppose that there exists a prime $2^k<p<2^{k+1}$ (since other cases are covered) such that $p \not \; \mid a_1a_2 \cdots a_{k+1}$ then we prove that $p-1 \mid a_ka_{k+1}$ which would be enough to conclude $p \mid a_{k+2}$ by FLT.
Let $p-1=2^{a} \cdot q_1^{\alpha_1} \cdots q_i^{\alpha_i}$ for odd primes $q_j$ , then $\nu_2(a_ka_{k+1}) \ge 2k+1>a$ so it remains to check that for any index $1 \le j \le i$ it happens that $\nu_{q_j}(a_ka_{k+1}) \ge \nu_{q_j}(p-1)$ .
The way to do this is to notice that every single $q_j<2^{\frac{k}{\alpha_j}}$ by definition of $p$ which shows the existence of some $a_j'$ for which $q_j \mid a_j'$ where $j' \le \frac{k}{\alpha_j}+1$ by inductive hypothesis and so say that next up we have $a_{j'}^{a_{j'}a_{j'-1}} \mid a_{j'+2}$ which shows that $\nu_{q_j}(a_{j'+2}) \ge (a_{j'}a_{j'-1})\nu_{q_j}(a_{j'})$ this is suficient to prove it whenever $\alpha_j=1$ , now for $\alpha_j \ge 2$ notice that $\nu_{q_i}(a_{j'+2m}) \ge a_{j'+2m-2} \cdots a_{j'-1}$ and obviously for $\alpha_j=2$ this solves it by checking initial terms even, for $\alpha_j \ge 3$ it now happens (for $k \ge 5$ )(check base cases $k=2,3$ just to be safe lol) that:
$\nu_{q_i}(a_{j'+2m}) \ge 6 \cdot (728)^{\frac{2(k-2)}{3}-2} \ge k+1 \ge \log_2(p-1)>\nu_{q_j}(p-1)$ Where here we get $j'+2m$ to be $k$ or $k+1$ but when $k=4$ we can ignore the rest of terms and only consider having two consecutives whose product is at least $6>5>4$ so it also works in this case and for $k=3$ too, so we have it all covered and from the $\nu_{q_j}$ 's we have that the inductive step is complete, thus we are done :cool:

:cool:

.

This post has been edited 2 times. Last edited by MathLuis, Apr 18, 2025, 8:53 PM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a