Diophantine equation: $7^x=3^y-2$
I've tried using mods but nothing is working on this one: solve in positive integers $x,y$ the diophantine equation $7^x=3^y-2$.
Solution 1:
Here is a bit ugly solution to this. First, note that $(x,y) = (1,2)$ is a solution. Now suppose $x \geq 2$. We have, $$ 3^y \equiv 2 \pmod{49}. $$ Now, using Euler's theorem, we deduce $$ 3^{\phi(49)}\equiv 1 \pmod{49} \implies 3^{42}\equiv 1 \pmod{49}. $$ Now, we will observe that $3^{21}\equiv (-1)\pmod{49}$, since $3^{21} \equiv (3^{5})^4 \times 3\equiv -1\pmod{49}$.Now with some little algebra we obtain that $3^{26} \equiv 2 \pmod{49}$. Hence, $$ y\equiv 26\pmod{42}. $$ Now, we will turn our attention to modulo $43$. With similar tricks again, we observe that $$ 3^{26}\equiv 15 \pmod{43} \implies 7^y \equiv 13 \pmod{43}. $$ But the values $7^y$ can take in modulo $43$ are given by: $$ 7,6,-1,-7,-6,1 $$ and repeats itself. Hence, $7^y \equiv 13 \pmod{43}$ is not satisfied.
Thus the equation does not have any solution other than the aforementioned one.
Solution 2:
Remark: the following treatize seems to be some overkill, and might become reduced to the format of the earlier answer of @Aaron . However such reduced answers are individually bound to the given example and lack generality and as I think: intuitivity. So I deduce the proof here with the lengthy scheme which can be generalized to any such problem of this structure. (A more extensive introduction can be found at my homepage)
We use that we already know a first solution $2 = 3^2-7^1$ and reorder $$ 7^x -7^1 = 3^y - 3^2 \\ \; \\ {7^{x-1} -1 \over 3^2} = {3^{y-2} - 1 \over 7} $$
such that, with $v=x-1$ and $w=y-2$ we search for $v,w \gt 0 $ satisfying $$ {7^v -1 \over 3^2} = {3^w - 1 \over 7} \tag 1 $$
Here, in the numerator on the lhs the primefactor $3$ must occur twice but is not allowed to occur thrice, and in the numerator on the rhs the primefactor $7$ must occur once but is not allowed to occur twice - in both cases because of the impossibility of the occurence of the primefactors on the other side.
This can be discussed (even in iteration) using the concept of "order of cyclic subgroups" because we know by P. Fermat and L. Euler, that primefactors occur in such expressions cyclically and increasingly with increasing $v$ and $w$.
Excurs To be able to look into joint modular conditions efficiently by a systematic algebra, I proposed at different places a little notation-scheme for the exponent of a primefactor $p$ in an expression like $b^n-1$ :
Divisibility: define $ [n:p] = \begin{cases} 1 & \text{if } p \mid n \\ 0 &\text{if } p \nmid n\end{cases} \qquad$ (known as "Iverson"-bracket)
Valuation: define $ \{ n , p \}=e \qquad $ where $n=p^e q^f r^g \cdots $ is the primefactorization of $n$
With this we proceed
Order: define $\lambda_{p,b} = \min(n) \qquad $ implicitely by $[b^n-1:p]=1$
I omit the second or both suffices when it or they are obvious from contextFirst exponent: define $\alpha_{p,b} = \{b^{\lambda_{p,b}}-1,p \}$
Second exponent: define $\beta_{p,b} = \{b^{\lambda_{p,b}}+1,p \}$
Finally we find with this that the general form for the existence of
- an odd primefactor $p$ is $\qquad\qquad\quad \{b^n -1,p\} = [n:\lambda_{p,b}](\alpha_{p,b} + \{n,p \})$
- the primefactor $p=2$ is for odd $b$: $ \quad \{b^n -1,2\} = \alpha_{2,b} + [n:2](\beta_{2,b}-1+ \{n,2 \})$
With this we can analyze the primefactor-decompositions in both sides (lhs and rhs) in $(1)$ which must be equal in an attempted solution for some $v$ and $w$. The proof of nonexistence of a nontrivial solution $v,w \gt 0$ is then derived from the impossibility that both sides can have the same primefactorization.
End excurs
First we find the required structure of $v$ which allows the primefactor $3$ exactly to the second power in the numerator of the lhs. In general we have:
$$ \{7^n - 1, 3\} = [n:1](1 + \{n,3\}) \tag {2.1} $$
That means by $[n:1]$ that for any $n$ divisible by $1$ the expression has a primefactor $3$ and by $1+\{n,3\}$ that whenever $n$ has $3$ to some power $m$ as primefactor then the expression has it to the power of $1+m $.
In the rhs of (1) cannot occur the primefactor $3$ so the numerator of the lhs must exactly cancel the denominator, thus we need that $\{7^v-1,3\}=2$ and by equalling $[v:1](1+\{v,3\})=2$ we find, that $\{v,3\}=1$ ($v$ must contain the primefactor $3$ exactly once) and thus we can restate the lhs
$$ {7^{3 v_0} - 1 \over 3^2} \qquad \text{where } [v_0:3]=0 \tag {2.2}$$
Analoguously we look at the rhs of (1) and the structure of $w$ which allows the primefactor $7$ exactly once. In general we have:
$$ \{3^n - 1, 7\} = [n:6](1 + \{n,7\}) \tag {3.1} $$
so to have in the numerator of the rhs the primefactor $7$ exactly once we need
$$ {3^{6w_0} - 1 \over 7} \qquad \text{where } [w_0:7]=0 \tag {3.2} $$
and we must solve for $v_0,w_0$ such that
$$ {7^{3v_0} -1 \over 3^2} = {3^{6w_0} - 1 \over 7} \tag 4$$
The key-idea is now to check in (4) for the other involved primefactors, that either they occur to the same powers at both sides or that we need to adapt the exponents in the lhs and rhs such that the equality becomes reality. But adapting the exponents includes then new/more other primefactors and at one moment this leads to the inclusion of more primefactors $3$ in the lhs or of $7$ in the rhs. Then we'll have a contradiction, because this cannot be compensated on the other side of the equation.
We begin looking at the primfactor $2$. In general we have
$$
\{7^n -1 ,2\} = 1+[n:2](3-1+ \{n,2 \}) = 1+2[n:2]+ \{n,2 \} \\
\{3^n -1 ,2\} = 1+[n:2](2-1+ \{n,2 \}) = 1+1[n:2]+ \{n,2 \}
$$
which means for the current case
$$ \begin{eqnarray}
\{7^{3v_0} -1 ,2\} &= 1+2[ 3v_0:2]+ \{3v_0,2 \} && \text{ lhs}\\
\{3^{6w_0} -1 ,2\} &= 1+ [ 6w_0:2]+ \{6w_0,2 \} &= 3+ \{w_0,2\} & \text{ rhs}\\
\end{eqnarray}$$
To adapt the both sides $v_0$ must at least be even. Then we get with $v_0 = 2v_1$:
$$ \begin{eqnarray}
\{7^{6v_1} -1 ,2\} &= 1+2[ 6v_1:2]+ \{6v_1,2 \} &= 4+ \{v_1,2\} & \text{ lhs} \\
\end{eqnarray}$$
Now the rhs must be adapted, introducing $w_0 = 2w_1$ is required
$$ \begin{eqnarray}
\{3^{12w_1} -1 ,2\} &= 1+ [ 12w_1:2]+ \{12w_1,2 \} &= 4+ \{w_1,2\} & \text{ rhs}\\
\end{eqnarray}$$
So we shall have equality in lhs and rhs for the primefactor $2$ if and only if $\{v_1,2\} = \{w_1,2\}$ , for instance, if $v_1$ and $w_1$ are both odd.
Our desired equality can now be written as
$$ {7^{6v_1} -1 \over 3^2} = {3^{12w_1} - 1 \over 7} \tag 5$$
and if $v_1 = w_1 = 1$ we have the primefactorizations
$$ \begin{eqnarray}
{7^{6\cdot 1} -1\over 3^2} &= 2^4 \cdot 19 \cdot 43 \\
{3^{12\cdot 1}-1 \over 7^1} &= 2^4 \cdot 5 \cdot 13 \cdot 73 \\
\end{eqnarray} $$
We see, that after canncelling of denominators $3^2$ and $7$ our equation (5) looks well for the primefactor $2$ - but not yet for the other primefactors.
Last step: If we only adapt the rhs for the primefactor $43$ now, we arrive at the expected contradiction.
In general we have for the primefactor $p=43$ $$ \{3^n -1 ,43\} = [n:42](1+ \{n,43 \} $$ so to have $ \{3^{12w_1} -1 ,43\} = 1 $ we must have $[w_1:7]=1$ and with $w_2 = 7 w_1$ we have: $$ \begin{array} {lll} \{3^{12 \cdot 7 \cdot w_2} -1 ,43\} &= [12 \cdot 7 \cdot w_2:42](1+ \{12 \cdot 7 \cdot w_2,43 \}) \\ &=1 + \{84 w_2,43 \}\\&=1 + \{ w_2,43 \} \\ \end{array}$$ But now for the primefactor $7$ we get $$ \begin{array} {lll}\{3^{12 \cdot 7 \cdot w_2} -1 ,7\} &= [12 \cdot 7 \cdot w_2:6](1+ \{12 \cdot 7\cdot w_2, 7\}) \\ &=1+ \{12 \cdot 7\cdot w_2, 7\} \\ &=2+ \{ w_2, 7\} \end{array} $$ and the rhs of (5) has after cancellation by the denominator one remaining instance of the primefactor $7$ which cannot be compensated in the lhs of (5). $$ \begin{array} {} {7^{6v_1} -1 \over 3^2} &\equiv {3^{12\cdot 7w_2} - 1 \over 7} &\equiv 0 \pmod {43} \\ {7^{6v_1} -1 \over 3^2} &\equiv {3^{12\cdot 7w_2} - 1 \over 7} &\equiv 0 \pmod {2^4}\end{array} \tag 6$$ but $$ \begin{array} {} {7^{6v_1} -1 \over 3^2} &\not \equiv {3^{12\cdot 7w_2} - 1 \over 7} &\pmod 7\end{array} \tag 7$$
The last incongruence proves the nonexistence of a nontrivial solution of (1).