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.

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.

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}$.

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

(wrong cuz badge)

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$

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

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$

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$

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

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.

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).

similar sequence in israel olympiad

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*}

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.

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.

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

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

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}$.

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.

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.

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.

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$

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.

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

$ $

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$

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.

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.

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.