# Eulers Theorem and Diophantine Equations

Eulers Theorem says that for all coprime intergers $a,b$

$a^ {φ(b)} \equiv 1 \pmod b$.

This implies that for any $z,x$ which satisfies $\gcd(x,y)=\gcd(z,y)=1$

$x^{φ(y)}-z^{φ(y)} \equiv 0\pmod y$

However, this inspired me to ask the following:

Are there no natural solutions to $x^{φ(y)}-z^{φ(y)}= y^t$ when $\gcd(x,y)=\gcd(z,y)=1$ and $φ(y)>2$?

Or more generally,

Are there no natural solutions to $x^{φ(y)}-z^{φ(y)}= y^t$ when $φ(y)>2$?

The first question is implied by Beal`s Conjecture. However, that seemed to difficult to be used here, and it looked like it could be solved with elementary methods.

I attempted to use L.T.E when $y=p^e$ and $p$ is a prime . However, this case could easily be solved with simple factoring and modular calculation, using the fact that $φ(y)$ is divisible by 2.

However, I could not solve it for the case when $y$ had two or more prime factors.

Any help would be greatly appreciated.

• It is fairly easy to prove that if $p>3$ is a prime, then there are no pairs of positive integers $(x,z)$ such that $x^{\phi(p)} - z^{\phi(p)}$ is a power of $p$ (I can write it in an answer, if you wish). I don't think there is any simple way to extend this to non-prime $y$, though.
– A.P.
Jan 10 '16 at 16:00
• By the way, the important condition is $\gcd(x,z) = 1$. If you drop it and you find one solution $(x_0,z_0)$, then $(y^s x_0, y^s z_0)$ will be a solution for every $s \geq 0$, too. You might also be interested in a theorem by Mahler that states that if $F(X,Z) \in \Bbb{Z}[X,Z]$ is a square-free binary form of degree $n \geq 3$ (as in this case) and $p_1,\dotsc,p_r$ are distinct primes, then $$|F(x,z)| = p_1^{e_1}\dotsm p_r^{e_r}$$ has at most finitely many solutions in $x,z,e_1,\dotsc,e_r \in \Bbb{Z}$ with $\gcd(x,z)=1$.
– A.P.
Jan 10 '16 at 16:18
• @A.P. I would appreciate if you wrote an answer about the proof to the theorem by Mahler. Jan 10 '16 at 23:18

The equation $$x^{\varphi(y)} - z^{\varphi(y)} = y^t \qquad \text{s.t. }\varphi(y) > 2 \tag{1} \label{eq:1}$$ is a Thue-Mahler equation, i.e. an equation of the form $$|F(x,z)| = c p_1^{e_1}\dotsm p_r^{e_r} \qquad \text{s.t. } (x,z,e_1,\dotsc,e_r) \in \Bbb{Z}^2 \times \Bbb{Z}^r_{\geq 0} \tag{2} \label{eq:tm}$$ with $F \in \Bbb{Z}[X,Z]$ (with some extra condition), $c \in \Bbb{Z}_{>0}$, and $p_1,\dotsc,p_r$ distinct (integer) primes. These have been thoroughly studied throughout the 20th century, starting from the work of K. Mahler. In particular, in these notes (theorem 9.4) you can find a proof that $\eqref{eq:tm}$ has at most finitely many solutions when $F$ is square-free and has degree $n \geq 3$, which is enough to show that for every fixed $y$ with $\phi(y) \geq 3$ equation $\eqref{eq:1}$ has at most finitely many solutions $(x,z,t) \in \Bbb{Z}^2 \times \Bbb{Z}_{\geq 0}$ such that $\gcd(x,z)=1$. This proof, which relies on a $p$-adic version of an important and hard to prove result in diophantine approximation called the subspace theorem, has the drawback of being ineffective: it doesn't give a way to actually compute those solutions, nor to estimate their number.

Fortunately, there are many effective bounds for the number of solutions of a Thue-Mahler equation and most, if not all, are proved using some lower bound for the (possibly $p$-adic) absolute value of linear forms in logarithms, like those given by A. Baker. In principle, any of these could be used to compute by exhaustion all the solutions, though usually those bounds are so large that this approach isn't practical.

Don't loose your hope, yet! In this paper Y. Bugeaud and K. Győry proved a theorem that in our case becomes:

Fix an integer $n \geq 3$ and distinct primes $p_1,\dotsc,p_r$. If the equation $$|x^n - z^n| = p_1^{e_1} \dotsm p_r^{e_r} \tag{3} \label{eq:bg}$$ has a solution in non-negative integers $e_1,\dotsc,e_r$ and non-zero integers $x,z$ such that $|x| \neq |z|$ and $\gcd(x,z) = 1$, then $$n \leq P + 1$$ where $P = \max\{p_1,\dotsc,p_r,3\}$.

Now, note that every $(x,z,e_1,\dotsc,e_r)$ solution of $\eqref{eq:bg}$ with $\gcd(x,z) = 1$ gives infinitely many solutions of the form $$\left(x p_1^{f_1} \dotsm p_r^{f_r}, z p_1^{f_1} \dotsm p_r^{f_r}, e_1 + nf_1, \dotsc, e_r + nf_r\right)$$ and conversely every solution can be reduced to a solution with coprime $x,z$. Furthermore, there are always the solutions $(1,0,0,\dotsc,0)$ and $(0,1,0,\dotsc,0)$. Thus we'll call trivial a solution with $\gcd(x,z) \neq 1$, $x=0$, or $z=0$.

Let's assume for a moment that $y \neq 2^k$, so that the maximum prime factor of $y$ is $P_y \geq 3$. Then the above result implies that $\eqref{eq:1}$ cannot have a non-trivial solution if $$\varphi(y) > P_y + 1.$$ Writing $k = v_{P_y}(y)$ we have $\varphi(y) =: c_y \varphi(P_y^k) = c_yP_y^{k-1} (P_y - 1)$, so this condition is equivalent to $$(c_yP_y^{k-1} - 1)(P_y - 1) > 2$$ thus we know for sure that there are no solutions unless $k = 1$ and either $c_y = 1$, or $c_y = 2$ and $P_y = 3$. In other words, the only missing cases are $$y \in \{12\} \cup \{2^k : k > 2\} \cup \{p,2p : p > 2 \text{ prime}\}$$ Moreover, as you said yourself it is fairly easy to exclude the cases $y = p^e$ using the factorization $x^{2n} - z^{2n} = (x^n + z^n)(x^n - z^n)$, which leaves only the cases $y = 12$ and $y = 2p$ for some odd prime $p$.

Consider $y = 12$ and let $(\xi,\zeta,\tau)$ be a non-trivial solution of $\eqref{eq:1}$. Then $\tau > 1$ and $$12^\tau = \xi^4 - \zeta^4 = (\xi^2 + \zeta^2)(\xi^2 - \zeta^2).$$ Now, neither $3$ nor $4$ can divide $\xi^2 + \zeta^2 > 1$. But this implies $\xi^2 + \zeta^2 = 2$, hence $\xi,\zeta \in \{1,-1\}$, which is absurd because $\xi^4 - \zeta^4 \neq 0$. Therefore there are no solutions for $y = 12$.

Similarly, consider $y = 2p$ with $p > 3$ prime, so that $\varphi(y) = \varphi(p) = p-1 > 2$, and let $f := \frac{p-1}{2} > 1$. Furthermore, suppose that $(\xi,\zeta,\tau)$ is a non-trivial solution of $\eqref{eq:1}$, and note that we may assume without loss of generality that $\xi > \zeta > 0$ and $\tau > 0$, because $\phi(y) > 2$ is even. Then observe that $$\xi^{\varphi(y)} - \zeta^{\varphi(y)} = (\xi^f + \zeta^f)(\xi^f - \zeta^f) = 2^\tau p^\tau$$ and that $p$ can only divide one of $\xi^f \pm \zeta^f$. Indeed, $p$ cannot divide $\xi$ without dividing $\zeta$ (and conversely), and $\alpha^f \equiv \pm 1 \pmod{p}$ for every $\alpha \in \Bbb{Z} \setminus p\Bbb{Z}$.

Now, $p \mid \xi^f - \zeta^f$ isn't possible, because it would lead to $$\xi^f - \zeta^f < \xi^f + \zeta^f \leq 2^\tau < p^\tau \leq \xi^f - \zeta^f$$ so $p \mid \xi^f + \zeta^f$ and $\xi^f - \zeta^f = 2^\sigma$ for some $0 < \sigma \leq \tau$. Then observe that, by the result quoted above, this last equation cannot have a non-trivial solution unless $f \leq 4$, which leaves only the case $p = 5$.

• It seems that since $x^2+y^2$ cannot be divisible by 3, $x^2-y^2$ must be $3^t$. Also, since $x^2+y^2$ cannot be divisible by 4, this implies that $x^2+y^2=2$. I think that this is a rather clean approach, though I understand if this is not the approach you are looking for. Also, I am assuming that $x^4-z^4$ is a typo above? Jan 12 '16 at 23:32
• But this method does seem unapplicable for $2p$. Jan 12 '16 at 23:42
• Wow, thank you for all your effort! Jan 15 '16 at 0:46
• I tried computing Győry's bound with Sage, but even in this simple case it the bound on the variables turned out to be of the order of $\exp(10^{1040})$... way too big for me to take the computational approach.
– A.P.
Jan 15 '16 at 23:14
• If $x^4-y^4=10^t$, $(x^2-y^2)(x^2+y^2)=10^t$. Therefore, because $x^2-y^2 \equiv x^2+y^2 \pmod 2$ $x^2-y^2=2^{t-1}, x^2+y^2=2*5^t$. This implies that $x^2=5^t+2^{t-2}$. However, if $t>4$, a examination by $\pmod 8$ gives us that $5^t \equiv 1\pmod 8$. Therefore, $t \equiv 0 \pmod 2$. However, a examination modular 3 gives us that $x^2 \equiv 2^{t+1} \pmod 3$, thus implying that $t \equiv 1 \pmod 2$ A contradiction. Jan 15 '16 at 23:54