Euler's totient function and primes I have found a formula for Euler's totient function but I have no proof. I need help to demonstrate the formula if possible.

$\phi$ denotes the Euler's totient function, $a$ denotes a natural number $>1$ and $n$ denotes a natural number multiple of $4$. If the remainder of the division of $\phi\left(a^n-2\right)+1$ by $n$ is equal to $n-1$ then $\phi(a^n-2)+1$ is always a prime number.
Example with $a=119$ and $n=20$ The remainder of the division of $\phi\left(119^{20}-2\right)+1$ by 20 is equal to 19 then $\phi\left(119^{20}-2\right)+1$ is prime.
Thanks for your answers.
 A: This is not a complete answer, but a comment gathering some low-hanging fruits.
Per Greg Martin's observation, a counterexample would have to satisfy the equation:
$$a^n - 2 = c\cdot p^k$$
with $c\in\{1,2\}$, a prime $p\equiv 3\pmod4$, and an integer $k>1$.
Below I will show that $k$ cannot be even and also cannot be a multiple of $3$, implying that $k\geq 5$ is coprime to 6.
Denoting $x:=a^{n/4}$, we rewrite the two equations as
$$x^4 - 2 = c\cdot p^k.$$
If $k$ is even, then introducing $y:=p^{k/2}$, we obtain the quartic equation
$$x^4 - 2 = c\cdot y^2.$$
In the case $c=1$, it is easy to establish absence of meaningful solutions via factoring $x^4-y^2=(x^2-y)(x^2+y)$, while in the case $c=2$ we can solve it with Magma's IntegralQuarticPoints function, showing that there are no solutions in this case either.
If $3\mid k$, then the equation is reduced to two elliptic curves (indexed by $c$):
$$Y^2 = cX^3 + 2,$$
where $Y:=a^{n/2}$ and $X:=p^{k/3}$. They have the only integral points (easily computed in Magma or Sage) $(X,Y)=(-1,1)$ for $c=1$ and
$(X,Y) \in \{ (-1,0), (1,2), (23,156)\}$ for $c=2$, neither of which gives us a solution to the original equation.
Hence, we have $\gcd(k,6)=1$ and thus $k\geq 5$.

PS. We may also notice that for $c=2$, $x$ must be even the equation takes form
$$8\left(\frac{x}2\right)^4 - p^k = 1,$$
while for $c=1$ it can be written as
$$x^4 - p^k = 2.$$
That is, $p^k$ if it exists would be the smallest of two powerful numbers that differ in 1 (OEIS A060355) or 2 (OEIS A076445).
A: For convenience "solution" shall mean "solution in integers $>2$".
Max Alekseyev's answer shows that the conjecture would become vacuously true if we could prove that the equations $x^4-2=y^n$ and $8x^4-1=y^n$ have no solutions $(x,y,n)$.
For $x^4-2=y^n$, even the existence of solutions to $X^2-2=y^n$ is a well known open problem: see end of Section 3.1 in
Le M., Soydan G. A brief survey on the generalized Lebesgue-Ramanujan-Nagell equation. arXiv preprint arXiv:2001.09617. 2020 Jan 27,
where it is conjectured that $X^2-2=y^n$ has no integer solutions.
Claim. $8x^4-1=y^n$ has no integer solutions.
Proof. Proposition 8.1 of
Bennett M.A., Skinner C.M. "Ternary Diophantine equations via Galois representations and modular forms". Canadian Journal of Mathematics. 2004 Feb;56(1):23-54, PDF
says that the only integer solution to $2X^2-1=y^n$ is $(X,y,n)=(78,23,3)$. So, if $(x,y,n)$ were a solution to $8x^4-1=y^n$ we would have $2x^2=78$ and thus $x^2=39$, contradiction. $\square$
UPDATE. The paper
Samir Siksek. "The modular approach to Diophantine equations." Number Theory: Volume II: Analytic and Modern Tools (2007): 495-527, PDF,
contains a lot of interesting pieces of information about the famous diophantine equation $x^2-2=y^n$. Here are some highlights.
We consider a priori all the integer solutions with $n\ge2$. The only known ones are $(x,y,n)=(\pm1,-1,n)$ with $n$ odd; we call these solutions trivial.
The conjecture of Le and Soydan is that there are no others.
One can clearly restrict to the case when $n$ is an odd prime; following Siksek we denote it by $p$, and write our equation
$$
x^2-2=y^p.
$$
For each integer $r$ satisfying
$$
\frac{1-p}2<r\le\frac{p-1}2
$$
consider the Thue equation
$$
(1+\sqrt2)^r(u+v\sqrt2)^p-(1-\sqrt2)^r(u-v\sqrt2)^p=2\sqrt2
$$
for the unknown integers $u$ and $v$. Arguing as Servaes in this answer we see that each solution of some of these $p$ Thue equations yields a solution to $x^2-2=y^p$. So, a priori, if we want to solve $x^2-2=y^p$ for a given $p$, we must solve these $p$ Thue equations.
But Siksek shows (Proposition 13.1) that in fact it suffices to solve the Thue equations corresponding to $p=\pm1$ (the other Thue equations have no solutions anyway).
Let us write out these two Thue equations:
$$
(\sqrt2+1)(u+v\sqrt2)^p+(\sqrt2-1)(u-v\sqrt2)^p=2\sqrt2,
$$
$$
(\sqrt2-1)(u+v\sqrt2)^p+(\sqrt2+1)(u-v\sqrt2)^p=2\sqrt2. 
$$
If $(u,v)$ is a solution to one these two equations, then we solve $x^2-2=y^p$ by setting $y:=2v^2-u^2$. Clearly $(u,v)=(1,0)$ is a solution to both of these two equations. Again we call this solution trivial, and we see that it furnishes the trivial solution to $x^2-2=y^p$.
What Proposition 13.1 says is that, conversely, if $x^2-2=y^p$, then $x+\sqrt2$ is equal to
$$
(\sqrt2+1)(u+v\sqrt2)^p\quad\text{or to}\quad(\sqrt2-1)(u+v\sqrt2)^p.
$$
Lemma 13.3 says that the Thue equations, or equivalently the equation $x^2-2=y^p$, have non nontrivial solution if $p$ is not in the range
$$
41\le p\le 1231.
$$
(Recall that $p$ is prime.)
Finally Lemma 13.2 says that any nontrivial solution to $x^2-2=y^p$ satisfies $y>(\sqrt p-1)^2$.
So, if I understand things correctly, one doesn't know if the polynomial diophantine equation
$$
x^2-2=y^{41}
$$
has a nontrivial solution, or equivalently, if at least one of the Thue equations
$$
(\sqrt2+1)(u+v\sqrt2)^{41}+(\sqrt2-1)(u-v\sqrt2)^{41}=2\sqrt2
$$
and
$$
(\sqrt2-1)(u+v\sqrt2)^{41}+(\sqrt2+1)(u-v\sqrt2)^{41}=2\sqrt2
$$
has a nontrivial solution.
A: This is a partial technical answer based on my intuition and ChatGPT. So, there are possible errors. Moreover the answer doesn't consider the modulo-1.
$\phi$ denotes the Euler's totient function, $a$ denotes a natural number $> 1$ and $n$ is a multiple of 4.
We will use a technique called "cyclotomic polynomials" to prove the conjecture (i.e the subproblem which states that there are infinitely many primes of the form of $\phi(a^n-2)+1$).
Firstly, we note that if $p$ is a prime of the form $\phi(a^n-2)+1$, then $p$ must be a factor of $a^n-1$ (by Fermat's little theorem). Therefore, $p$ cannot divide $a^k-1$ for any positive integer $k<n$, since otherwise we would have $p$ dividing $a^n-1$ but not $a^k-1$, which is impossible.
Now, consider the cyclotomic polynomial of order n:
$$\phi_n(x) = \frac{x^n-1}{x-1} = x^{n-1} + x^{n-2} + ... + x + 1$$
Since $n$ is a multiple of 4, we can write $n=4m$ for some positive integer $m$. In this case, we have:
$$a^n-1 = (a^{2m}-1)(a^{2m}+1) = (a^m-1)(a^m+1)(a^{2m}+1)$$
Note that $a^m-1$ and $a^m+1$ are both factors of $\phi_{2m}(a)$, since $\phi_2m(a)$ is the product of all irreducible polynomials over the finite field $F_{p^k}$ of degree $2m$ that have a as a root. Therefore, we have:
$$a^m-1 ≡ 0 (mod p)$$
$$a^m+1 ≡ 0 (mod p)$$
This implies that $a^2 \equiv 1 \pmod p$, since otherwise we would have $p$ dividing both $a^m-1$ and $a^m+1$, which is impossible. Therefore, we have:
$$a^n-2 \equiv (a^2)^{2m}-2 \equiv 1 (mod p)$$
which implies that $p$ divides $\phi(a^n-2)+1$
To show that there are infinitely many such primes, we need to show that there are infinitely many values of $n$ for which $a^n-2$ is not a power of $2$. This is true because there are infinitely many prime numbers that are not of the form $2^k+1$ (by Dirichlet's Theorem on arithmetic progressions), and we can choose $a$ to be any primitive root modulo such a prime. Therefore, there are infinitely many primes of the form $\phi(a^n-2)+1$, as desired.
