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

• Observations: the assumption implies that $\phi(a^n-2)\equiv2\pmod4$. The only numbers $m$ such that $\phi(m)\equiv2\pmod4$ (in other words, $2\mid\phi(m)$ but $4\nmid\phi(m)$) are ($m=4$ or) $m=p^k$ or $m=2p^k$ for an odd prime $p\equiv3\pmod4$ and a positive odd integer $k$. It's far more likely for such an integer to be a prime than to be a cube (or higher power) of a prime. I think that's all we're seeing—it's not related to the fact that $m=a^n-2$ here. In particular, there doesn't seem to be anything preventing occasional counterexamples. Commented Jun 23, 2022 at 6:12
• Welcome to Math.SE. Interesting conjecture. A few questions: 1. Why do you believe this to be true? 2. What ranges of $a,n$ have you checked? 3. How do you know that $\phi(119^{20} - 2)+1$ is prime? Commented Jun 23, 2022 at 6:12
• @Greg Martin : thanks for your observations. I don't know if it exists a counterexample, it's a conjecture that I found simply by noting that $\phi(a)+1 = 3 (mod 4)$ when $\phi(a)+1$ is prime and then I generalized the problem for $n = 4k$ ($k$ an integer). Commented Jun 23, 2022 at 6:47
• @Arkady : thanks. 1) I found this formula by noting that $\phi(a)+1 = 3 (mod 4)$ when $\phi(a)+1$ is prime and I generalized the problem (see above). 2) I have checked about 100 numbers that were primes in differents ranges (73 digits is the highest prime that I found with this formula). 3) I use wolframalpha to calculate this number and calculis.net/grand-nombre-premier to check if a number is prime. Commented Jun 23, 2022 at 6:48
• Cross-posted at MO: mathoverflow.net/q/440738 Commented Feb 16, 2023 at 19:20

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

• In the case $c=1$ we can assume $k\ge7$ prime to 30 (see this answer). Commented Feb 23, 2023 at 15:31

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

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

• This does not quite make sense, starting with a conjecture different from what is asked in the question, giving a formula for $\phi_n(x)$ that holds only for prime $n$ while $n$ is a multiple of $4$ etc. Commented Feb 22, 2023 at 21:33
• You are right. As mentioned above, I have proved there are infinitely many primes of the form $\phi(a^n-2)+1$ but without use the initial conditions (i.e when $n=4m$ with $m$ an integer $\geq 1$). This is why I said this is a subproblem. Commented Feb 22, 2023 at 22:04