p^k divides term of sequence

Art of Problem Solving

AoPS Online

Contests & Programs AMC and other contests, summer programs, etc.

AMC and other contests, summer programs, etc.

3 M G

BBookmark VNew Topic kLocked

Contests & Programs AMC and other contests, summer programs, etc.

AMC and other contests, summer programs, etc.

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

p^k divides term of sequence

G H J

Reveal topic tags

awesomeness_in_a_bun

L

G H BBookmark kLocked kLocked NReply

Source: USAJMO 2024/3

The post below has been deleted. Click to close.

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

424 posts

#1 h Mar 20, 2024, 4:01 AM • 2 Y

Y by megarnie, deduck

Let $a(n)$ be the sequence defined by $a(1)=2$ and $a(n+1)=(a(n))^{n+1}-1$ for each integer $n\geq 1$ . Suppose that $p>2$ is a prime and $k$ is a positive integer. Prove that some term of the sequence $a(n)$ is divisible by $p^k$ .

Proposed by John Berman

This post has been edited 1 time. Last edited by KevinYang2.71, Mar 21, 2024, 3:11 PM

Z K Y

The post below has been deleted. Click to close.

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

93 posts

#2 h Mar 20, 2024, 4:01 AM • 3 Y

Y by pikapika007, Mogmog8, centslordm

If $p \nmid a(\phi(p^k) - 1)$ for all sufficiently large $k$ , then we are done.
Else, we get that $a(\phi(p^k) + 1) \equiv 2 \pmod{p^k}$ which gives that $a(2) \equiv a(\phi(p^k) + 2) \equiv 3 \pmod{p^k}$ so we have periodicity with period $\phi(p^k)$ eventually.

For smaller $n = k-1$ , suppose that $p \nmid a(\phi(p^n) - 1)$ . It follows that $a(\phi(p^n)) = 0 \pmod{p}$ . Consider $a(c), a(c + \phi(p^n)), \dots, a(c + (p-1)\phi(p^n))$ . By iterating repeatedly on $c$ , we eventually get two equal values and a period $C \cdot \phi(p^n)$ for $C < p$ , taking a gcd gives $\phi(p^n)$ .

Inductively we have a $0 \pmod{p^n}$ with period $\phi(p^n)$ . It follows by another PHP argument that $\pmod{p^k}$ has period $\phi(p^n)$ as well. However, this implies that $p \mid a(\phi(p^{k-1}) - 1 + (k-1) \cdot \phi(p^{k-1}))$ , contradiction.

Z K Y

The post below has been deleted. Click to close.

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

1751 posts

#3 h Mar 20, 2024, 4:02 AM • 4 Y

Y by Shifted777, bjump, a_smart_alecks, Orthogonal.

First, we will show that the problem statement holds for $k = 1.$ That is, we will show that for all primes $p > 2,$ there exists an integer $n_p$ such that $p \mid a(n_p).$ By the problem condition, we have
$a(p-1) = ((a(p-2))^{p-1} - 1.$ If $a(p-2) \equiv 0 \mod{p},$ then we just set $n_p = p-2,$ otherwise FLT implies that $(a(p-2))^{p-1} - 1 \equiv 1 - 1 \equiv 0 \pmod{p},$ so we take $n_p = p-1.$ Either way, we have found our $n_p.$

Now, call a prime $p$ good if there exists a positive integer $i$ such that $p \mid a(2i)$ and bad otherwise. We will split the problem into cases on whether $p$ is good or not.

Case 1: $p$ is good. Then suppose that $p \mid a(2i)$ for some positive integer $i$ , so that $a(2i) = xp$ for some positive integer $x.$ Then $a(2i+1) = (xp)^{2i+1} - 1$ and $a(2i+2) \equiv ((xp)^{2i+1} - 1)^{2i+2} - 1 \equiv (-1)^{2i+2} - 1 \equiv 1 - 1 \equiv 0 \pmod{p^{2i+1}}.$ In particular, $a(2i+2)$ is divisible by $p,$ so a straightforward induction implies that $p^{2i+2m-1} \mid a(2i+2m).$ By taking $m$ arbitrarily large, this solves the problem for good $p.$

Case 2: $p$ is bad. Let $z = x(p-1)$ where $x$ is a positive integer. Then plugging in $n = z-1$ into the problem condition gives $a(z) = ((a(z-1))^z - 1.$ If $a(z-1) \not \equiv 0 \pmod{p},$ then FLT implies that this expression is $0$ modulo $p,$ so $a(z) \equiv 0 \pmod{p}.$ However, since $z$ is even, this implies that $p$ is good, which is a contradiction. Thus we have $a(z-1) \equiv 0 \pmod{p}.$

Plugging in $n = z-2$ into the problem condition, we get $a(z-1) \equiv ((a(z-2))^{z-1} - 1 \equiv 0 \pmod{p},$ so $(a(z-2))^{z-1} \equiv 1 \pmod{p}.$ If $a(z-2) \equiv 0 \pmod{p}$ then this obviously doesn't hold, so FLT implies that $(a(z-2))^z \equiv 1 \pmod{p}$ and so $a(z-2) \equiv 1 \pmod{p}.$

Now, by the Chinese Remainder Theorem, there exists a value of $x$ that makes $z$ equivalent to $1 \pmod{p^k},$ so assume henceforth that $z \equiv 1 \pmod{p^k}.$ Since $a(z-2) \equiv 1 \not \equiv 0 \pmod{p}$ and $p > 2,$ we can apply the exponent-lifting lemma and get
$\begin{align*} \nu_p (a(z-1)) &= \nu_p ((a(z-2))^{z-1} - 1^{z-1}) \\ &= \nu_p (a(z-2) - 1) + \nu_p (z-1) \\ &\ge 0 + k = k \end{align*}$ since $p^k \mid z-1,$ so $p^k \mid a(z-1).$ Setting $k$ to be arbitrarily large solves the problem for bad $p.$

We have exhausted all cases, so we are done.

I have a video solution to this problem which can be found at https://www.youtube.com/watch?v=HLOjs-amXWI.

This post has been edited 2 times. Last edited by EpicBird08, Oct 27, 2024, 3:09 AM
Reason: how did i find a typo seven months later

Z K Y

The post below has been deleted. Click to close.

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

337 posts

#4 h Mar 20, 2024, 4:06 AM • 2 Y

Y by KevinYang2.71, thinkcow

If $p\nmid a(m\varphi(p^k) - 1)$ for some integer $m$ then the conclusion is obvious. Therefore, assume $p\mid a(m\varphi(p^k) - 1)$ for all $m$ .

We can assume $p\mid a(m\varphi(p) - 1)$ . If not, then $a(m\varphi(p)) \equiv 0 \pmod p$ , and since $\varphi(p)$ is even, we have $a(m\varphi(p) + 1)\equiv -1 \pmod p$ , $a(m\varphi(p) + 2)\equiv 0 \pmod p$ , repeating, which finishes because $m\varphi(p^k) - 1$ is odd.

Now, we claim $a(m\varphi(p) - 2) \equiv 1 \pmod p$ . This is because $(a(m\varphi(p) - 2))^{m\varphi(p) - 1} - 1 \equiv 0\pmod p$ , and by orders, we must have $a(m\varphi(p) - 2) \equiv 1 \pmod p$ .

We claim $p^k\mid a(p^{k-1} (p-2))$ . Notice that $p^{k-1} (p-2) - 1 \equiv - 2 \pmod{\varphi(p)}$ , so $a(p^{k-1} (p-2) - 1)\equiv 1 \pmod p$ , which can be written as $dp + 1$ for some integer $d$ .

Finally, expanding $(dp + 1)^{p^{k-1} (p-2)}$ , by binomial theorem, every term vanishes $\pmod{p^k}$ , so it is equivalent to $1\pmod{p^k}$ .

This post has been edited 3 times. Last edited by plang2008, Mar 20, 2024, 4:10 AM
Reason: nevermind i'm throwing

Z K Y

The post below has been deleted. Click to close.

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

1437 posts

#5 h Mar 20, 2024, 4:06 AM

Y by

How many points for proving Case 1 in the 2above solution?

This post has been edited 1 time. Last edited by pi_is_3.14, Mar 20, 2024, 4:07 AM

Z K Y

The post below has been deleted. Click to close.

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

616 posts

#6 h Mar 20, 2024, 4:44 AM

Y by

(wrong cuz badge)

This post has been edited 3 times. Last edited by Ilikeminecraft, Aug 9, 2024, 5:32 AM
Reason: wrong

Z K Y

The post below has been deleted. Click to close.

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

125 posts

abeot

#7 h Mar 20, 2024, 12:39 PM • 3 Y

Y by GrantStar, centslordm, Tem8

First, suppose that $p \nmid a_{p-2}$ . Then since $a_{p-1} = (a_{p-2})^{p-1} - 1$ , by Fermat it follows that $p \mid a_{p-1}$ . Then
$a_p \equiv (a_{p-1})^p - 1 \equiv -1 \pmod {p^p} \implies a_{p+1} \equiv (-1)^{p+1} - 1 \equiv 1 - 1 \equiv 0 \pmod {p^p}$ We can repeat this indefinitely since $p+1$ , $p+3$ etc. is even to find that $p^k$ would divide some term.

Otherwise then $p \mid a_{p-2}$ and with some work we can calculate $a_p \equiv -2 \mod p$ so $a_{p+1} \equiv 3 \mod p$ , and the sequence becomes periodic with period $p-1$ . This implies that $a_{m(p-1)-1}$ is always divisible by $p$ . Then take the $x$ such that $p^k \mid x(p-1)-1$ , which is possible since $\gcd(p^k, p-1) = 1$ . Verify that $a_{x(p-1)-2} \equiv 1 \pmod p$ and so we can apply LTE:
$\nu_p(a_{x(p-1)-1}) = \nu_p((a_{x(p-1)-2})^{x(p-1)-1} - 1) = \nu_p(x(p-1)-1) + \nu_p(a_{x(p-1)-2} - 1)$ So $\nu_p(a_{x(p-1)-1}) \ge k$ 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.

136 posts

#8 h Mar 20, 2024, 12:55 PM

Y by

had little time for this one...maybe 2 or 3 points for a case?

Z K Y

The post below has been deleted. Click to close.

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

5419 posts

#9 h Mar 20, 2024, 2:03 PM • 1 Y

Y by GrantStar

First things first, if $a(p^k-p^{k-1}-1)\not\equiv0\pmod{p}$ , Euler's Totient Theorem gives
$\begin{align*} a(p^k-p^{k-1}&)=a(p^k-p^{k-1}-1)^{p^k-p^{k-1}}-1\\ &\stackrel{\text{ETT}}{\equiv}1-1=0\pmod{p^k}. \end{align*}$ Now if $a(p^k-p^{k-1}-1)\equiv0\pmod{p}~(\ast)$ , clearly $a(p-2)\equiv0\pmod{p}~(\dagger)$ , as otherwise
$\begin{align*} a(p-1)=a(p-2)^{p-1}-1\stackrel{\text{ETT}}{\equiv}1-1&=0\pmod{p}\\ a(p)=a(p-1)^p-1\equiv0^p-1&=-1\pmod{p}\\ a(p+1)=a(p)^{p+1}-1\equiv(-1)^{p+1}-1&=0\pmod{p}\\ &~\vdots\\ a(\text{odd})&\equiv-1\pmod{p}\\ a(\text{even})&\equiv0\pmod{p} \end{align*}$ which contradicts $(\ast)$ .

From $(\dagger)$ we can gather a couple facts:

$a(\cdot)\pmod{p}$ is periodic with length $p-1$ , since
$\begin{align*} a(p-1)=a(p-2)^{p-1}-1\equiv0^{p-1}-1&=-1\pmod{p}\\ a(p)=a(p-1)^p-1\equiv(-1)^{p-1}-1&=-2\pmod{p}\\ a(p+1)=a(p)^{p+1}\equiv(-2)^{p+1}-1&=3\pmod{p}, \end{align*}$ the last of which equates to $a(2)$ .
Specifically, $a(p-3)\equiv1\pmod{p}$ , because
$a(p-2)=a(p-3)^{p-2}-1\equiv a(p-3)^{-1}-1\equiv0\pmod{p}.$

In other words, any index $\equiv-2\pmod{p-1}$ correlates to a term $\equiv1\pmod{p}$ . The rest is easy: consider, say, the integer $\tfrac{(p-2)p^{k-1}+1}{p-1}$ , so that
$a((p-2)p^{k-1}-1)=a(\tfrac{(p-2)p^{k-1}+1}{p-1}(p-1)-2)\equiv1\pmod{p}.$ Lifting the Exponent yields
$\begin{align*} v_p(a((p-2)p^{k-1}))&=v_p(a((p-2)p^{k-1}-1)^{(p-2)p^{k-1}}-1)\\ &=v_p(a((p-2)p^{k-1}-1)-1)+v_p((p-2)p^{k-1})\\ &\ge1+(k-1)=k, \end{align*}$ as desired. $\square$

Z K Y

The post below has been deleted. Click to close.

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

7585 posts

#10 h Mar 20, 2024, 2:57 PM

Y by

solved in 20 minutes last night, unfortunately beaten by pi271828 who solved it in five (he swept the day in 15 minutes, so sad that he didn't make jmo because of cheaters

)

i was going to write a sketch but i guess this is a full solution

Step 1: Consider a value $n$ which satisfies $a(n)\equiv 0\pmod p$ . If $n$ is even, then residues will rotate between $0$ and $-1$ . (Step 2)

Otherwise assume that $a(2k)\not \equiv 0\pmod p$ and take $n\equiv -1\pmod {p-1}$ . In this case $n$ is odd and if $a(n)\not\equiv 0\pmod p$ we find that $a(n+1)\equiv 0\pmod p$ , a contradiction. (Step 3)

Step 2: First case from above: when $a(n)\equiv -1\pmod p$ and $n$ is odd and large we use LTE; suffices to have $\nu_p\left(\frac{n+1}{2}\right)\ge k$ hence $n\equiv -1\pmod {2p^k}$ works just fine.

Step 3: Second case from above: notice for such $n\equiv -1\pmod {p-1}$ we have
$a(n)=((a(n-1))^{p-1})^{\tfrac{n+1}{p-1}}-1$ hence we need $p^k\mid \frac{n+1}{p-1}$ . Taking $n=p^k(p-1)-1$ works here.

Done. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

148 posts

#11 h Mar 20, 2024, 3:55 PM

Y by

any points for proving that when n is even if p works then p^k works?

Z K Y

The post below has been deleted. Click to close.

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

8859 posts

#12 h Mar 20, 2024, 4:42 PM

Y by

This problem may be the easiest J3/6 ever; it's straightforward with LTE.

The idea is that LTE ``almost" works; we just need to guarantee that the relevant terms are not already multiples of $p$ .

We will write $a_n$ in lieu of $a(n)$ for simplicity. Observe that we have $a_{p-1} = a_{p-2}^{p-1} - 1 \equiv 0 \pmod p$ when $p \nmid a_{p-2}$ . (We will deal with the case $p \mid a_{p-2}$ later.)

Now, for $p$ that satisfy this condition, notice that
$\begin{align*} a_p &= a_{p-1}^p - 1 \equiv -1 \pmod p \\ a_{p+1} &= a_p^{p+1} - 1 \equiv 1 - 1 \equiv 0 \pmod p. \end{align*}$ I claim that in general, we have $a_{p+2k} \equiv -1\pmod p$ and $a_{p+2k+1} \equiv 0 \pmod p$ for all $k \geq 0$ . The proof is by induction, with the base case $k=0$ illustrated above.

Assume that the result is true for $k-1$ ; then
$\begin{align*} a_{p+2k} &= a_{p+2k-1}^{p+2k} - 1 \equiv -1 \pmod p\\ a_{p+2k+1} &= a_{p+2k}^{p+2k+1} - 1 \equiv (-1)^{\mathrm{even}} - 1 \equiv 0 \pmod p. \end{align*}$ This completes the induction.

Now we apply the LTE lemma. Notice that as $(p-1)p^{k-1} - 1$ is odd, we have $a_{(p-1)p^{k-1}-1} \equiv -1 \pmod p$ . Then by LTE lemma,
$\begin{align*} \nu_p\left(a_{(p-1)p^{k-1}}\right) &= \nu_p\left(a_{(p-1)p^{k-1}-1}^{(p-1)p^{k-1}} - 1\right) \\ &= \nu_p\left(a_{(p-1)p^{k-1}-1}^{p-1} - 1\right) + \nu_p\left(p^{k-1}\right) \\ &\geq 1+k-1 = k \end{align*}$ as $p \mid a_{(p-1)p^{k-1}-1}^{p-1} - 1$ by our above claim. Thus, we have exhibited a term that is a multiple of $p^k$ , as needed.

Now we deal with the case $p \mid a_{p-2}$ ; this case is similar. We have
$\begin{align*} a_{p-1} &= a_{p-2}^{p-1} - 1 \equiv -1 \pmod p \\ a_p &= a_{p-1}^p - 1\equiv -2 \pmod p\\ a_{p+1} &= a_p^{p+1} - 1 \equiv (-2)^{p+1} - 1 \equiv 3 \pmod p \end{align*}$ as $(-2)^{p-1} \equiv 1 \pmod p$ . In particular, I claim that for all $k \geq 2$ , we have $a_{p-1 + k} \equiv a_k \pmod p$ . We will induct again; the base case $k=2$ is illustrated above. For the inductive step,
$\begin{align*} a_{p+k} &= a_{p-1+k}^{p+k} - 1 \\ &\equiv a_k^{p+k} - 1 \pmod p \\ &\equiv a_k^{k+1} - 1 \pmod p \\ &\equiv a_k \pmod p \end{align*}$ as $a_k^{p+k} \equiv a_k^{k+1}$ holds always. This completes the induction.

By iterating this above claim, we have $a_i \equiv a_j \pmod p$ for sufficiently large $i, j$ if $i \equiv j \pmod {p-1}$ .

Now we look at $a_{(p-2)p^{k-1}}$ . Notice that as $(p-2)p^{k-1} \equiv p-2 \pmod {p-1},$ we have $a_{(p-2)p^{k-1}} \equiv a_{p-3} \pmod p$ . But as $p \mid a_{p-2}$ , we have
$p \mid a_{p-2} = a_{p-3}^{p-2} - 1 \iff a_{p-3}^{-1} \equiv 1 \pmod p \iff a_{p-3} \equiv 1 \pmod p.$ Then by LTE lemma again,
$\begin{align*} \nu_p\left(a_{(p-2)p^{k-1}}\right) &= \nu_p\left(a_{(p-2)p^{k-1}-1}^{(p-2)p^{k-1}} - 1\right) \\ &= \nu_p\left(a_{(p-2)p^{k-1} - 1}^{p-2} - 1\right) + \nu_p\left(p^{k-1}\right) \\ &\geq 1 + k-1 = k. \end{align*}$ So the term $a_{(p-2)p^{k-1}}$ is a multiple of $p^k$ , as needed.

This post has been edited 1 time. Last edited by HamstPan38825, Mar 21, 2024, 12:53 AM

Z K Y

The post below has been deleted. Click to close.

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

5419 posts

#13 h Mar 20, 2024, 4:53 PM

Y by

Will I be deducted for replacing the above rigorous inductions with the first few terms? It should be pretty obvious (for the period $2$ case each term only depends on the previous; and for the period $p-1$ case it's simply FLT -- I mentioned "FLT" for the latter).

Z K Y

The post below has been deleted. Click to close.

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

PRMOisTheHardestExam

409 posts

PRMOisTheHardestExam

#14 h Mar 20, 2024, 5:10 PM

Y by

similar sequence in israel olympiad

Z K Y

The post below has been deleted. Click to close.

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

1389 posts

#15 h Mar 20, 2024, 6:51 PM

Y by

Solution

This post has been edited 5 times. Last edited by VicKmath7, Mar 20, 2024, 8:24 PM

Z K Y

The post below has been deleted. Click to close.

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

3369 posts

#16 h Mar 20, 2024, 7:09 PM • 1 Y

Y by megarnie

We fix $p$ and prove the result. Let $n$ be the smallest index such that $a_n \equiv 0 \pmod p$

Claim: $1 < n < p-1$

Note that $a_{p-1} = a_{p-2}^{p-1} -1 \equiv 0 \pmod p$ for $p \nmid a_{p-2}$ . Note that if $a_{p-1} \neq 0 \pmod p$ then $a_{p-2} \equiv 0 \pmod p$ , so we have proven the claim.

Now, if $n$ is even, then the sequence $a_i$ ends up cycling as $a_i \equiv 0 \pmod{p}$ for $i$ even, and $a_i \equiv -1 \pmod p$ for $i$ odd. Now taking $a_{p^{k} - p^{k-1}} \equiv a_{p^k - p^{k-1}-1}^{\varphi(p^k)} - 1 \equiv 0 \pmod{p^k}$ as $p^{k} - p^{k-1} - 1$ is odd.

If $n$ is odd, we have $a_{n+1} \equiv -1 \pmod p$ and $a_{n+2} \equiv -2 \pmod p$ , so $a_i$ essentially cycles with order $n+1$ as $n+3$ is even. If $p-1 \neq 0 \pmod{n+1}$ we take $n = p^{k+1} - p^k - 1 \neq -1 \pmod{n+1}$ as usual. If $p-1 \equiv 0 \pmod{n+1}$ . This implies $a_{p-1} \equiv -1 \pmod{p} \implies p \mid a_{p-2} \implies a_{p-3} \equiv 1 \pmod{p}$

Now let $\mathcal{X} = p-2 + (p-1)\cdot(p-2)\cdot\left( \frac{p^k-1}{p-1} \right) = (p-2) \cdot p^k$

We have $a_{\mathcal{X}-1} \equiv a_{p-3} \equiv 1 \pmod p$ , so LTE is applicable. Now to finish note that $\begin{align*}v_p(a_{\mathcal{X}}) \\ = v_p(a_{\mathcal{X}-1}^{\mathcal{X}} - 1) \ge v_p(\mathcal{X}) + 1 = k\\ \end{align*}$

Z K Y

The post below has been deleted. Click to close.

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

8 posts

#17 h Mar 20, 2024, 7:48 PM • 1 Y

Y by thisismath1234

This problem was extremely trivial. I remember solving this problem during the contest like it was just yesterday. honestly i think the mop cuttoff wil be like 42 because this contest was so easy.

Z K Y

The post below has been deleted. Click to close.

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

1566 posts

#18 h Mar 21, 2024, 12:36 AM

Y by

I would greatly appreciate if somebody could look over my solution if you have time—since I already screwed up #2, I’d like to not have screwed up #3 as well.

Although this should be read forward from Claim 1 to Claim 3, the solution itself is much more motivated when read in reverse from Claim 3 to Claim 1.

Let $a(n)$ be the sequence defined by $a(1)=2$ and $a(n+1)=(a(n))^{n+1}-1$ for each integer $n\geq 1$ . Suppose that $p>2$ is a prime and $k$ is a positive integer. Prove that some term of the sequence $a(n)$ is divisible by $p^k$ .

Claim 1: Fix a prime $p$ . If $a(\ell(p - 1) - 2) \equiv 1 \pmod{p}$ for all $\ell \ge 1$ (if $p = 3$ then for all $\ell \ge 2$ ), then for all integers $k \ge 1$ , then there exists a term of the sequence $a(n)$ divisible by $p^k$ .
Proof: Let $\ell$ be the modular inverse of $p - 1$ modulo $p^k$ . Then, $\ell(p - 1) - 1 \equiv 1 - 1 \equiv 0 \pmod{p^k}.$ By the recursive rule given, $a(\ell(p - 1) - 1) \equiv a(\ell(p - 1) - 2)^{\ell(p - 1) - 1} - 1 \pmod{p^k}.$ Since $p \mid a(\ell(p - 1) - 2) - 1$ (assumed), the conditions for LTE are met. Using it, we get that
$\begin{align*} \nu_p(a(\ell(p - 1) - 1)) &= \nu_p\bigl(a(\ell(p - 1) - 2)^{\ell(p - 1) - 1} - 1^{\ell(p - 1) - 1})\bigr) \\ &= \nu_p(a(\ell(p - 1) - 2)) + \nu_p(\ell(p - 1) - 1) \\ &\ge k + 1. \end{align*}$ Thus, by letting $n = \ell(p - 1) - 1$ , we have a term of the sequence $a(n)$ divisible by $p^k$ , as desired $\blacksquare$

By Claim 1, we may assume that there exists a value of $\ell$ such that $a(\ell(p - 1) - 2) \not \equiv 1 \pmod{p}$ .

Claim 2: Fix an odd prime $p$ . Assuming there exists a value of $\ell$ such that $a(\ell(p - 1) - 2) \not \equiv 1 \pmod{p}$ , then there exists an even integer $n$ such that $p \mid a(n)$ .
Proof: Let $\ell$ be such. Notice that if $p \mid a(\ell(p - 1) - 2)$ , then we would be done by letting $n := \ell(p - 1) - 2)$ which is even. Thus, from now on assume that $p \nmid a(\ell(p - 1) - 2)$ .

By the recursive rule,
$a(\ell(p - 1) - 1) \equiv a(\ell(p - 1) - 2)^{\ell(p - 1) - 1} - 1 \pmod{p}.$ Suppose for the sake of contradiction that $a(\ell(p - 1) - 1) \equiv 0 \pmod{p}$ . Then, the congruence becomes $a(\ell(p - 1) - 2)^{\ell(p - 1) - 1} \equiv 1 \pmod{p}.$ Multiply both sides by $a(\ell(p - 1) - 1)$ . This becomes
$a(\ell(p - 1) - 2)^{\ell(p - 1)} \equiv a(\ell(p - 1) - 2) \pmod{p}.$ By Fermat’s Little Theorem, since $p \nmid a(\ell(p - 1) - 2)$ , we have that $a(\ell(p - 1) - 2)^{p - 1} \equiv 1 \pmod{p}$ . Plugging this into the LHS, we get that $1 \equiv a(\ell(p - 1) - 2) \pmod{p}.$ Since this directly contradicts the assumption that $a(\ell(p - 1) - 2) \not \equiv 1 \pmod{p}$ , it must be that $p \nmid a(\ell(p - 1) - 1)$ .
Again, by the recursive rule, we have that $a(\ell(p - 1)) \equiv a(\ell(p - 1) - 1)^{\ell(p - 1)} - 1.$ Since $p \nmid a(\ell(p - 1) - 1)$ , by Fermat’s Little Theorem, $a(\ell(p - 1) - 1)^{p - 1} \equiv 1 \pmod{p}$ . Plugging this in, we get that $a(\ell(p - 1)) \equiv 1^{\ell} - 1 \equiv 0 \pmod{p}.$ Thus, by letting $n := \ell(p - 1)$ , we have found an even $n$ such that $p \mid a(n)$ .

Claim 3: Fix an odd prime $p$ . If there exists an even integer $n$ such that $p \mid a(n)$ , then for all integers $k \ge 1$ , there exists an integer $m$ such that $p^k \mid a(m)$ .
Proof: Suppose that $a(n) \equiv 0 \pmod{p}$ . By the recursive rule, $a(n + 1) \equiv a(n)^{n + 1} - 1 \equiv -1 \pmod{p^{n + 1}}.$ Again by the recursive rule, using the fact that $n$ is even, $a(n + 2) \equiv a(n + 1)^{n + 2} - 1 \equiv (-1)^{n + 2} - 1 \equiv 0 \pmod{p^{n + 1}}.$ So, $p^{n + 1} \mid a(n + 2)$ . Repeating this process, we get that $p^{(n + 1)(n + 3)} \mid a(n + 4)$ . By induction, we have that $(n + 1)(n + 3)\cdots (n + (2 \ell - 1)) \le \nu_p(a(n + 2\ell))$ for all $\ell \ge 1$ . For sufficiently large $\ell$ and fixed $k$ , we have that $(n + 1)(n + 3) \cdots (n + (2\ell - 1)) \ge k$ . Thus, by letting $m := n + 2\ell$ for sufficiently large $\ell$ , we are done.

By joining the three claims, we have proven the original problem.

This post has been edited 2 times. Last edited by solasky, Mar 21, 2024, 12:41 AM

Z K Y

The post below has been deleted. Click to close.

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

337 posts

#19 h Mar 22, 2024, 3:19 AM

Y by

plang2008 wrote:

If $p\nmid a(m\varphi(p^k) - 1)$ for some integer $m$ then the conclusion is obvious. Therefore, assume $p\mid a(m\varphi(p^k) - 1)$ for all $m$ .

We can assume $p\mid a(m\varphi(p) - 1)$ . If not, then $a(m\varphi(p)) \equiv 0 \pmod p$ , and since $\varphi(p)$ is even, we have $a(m\varphi(p) + 1)\equiv -1 \pmod p$ , $a(m\varphi(p) + 2)\equiv 0 \pmod p$ , repeating, which finishes because $m\varphi(p^k) - 1$ is odd.

Now, we claim $a(m\varphi(p) - 2) \equiv 1 \pmod p$ . This is because $(a(m\varphi(p) - 2))^{m\varphi(p) - 1} - 1 \equiv 0\pmod p$ , and by orders, we must have $a(m\varphi(p) - 2) \equiv 1 \pmod p$ .

We claim $p^k\mid a(p^{k-1} (p-2))$ . Notice that $p^{k-1} (p-2) - 1 \equiv - 2 \pmod{\varphi(p)}$ , so $a(p^{k-1} (p-2) - 1)\equiv 1 \pmod p$ , which can be written as $dp + 1$ for some integer $d$ .

Finally, expanding $(dp + 1)^{p^{k-1} (p-2)}$ , by binomial theorem, every term vanishes $\pmod{p^k}$ , so it is equivalent to $1\pmod{p^k}$ .

The binomial was motivated by the solution I had for 2024 AIME I 13... in contest (after like over an hour oops) I tried to recreate the solution to that problem and just seeing how binomials worked. The difference is here is that the residue $\bmod~p$ is fixed while in the AIME problem the exponent is fixed. Realizing why the AIME problem worked (most terms of the binomial vanish), I quickly realized that the exponent must be divisible by $p^{k-1}$ . A quick CRT led to the desired exponent and I was able to solve and write this up with 5 minutes left.

I forgot LTE existed

Z K Y

The post below has been deleted. Click to close.

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

424 posts

#20 h Mar 22, 2024, 3:37 AM • 2 Y

Y by megarnie, deduck

i knew LTE existed but i forgot the statement and didnt know how to use it

Z K Y

The post below has been deleted. Click to close.

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

1437 posts

#21 h Mar 22, 2024, 9:14 PM

Y by

I cannot believe I missed this in contest, I think this might be due to faksesolving p2 multiple times before finally figuring out a working solution to it.

In contest progress:
Case 1: $a(p - 2 \pmod {p - 1}) \neq 0 \pmod p$
Then, $a(p - 1) \equiv 0 \pmod p$ \implies $a(\text{odd}) \equiv -1 \pmod p$ (parity reasons) which implies $a(m(p - 1)p^{k - 1} - 1) \equiv -1 \pmod p$ for large $m$ or $a(m(p - 1)p^{k - 1}) \equiv 0 \pmod {p^k}$ by Euler's Theorem.
__________

Case 2: $a(p - 2 \pmod {p - 1}) \equiv 0 \pmod p$
$a(p - 3 \pmod {p - 1}) \equiv 1 \pmod p$ by FLT and inverses. Now by CRT, consider $n \equiv p - 3 \pmod {p - 1}$ and $n \equiv 0 \pmod {p^k}$ and by LTE, $a(n + 1) \equiv 0 \pmod {p^k}$ .

This post has been edited 11 times. Last edited by pi_is_3.14, Apr 9, 2024, 6:55 AM

Z K Y

The post below has been deleted. Click to close.

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

682 posts

#22 h Mar 25, 2024, 2:54 AM

Y by

Uhhhh what.

Okay so redefine the sequence by $\{a\}_i$ for $i \geq 1$ , with $a_ 1 = 2$ . Then we note that,
$\begin{align*} a_{\ell+1} = (a_\ell)^{\ell + 1} - 1 \end{align*}$ Anyways now we take cases on whether $p \mid a_{p-2}$ . If not then note that,
$\begin{align*} a_{p - 1} \equiv (a_{p-2})^{p-1} - 1 &\equiv 0 \pmod{p}\\ a_p \equiv (a_{p - 1})^p - 1 &\equiv -1 \pmod{p}\\ a_{p + 1} \equiv (a_p)^{p+1} - 1 &\equiv 0 \pmod{p} \end{align*}$ Thus all $a_{p + 2k + 1} \equiv 0 \pmod{p}$ . Lifting the exponent then guarantees the sequence is unbounded modulo $p$ .

Otherwise we have $p \mid a_{p-2}$ ; in fact we may assume that $p \mid a_{(p - 1)m - 1}$ for all $m$ . To see this if we assume otherwise we find,
$\begin{align*} a_{(p - 1)m} \equiv (a_{(p - 1)m - 1})^{(p - 1)m} - 1 &\equiv 0 \pmod{p}\\ a_{(p - 1)m + 1} \equiv (a_{(p - 1)m})^{(p - 1)m + 1} - 1 &\equiv - 1\pmod{p}\\ a_{(p - 1)m + 2} \equiv (a_{(p - 1)m + 1})^{(p - 1)m + 2)} - 1 &\equiv 0 \pmod{p} \end{align*}$ whence our previous argument would suffice. Thus for all $m$ we have $p \mid a_{(p - 1)m - 1}$ . Then as $p \nmid a_{(p - 1)m - 2}$ lifting the exponent we find,
$\begin{align*} \nu_p(a_{(p - 1)m - 1}) = \nu_p\left((a_{(p - 1)m - 2})^{(p - 1)m - 1} - 1\right) = \nu_p(a_{(p - 1)m - 2} - 1) + \nu_p((p - 1)m - 1) \end{align*}$ Now taking $m$ satisfying the congruence,
$\begin{align*} (p - 1)m \equiv 1 \pmod{p^k} \end{align*}$ which clearly exists as $\gcd(p - 1, p^k) = 1$ we find,
$\begin{align*} \nu_p(a_{(p - 1)m - 1}) = \nu_p(a_{(p - 1)m - 2} - 1) + \nu_p((p - 1)m - 1) \geq k \end{align*}$ as desired. This demonstrates the result for all $k$ so we're done.

Remark: Basically tweaking LTE till it works. Fell into the trap of thinking that a sequence can't be periodic for a while and failed on showing that can't be the case (probably because it's not true), but other than that the problem was fine.

This post has been edited 2 times. Last edited by Shreyasharma, Mar 25, 2024, 2:58 AM

Z K Y

The post below has been deleted. Click to close.

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

Marius_Avion_De_Vanatoare

55 posts

Marius_Avion_De_Vanatoare

#23 h Mar 25, 2024, 12:23 PM

Y by

The first term of the sequence is not relevant.
Rewrite the identity as $a_{n}=a_{n-1}^n-1$
taking $n$ to be a multiple of $p-1$ in the last identity we see by F.L.T that either $a_{n(p-1)}$ or $a_{n(p-1)-1}$ is divisible by $p$ .
If it ever happens such that $a_{n(p-1)}$ is divisible we see by easy induction that from then on for all the even indices the array is divisible by $p$ and for all odd indices it is $-1$ mod $p$ , and by taking $n=2p^{\alpha}$ for large enough $\alpha$ we conclude by L.T.E.
Else see that $a_{(p-1)n-2}$ is 1 mod $p$ always, and by taking $n$ so that $(p-1)n-2$ is divisible by $p^{\alpha}$ for large enough ${\alpha}$ (by C.R.T. or just considering modular inverses) we are done by L.T.E. again.

Z K Y

The post below has been deleted. Click to close.

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

2502 posts

ATGY

#24 h Mar 28, 2024, 11:33 AM

Y by

Case 1: $a_{p - 2} \neq 0\mod{p}$ :

By FLT, we have $a_{p - 1} = {a_{p - 2}}^{p - 1} - 1 \equiv 0 \pmod{p}$ , $a_{p} = a_{p - 1}^{p} - 1 \equiv -1\mod{p^p}$ . By FLT again, $a_{p + 1} \equiv 0\mod{p^p}$ , and this continues for $p + 1, p + 3, \dots$ (even indices) until we find a term that divides $p^k$ , so we are done for this case.

Case 2: $a_{p - 2} \equiv 0\mod{p}$ :

Firstly notice that $a_{p - 1} \equiv -1\mod{p}$ , $a_{p} \equiv -2\mod{p}$ , $a_{p + 1} \equiv 3\mod{p}$ , and $a_{p + 1} \equiv a_{2} \mod{p}$ , meaning that the sequence is periodic with period $p - 1$ . Now, notice that:
${a_{p - 3}}^{p - 2} \equiv 1 \pmod{p} \implies {a_{p - 3}}^{-1} \equiv 1 \pmod{p} \implies a^{p - 3} \equiv 1 \pmod{p}$ It is not hard to find a construction, notice that $(p - 2)p^{k - 1} \equiv 1\mod{p - 1} \implies a_{(p - 2)p^{k - 1}} \equiv a_{p - 3}\mod{p}$ .

Since it's $1\mod{p}$ , we can use LTE.
$\begin{align*} v_p(a_{(p - 2)p^{k - 1}}) &= v_p(a_{(p - 2)p^{k - 1}-1}^{(p - 2)p^{k - 1}} - 1) \\ &\hfill=v_p(a_{(p - 2)p^{k - 1}-1} - 1) + v_p((p - 2)p^{k - 1}) \\ &\hfill\geq k \end{align*}$
So, we are done.

Z K Y

The post below has been deleted. Click to close.

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

424 posts

#25 h Jun 16, 2024, 8:24 PM • 4 Y

Y by blueberryfaygo_55, megarnie, AtharvNaphade, lpieleanu

ban
Thanks plang2008 for the help.

Fix a prime $p$ and a positive integer $k$ .

Note that $p-1\mid p^{k-1}(p-2)+1$ . If $p\nmid a(p^{k-1}(p-2))$ , by FlT we have $a(p^{k-1}(p-2)+1)\equiv 0\pmod{p}$ . We claim that $p^r\mid a(p^{k-1}(p-2)+2r-1)$ . We apply induction on $r$ with the base case trivial. For the induction step, note that $a(p^{k-1}(p-1)+2r)\equiv -1\pmod{p^{r+1}}$ since $p-1\geq 2$ . Since $p^{k-1}(p-2)+2r+1$ is even, it follows that $a(p^{k-1}(p-1)+2r+1)\equiv 0\pmod{p^{r+1}}$ , as desired.

If $p\mid a(p^{k-1}(p-2))$ , we have
$a(p^{k-1}(p-2)-1)^{p^{k-1}(p-2)}-1\equiv 0\pmod{p}$ so $a(p^{k-1}(p-2)-1)\equiv 1\pmod{p}$ by FlT. By LTE,
$\nu_p\left(a(p^{k-1}(p-2)-1)^{p^{k-1}(p-2)}-1\right)=\nu_p\left(a(p^{k-1}(p-2)-1)-1\right)+\nu_p(p^{k-1}(p-2))\geq k,$ as desired. $\square$

Z K Y

The post below has been deleted. Click to close.

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

886 posts

#26 h Jul 27, 2024, 3:22 AM • 2 Y

Y by EpicBird08, dolphinday

Thanks to @epicbird08 for the help

$\textbf{Case 1: For even } m \text{ , } p^k \mid a(m)$ $a(m+1) \equiv (a(m))^{m+1} -1 \equiv -1 \pmod p^k$ $a(m+2) \equiv (a(m+1))^{m+2} -1 \equiv 0 \pmod p^{k+1}$ Therefore, if $p^k \mid a(m), p^{k+1} \mid a(m+2).$
$\textbf{Case 2: For even } m \text{ , } p^k \nmid a(m)$ Suppose there exists $m$ such that
$m \equiv -1 \mod p-1$ and $p \nmid a(m)$ .
Then:
$a(m) \equiv 0 \pmod p$ Due to Fermat's Little Theorem.
This means that $p-1$ is even so $m+1$ is even which is a contradiction.
If $m \equiv -1 \mod p-1$
Then:
$0 \equiv (a(m-1))^m-1 \pmod p$ And therefore:
$1 \equiv a(m-1) \pmod p$ We can rearrange the formula for $a(m)$ to yield:
$a(m) = a(m-1)^{m}-1.$ Note that since $a(m-1) \equiv 1 \pmod p$ , we can apply Lifting the Exponent.
Therefore, we have that:
$v_p(a(m-1)-1)+v_p(m).$ We can freely alter $v_p(m)$ . We want this to ideally be $1 \pmod p^k$ .
We want $v_p(m) \geq k$ . Therefore:
$m \equiv 0 \pmod p^k.$ And,
$m \equiv -1 \pmod {p-1}$
This is possible by the Chinese Remainder Theorem and thus we are done.

Z K Y

The post below has been deleted. Click to close.

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

757 posts

#27 h Aug 27, 2024, 8:53 PM • 1 Y

Y by radian_51

I remember somehow incorporating $1434$ into my in-contest writeup. Maybe I used a different approach 5 months ago?

Subjective Rating (MOHs) $\text{[math]}$

Attachments:

Z K Y

The post below has been deleted. Click to close.

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

795 posts

#28 h Sep 23, 2024, 5:13 PM • 1 Y

Y by dolphinday

For an arbitrary odd prime $p$ , first suppose $p \nmid a_{p-2}$ . Then FLT gives
$a_{p-1} \equiv 0 \pmod p \implies a_p \equiv -1 \pmod{p^p} \implies a_{p+1} \equiv 0 \pmod{p^p} \implies \ldots,$
from which we get a tower of $p$ powers, which clearly finishes. Notice this approach works for any index $i \equiv -1 \pmod{p-1}$ such that $p \nmid a_i$ .

Otherwise, suppose we always have $p \mid a_i$ when $i \equiv -1 \pmod{p-1}$ . Then
$a_i = a_{i-1}^i-1 \implies a_{i-1}^i \equiv 1 \implies a_{i-1}^{-1} \equiv 1 \implies a_{i-1} \equiv 1 \pmod p$ $\implies v_p(a_i) = v_p(a_{i-1}^i-1) = v_p(a_{i-1}-1) + v_p(i) \ge v_p(i) + 1.$
Thus we can simply set $i$ to be multiples of arbitrarily high powers of $p$ through CRT to finish. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

351 posts

#29 h Oct 27, 2024, 1:59 AM

Y by

wait this isn't that bad

Fix an arbitrary prime $p > 2$ .

Case 1: Some even $n$ exists where $a(n) \equiv 0 \pmod{p}$ .

Suppose this particular value is $n = 2t$ . Note that the values $a(2t), a(2t + 1), \dots$ oscillate between $0$ and $-1$ repeatedly in $\pmod{p}$ , so for every $m \ge t + 1$ by LTE we have
$\nu_p \Bigl(a(2m) \Bigl) = \nu_p \Bigl(a(2m - 1)^{2m} - 1 \Bigl) = \nu_p \Bigl(a(2m - 1)^2 - 1 \Bigl) + \nu_p (m)$ which can clearly reach arbitrarily large values, so we have proven the claim in this case.

Case 2: No even $n$ exists where $a(n) \equiv 0 \pmod{p}$ .

First note that $p = 3$ is covered by the above case. Now observe that for all $n \equiv p - 2 \pmod{p - 1}$ , we must have $p \mid a(n)$ as otherwise, FLT gives
$a(n + 1) \equiv a(n)^{n + 1} - 1 \equiv 1 - 1 \equiv 0\pmod{p}$ which cannot occur since $n + 1$ is divisible by $p - 1$ which is even. Now for all $n \equiv p - 3 \pmod{p - 1}$ , we have
$a(n)^{p - 2} \equiv 1 \equiv a(n)^{p - 1} \pmod{p} \implies a(n) \equiv 1 \pmod{p}.$ To finish, by LTE, for all $n \equiv p - 2 \pmod{p - 1}$ we have
$\nu_p \Bigl(a(n) \Bigl) = \nu_p \Bigl(a(n - 1)^n - 1 \Bigl) = \nu_p \Bigl(a(n - 1) - 1 \Bigl) + \nu_p(n)$ and by CRT we can easily find an $n$ that reaches arbitrarily large $\nu_p$ values whilst being $p - 2 \pmod{p - 1}$ , so again we have proven the claim.

We have exhausted all cases, and we are done.

This post has been edited 2 times. Last edited by blueprimes, Nov 29, 2024, 8:09 PM

Z K Y

The post below has been deleted. Click to close.

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

1018 posts

bjump

#30 h Nov 27, 2024, 3:23 AM • 2 Y

Y by KevinYang2.71, KenWuMath

Consider an arbitrary odd prime $p$ . If $p \mid a(p-2)$ then $a(p-1) \equiv -2 \pmod{p}$ , $a(0) \equiv -2 \pmod{p}$ , and $a(p+1) \equiv (-2)^2 + 1 \equiv a(3) \pmod{p}$ , we get that this is periodic mod $p$ so that $a(k(p-1)-1) \equiv 0 \pmod{p}$ for all $k\ge 1$ . Now by LTE $\nu_p (a(k(p-1)-1)) = \nu_p (a(k(p-1)-1)^{k(p-1)-1}-1) = \nu_{p} (a(k(p-1)-1) -1 ) + \nu_{p} (k(p-1)-1)$ so by taking $k \equiv (p-1)^{-1} \pmod{p^k}$ for sufficiently large $k$ we can get arbitrarily high powers of $p$ to divide this. Also the previous application of LTE works because $a(k(p-1)-1)^{k(p-1)-1}-1 \equiv 0 \pmod{p} \iff a(k(p-1)-1)^{-1} -1 \equiv 0 \pmod{p} \iff a(k(p-1)-1) -1 \equiv 0 \pmod{p}$ . Now if $a(p-2) \not \equiv 0 \pmod{p}$ then $a(p-1) \equiv a(p-2)^{p-1}-1 \equiv 0 \pmod{p}$ . Then $a(p) \equiv -1 \pmod{p}$ , and $a(p+1) \equiv 0 \pmod{p}$ , and $a(p+2) \equiv -1 \pmod{p}$ ... $a( \text{odd}) \equiv -1 \pmod{p}, a(\text{even}) \equiv 0 \pmod{p}$ . For odds and evens greater than or equal to $p-1$ . Now consider $a(2k(p-1)$ , by LTE $\nu_p (a(2k(p-1))) = \nu_p (a(2k(p-1)-1)^{p-1}-1) + \nu_p(2k)$ so by taking $k$ with sufficiently many factors of $p$ we are finished with the problem.

Z K Y

The post below has been deleted. Click to close.

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

D4N13LCarpenter

13 posts

D4N13LCarpenter

#31 h Jan 18, 2025, 2:05 PM • 1 Y

Y by Vahe_Arsenyan

We start by proving the following:
Claim. For all $p>2$ there exists $k$ such that $p\mid a_k$ .
Proof. Notice that $a_{p-1}=(a_{p-2})^{p-1}-1.$ If $p\mid a_{p-2}$ , then we are done. If this isn't the case check that $(a_{p-2})^{p-1}\equiv 1 \pmod{p}$ by Fermat's Little Theorem, implying that $p\mid a_{p-1}$ . Either case we have proven the claim.
This leaves us with two possibilities, $p\mid a_{p-1}$ or $p\mid a_{p-2}$ . We treat them separately.

Case 1. $p\mid a_{p-1}$ .
Let $k=\nu_p(a_{p-1})$ . This yields $a_p\equiv -1\; mod\; p^{kp}$ . But now, since $p+1$ is even, we get that $a_{p+1}=(a_p)^{p+1}-1\equiv (-1)^{p+1}-1=1-1=0 \pmod{p^{kp}}$ So $\nu_p(a_{p+1})\geq kp$ . However, note that since $p+1$ is also even, we can keep repeating this procedure to get that, effectively, $\nu_p(a_n)$ is unbounded.

Case 2. $p\mid a_{p-2}$ .
This is equivalent to saying that $\forall k, p\mid a_{k(p-1)-1}$ , since, the argument used to prove our Claim works for any pairs of the form $(k(p-1), k(p-1)-1)$ , and if in any moment $p\mid k(p-1)$ , Case 1 finishes the proof since $k(p-1)$ is even. Hence $a_{k(p-1)-1}=(a_{k(p-1)-2})^{k(p-1)-1}-1$ implies $(a_{k(p-1)-2})^{k(p-1)-1}\equiv 1 \pmod{p}$ . However, we also have $(a_{k(p-1)-2})^{k(p-1)}\equiv 1 \; mod\; p$ by Fermat's Little Theorem. Combining both yields $a_{k(p-1)-2}\equiv 1 \pmod{p}$ . Now note that we can apply Lifting The Exponent to get $\nu_p((a_{k(p-1)-2})^{k(p-1)-1}-1)=\nu_p(a_{k(p-1)-2}-1)+\nu_p(k(p-1)-1).$ But since $\nu_p(k(p-1)-1)$ is unbounded we have finished.

This post has been edited 2 times. Last edited by D4N13LCarpenter, Jan 18, 2025, 2:08 PM

Z K Y

The post below has been deleted. Click to close.

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

2534 posts

#32 h Mar 12, 2025, 2:50 AM • 1 Y

Y by dolphinday

quite dissapointing i did not solve this problem in the contest (even more unfortunate that i screwed up the writeup of the evens case

)

We split this problem into two cases: when there is an even value of $x$ such that $p \mid a(x)$ and when there doesn't.

If there exists a value of $x =2i$ such that $p \mid a(2i)$ , we have

$a(2i+2) = ((a(2i))^{2i+1}-1)^{2i+2}-1 \equiv 0 \pmod{p^{2i+1}}.$
In particular, $p \mid a(2i+2)$ , so we can inductively find that

$a(2i+2k+2) = ((a(2i+2k))^{2i+2k+1}-1)^{2i+2k+2} \equiv 0 \pmod{p^{2i+2k+1}}.$
Setting $k$ to be arbitrarily large solves this case. Notice that

$a(p-1) = (a(p-2))^{p-1} - 1 \equiv 0 \pmod{p},$
unless $p \mid a(p-2)$ . Thus, $p-1$ is our desired even value of $x$ except when $p \mid a(p-2)$ .

In that case, $a(p) \equiv 2 \pmod{p}$ , so one can easily confirm that the sequence is periodic modulo $p$ with period $p-1$ by using Fermat's Little Theorem and induction. Suppose that $m = n(p-1)$ for some value of $n$ . We have that $p \mid a(m-1)$ , so

$a(m-1) = (a(m-2))^{m-1} -1 \equiv 0 \pmod{p}$ $\implies (a(m-2))^{m-1} \equiv 1 \pmod{p}$
Obviously $a(m-2) \not\equiv 0 \pmod{p}$ , so we must have $a(m-2) \equiv 1 \pmod{p}$ . Then,

$\nu_p(a(m-1)) = \nu_p((a(m-2))^{m-1} -1) = \nu_p(a(m-2)-1) + \nu_p(m-1) = \nu_p(m-1) + 1$
by Lifting the Exponent. However, $\nu_p(m-1)$ is unbounded since we can pick a value of $n$ such that $p^k \mid m-1$ for arbitrarily large values of $k$ (which can be confirmed with Chinese Remainder Theorem), so we are done. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

172 posts

#33 h Mar 17, 2025, 5:13 PM

Y by

Solution. The structure of the recurrence somewhat reminds us of the famous Euler's Totient theorem, turns out there is a little more to that. Consider the terms with indices which are one less than multiples of $\varphi(p^k)$ . If any of them say $a(m\varphi(p^k)-1)$ is invertible over $\mathbb{Z}_{p^k}$ for some natural $m$ , then we are done as $a(m\varphi(p^k))\equiv 0\pmod{p^k}.$ Suppose there isn't one then it is certain that
$a(m(p-1)-1)= (a(m(p-1)-2))^{m(p-1)-1}-1\equiv 0\pmod{p}\qquad\text{for each $m$,}$ From the above one might agree, $\gcd(p, a(m(p-1)-2))=1$ and $a(m(p-1)-2)\equiv 1\pmod{p}$ . Wait how does that help?! Lifting the Exponent lemma (LTE for short) to the rescue my friend! Recollect that given a prime $p|a-b$ with $\gcd(a,p)=\gcd(b, p)=1$ we have
$\nu_p(a^n-b^n)=\nu_p(a-b)+\nu_p(n),$ where $\nu_p()$ denotes the $p-$ adic valuation. We then have,
$\nu_p((a(m(p-1)-2))^{m(p-1)-1}-1) = \nu_p(a(m(p-1)-2)-1)+\underbrace{\nu_p(m(p-1)-1)}_{\text{can take arbitrarily large values}}.$ Claim 1. The value of $\nu_p({m(p-1)-1})$ can be made arbitrarily large with a right choice for $m$ .
Proof. Easily follows from an elementary result. As $\gcd(p-1,p^k)=1$ , Bézout's lemma (or more precisely a corollary) assures the existence of two positive integers $x,y$ such that $x(p-1)-1=yp^k$ . And $\nu_p(x(p-1)-1)\ge k$ , hence the claim.

By claim 1 we have a valid construction for $m$ with $p^k |a(m(p-1)-1)$ and we are done. $\square$

Comment. The fact that $a(1)=2$ is just not necessary.

This post has been edited 1 time. Last edited by anudeep, Mar 18, 2025, 3:27 AM

Z K Y

The post below has been deleted. Click to close.

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

15 posts

#34 h Mar 17, 2025, 9:36 PM

Y by

Solution

We begin by proving the base case where $k = 1$ , meaning that for every prime number $p > 2$ , there exists a positive integer $n_p$ such that $p$ divides $a(n_p)$ . To establish this, we use the given problem condition:

$a(p-1) = \left( a(p-2) \right)^p - 1.$
Applying Fermat’s Little Theorem (FLT), we analyze two cases. If $a(p-2) \equiv 0 \pmod{p}$ , we can simply set $n_p = p-2$ , and the condition is immediately satisfied. Otherwise, FLT guarantees that

$(a(p-2))^p \equiv a(p-2) \pmod{p}.$
Substituting this into the problem condition, we get

$a(p-1) = a(p-2)^p - 1 \equiv a(p-2) - 1 \equiv 0 \pmod{p}.$
This implies that setting $n_p = p-1$ also satisfies the condition. In both cases, we have successfully identified $n_p$ for each prime $p$ , completing the proof for $k = 1$ .

To generalize, we define a prime $p$ as \textit{good} if there exists some positive integer $i$ such that $p \mid a(2i)$ , and \textit{bad} otherwise. We now proceed by considering these two cases separately.

Case 1: $p$ is a good prime.

By assumption, there exists some integer $i$ such that $p \mid a(2i)$ , which means we can write $a(2i) = xp$ for some integer $x$ . Now consider the next term in the sequence:

$a(2i+1) = (xp)^{2i+1} - 1.$
Expanding this, we obtain:

$a(2i+2) \equiv \left( (xp)^{2i+1} \right)^{2i+2} -1 = (-1)^{2i+2} -1 \equiv 0 \pmod{p^{2i+1}}.$
This directly implies that $p$ divides $a(2i+2)$ , and by a straightforward induction argument, we can conclude that $p$ will divide infinitely many terms of the sequence. Taking sufficiently large values of $m$ guarantees that $p^{2i+2m-1} \mid a(2i + 2m)$ , solving the problem for good primes.

Case 2: $p$ is a bad prime.

Since $p$ is bad, it follows that $p \nmid a(2i)$ for all positive integers $i$ . Consider the integer $z = x(p-1)$ for some positive integer $x$ , and plug in $n = z - 1$ into the given problem condition:

$a(z) = \left( a(z-1) \right)^z - 1.$
If $a(z-1) \not\equiv 0 \pmod{p}$ , then by FLT, the exponentiation ensures that $a(z) \equiv 0 \pmod{p}$ , which contradicts our assumption that $p$ is bad. This forces $a(z-1) \equiv 0 \pmod{p}$ .

Plugging in $n = z-2$ into the problem condition, we obtain:

$a(z-1) \equiv \left( a(z-2) \right)^{z-1} - 1 \equiv 0 \pmod{p}.$
From this, we deduce:

$(a(z-2))^{z-1} \equiv 1 \pmod{p}.$
If $a(z-2) \equiv 0 \pmod{p}$ , then the above equation does not hold, contradicting FLT. Thus, we must have $(a(z-2))^z \equiv 1 \pmod{p}$ , and consequently, $a(z-2) \equiv 1 \pmod{p}$ .

To resolve this contradiction, we invoke the Chinese Remainder Theorem. There must exist a value of $x$ such that $x$ satisfies $z \equiv 1 \pmod{p^k}$ for sufficiently large $k$ . Setting $z = 1 \pmod{p^k}$ and using the exponent-lifting lemma, we establish:

$\nu_p(a(z-1)) = \nu_p((a(z-2))^{z-1} - 1) = \nu_p(a(z-2) - 1) + \nu_p(z-1).$
Since $p^k$ divides $z - 1$ , it follows that $p^k$ must also divide $a(z-1)$ . Choosing arbitrarily large values of $k$ ensures that $p^k$ divides infinitely many terms in the sequence, solving the problem for bad primes.

Having covered both cases, we conclude that the given statement holds for all primes $p > 2$ , thereby completing the proof. $\square$

This post has been edited 1 time. Last edited by jcoons91, Mar 17, 2025, 9:37 PM

Z K Y

The post below has been deleted. Click to close.

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

cursed_tangent1434

621 posts

cursed_tangent1434

#35 h Apr 22, 2025, 4:35 PM

Y by

For each odd prime $p$ , by Fermat's Little Theorem either $p \mid a_{p-2}$ or
$a_{p-1}=a_{p-2}^{p-1}-1 \equiv 1 - 1 \equiv 0 \pmod{p}$ Thus, we always have some term divisible by $p$ . Now, we split into two cases.

Case 1 : If $p \mid a_{p-1}$ , then note
$a_p=a_{p-1}^p-1 \equiv 0-1 \equiv -1 \pmod{p}$ and
$a_{p+1} = a_p^{p+1} -1 \equiv (-1)^{p-1}-1 \equiv 0 \pmod{p}$ since $2 \mid p-1$ . Hence, by induction it follows that $p\mid a_i$ for all even $i \ge p-1$ and $a_i \equiv -1 \pmod{p}$ for all odd $i > p-1$ . Thus, for all $k \ge 1$ ,
$a_{p^k(p-1)-1}= a_{p^k(p-1)-1}^{p^k(p-1)}-1 \equiv 1-1 \equiv 0 \pmod{p^{k+1}}$ by Euler's Generalization of Fermat's Little Theorem and since $p^k(p-1)-1$ is odd, $\gcd(a_{p^k(p-1)-1},p)=1$ which proves the result.

Case 2 : If $p \mid a_{p-2}$ , then note,
$\begin{align*} a_{p-1}&=a_{p-2}^{p-1}-1 \equiv -1 \pmod{p}\\ a_{p} &= a_{p-1}^p-1 \equiv (-1)^p-1 \equiv -2 \equiv -a_1 \pmod{p}\\ a_{p+1} &= a_p^{p+1} -1 \equiv a_p^2 -1 \equiv a_1^2-1 = a_2 \pmod{p}\\ & \vdots \\ a_{2p-3} &= a_{2p-4}^{2p-3}-1 \equiv a_{2p-3}^{p-2}-1 \equiv a_{p-3}^{p-2}-1 = a_{p-2}\equiv 0 \pmod{p} \end{align*}$ Now, since $2p-3$ is odd, again repeating this process, we have that $a_{i} \equiv 0 \pmod{p}$ for all $i \equiv -1 \pmod{p-1}$ . Further, if $a_{p-2+r(p-1)} \equiv 0 \pmod{p}$ we may note have $a_{p-2+2(p-1)-1} \equiv 0 \pmod{p}$ for any positive integer $r$ as this implies
$0 \equiv a_{p-2+r(p-1)}=a_{p-2+r(p-1)-1}^{p-2+r(p-1)}-1 \equiv 0 -1 \equiv -1 \pmod{p}$ which is a clear contradiction. However thus,
$\begin{align*} 0 \equiv a_{p-2+r(p-1)} &=a_{p-2+r(p-1)-1}^{p-2+r(p-1)}-1 \pmod{p}\\ a^{p-2}_{p-2+r(p-1)-1} & \equiv 1 \pmod{p}\\ \frac{1}{a_{p-2+r(p-1)-1}} & \equiv 1 \pmod{p}\\ a_{p-2+r(p-1)-1} & \equiv 1 \pmod{p} \end{align*}$ for all positive integers $r$ . Now, for each integer $k \ge 1$ consider an index $i$ such that $p^k \mid i$ and $i \equiv -1 \pmod{p-1}$ which exists by the Chinese Remainder Theorem. Then,
$a_i=a_{i-1}^i -1 = \left (a_{i-1}^{\frac{i}{p^k}}\right)^{p^k}-1$ By the Lifting the Exponent Lemma we have,
$\nu_p(a_{i-1}^i-1) = \nu_p(a_{i-1}^\frac{i}{p^k}-1) + \nu_p(p^k) \ge k+1$ since $a_{i-1}^\frac{i}{p^k}-1 \equiv (1)^\frac{i}{p^k}-1 \equiv 0 \pmod{p}$ as $i-2 \equiv -2 \pmod{p-1}$ . Thus, the result is also proven in this case and we are done.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a