Solution

NikoIsLife wrote:

Solution

Euler's toitent function only works when the number is coprime.

The statement is direct for $p = 2$. Henceforth assume $p \ge 3$. Let $a_n = LHS$ and $b_n = RHS$. Note that $b_n$ is periodic with period $p$. Claim: For any modulus $m$, the sequence $c_{i,n}:=2^{2^{...^{2^{n}}}}$ ($i$ 2's) is eventually periodic $\pmod m$ with period $< m$. Proof: Proceed with induction on $i$; the base case $i=1$ is clear. Suppose the statement holds for $i-1$. Take $n$ large such that $\nu_2(c_{i,n}) > \nu_2(m)$. It suffices to show the sequence periodic $\pmod d$ where $d$ is the largest odd divisor of $m$. For this use Euler's Totient Theorem and induction hypothesis. Note that if $a_m \equiv c\pmod p$ and $b_n \equiv c\pmod p$ then $a_i \equiv c\equiv b_i\pmod p$ where $i \equiv m \pmod T$ ($T$ the period of $a_n$) and $i \equiv n \pmod p$. Therefore it suffices to show that $$\{a_n\}_{n\ge K} \cap \{b_m\}_{m\ge 1} \ne \emptyset \pmod p$$$\{b_m\}$ is the set of all numbers with order dividing $\frac{p-1}{a_1,p-1}$so it suffices to show that infinitely many $n$ satisfy $a_n^{\frac{p-1}{a_1,p-1}} \equiv 1 \pmod p$. But all even $n$ satisfy this property (the whole thing ends up being $2^{(p-1)t}$ for some $t\in \mathbb N$) so we are done.

stroller wrote: The statement is direct for $p = 2$. Henceforth assume $p \ge 3$. Let $a_n = LHS$ and $b_n = RHS$. Note that $b_n$ is periodic with period $p$. Claim: For any modulus $m$, the sequence $c_{i,n}:=2^{2^{...^{2^{n}}}}$ ($i$ 2's) is eventually periodic $\pmod m$ with period $< m$. Proof: Proceed with induction on $i$; the base case $i=1$ is clear. Suppose the statement holds for $i-1$. Take $n$ large such that $\nu_2(c_{i,n}) > \nu_2(m)$. It suffices to show the sequence periodic $\pmod d$ where $d$ is the largest odd divisor of $m$. For this use Euler's Totient Theorem and induction hypothesis. Note that if $a_m \equiv c\pmod p$ and $b_n \equiv c\pmod p$ then $a_i \equiv c\equiv b_i\pmod p$ where $i \equiv m \pmod T$ ($T$ the period of $a_n$) and $i \equiv n \pmod p$. Therefore it suffices to show that $$\{a_n\}_{n\ge K} \cap \{b_m\}_{m\ge 1} \ne \emptyset \pmod p$$$\{b_m\}$ is the set of all numbers with order dividing $\frac{p-1}{a_1,p-1}$so it suffices to show that infinitely many $n$ satisfy $a_n^{\frac{p-1}{a_1,p-1}} \equiv 1 \pmod p$. But all even $n$ satisfy this property (the whole thing ends up being $2^{(p-1)t}$ for some $t\in \mathbb N$) so we are done. could explain why $\{b_m\}$ is the set of all numbers with order dividing $\frac{p-1}{a_1,p-1}$ ?

Redacted ....

We define two functions $f,g.$ For $\forall x\ge p,$ define $$f(x)=\begin{matrix}\underbrace{2^{2^{ .^{.^{2^x}}}}}\\{\text{1397 times of 2}}\end{matrix}\mod p,$$$$g(x)=\begin{matrix}\underbrace{x^{2^{ .^{.^{2^2}}}}}\\{\text{1397 times of 2}}\end{matrix}\mod p.$$Then $f(x)$ has a period of $\varphi ^{(1397)}(p),$ $g(x)$ has a period of ${p}.$ Also, for any positive integer $A,$ let $C=\log_2\log_2f(A),$ $D=\log_2\log_Ag(A).$ When ${A}$ is large, $C>D.$ Therefore let $B=2^{2^{C-D}},$ we have $$g(B)\equiv B^{2^D}=2^{2^{C-D}\cdot 2^D}=2^{2^C}\equiv f(A)\pmod p.$$By $\gcd \left(\varphi ^{(1397)}(p),p\right)=1,$ using Chinese Remainder Theorem, there exists infinite $t\in\mathbb N_+,$ such that $$C\equiv A\pmod p,C\equiv B\pmod{\varphi ^{(1397)}(p)}.$$This leads to $f(t)\equiv g(t)\pmod p.\blacksquare$

Proposed by Yahya Motevassel