Find all positive integers $x,y,z$ and $t$ such that $2^x3^y+5^z=7^t$.
Problem
Source: JBMO 2012
Tags: modular arithmetic, number theory, greatest common divisor, algebra
flare
27.06.2012 21:07
First, assuming $x \ge 2$, we take the equation mod 4 and see $t$ is even. Then we take the equation mod 3 and see $z$ is even. We make the following substitutions: $t=2m$ and $z=2n$. So \[2^x3^y = (7^m - 5^n)(7^m+5^n)\] Note, going mod 4 again we see that one of $7^m-5^n$ or $7^m+5^n$ has many factors of 2, and the other has only 1. Similarly, with mod 3, we see that one of the things at the right is divisible by $3^y$, and the other has no factors of 3. Now we can consider a few cases -- $7^m - 5^n$ is either $2, 2^{x-1},$ or $3^y(2)$. It cannot be $2^{x-1}3^y$ since it would be greater than $7^m + 5^n$ in that case. $7^m = 5^n + 2^{x-1}$ and $7^m = 5^n + 2$ are classic Diophantine equations with the only solution being $x=2, m=1, n=1$.
Proof of 7^a = 5^b + 2^c... changed the variable names for convenienceFirst assume $c \ge 2$. Then by mod 4, $a$ is even. Mod 3, $b$ and $c$ have same parity. Mod 5, $a$ and $c$ have same parity... so all 3 are even. Going difference of squares on $7^a - 2^c = 5^b$, with $a=2l$ and $c=2d$, \[(7^l-2^d)(7^l+2^d) = 5^b\] Mod 5, however, says both factors cannot be powers of 5. Only possibility is $7^l - 2^d = 1$. Mod 3 says that this is impossible. So now we have to consider when $c=1$ or $7^a = 5^b + 2$. If $b \ge 2$, Mod 25 yields a contradiction. So $b=1$ as well, and thus we have the only solutions to be $\boxed{a=1, b =1, c=1}$ as we desired to prove.
However, if $x=2$, then the $7^m-5^n$ has only one factor of 2, meaning $7^m+5^n$ has more factors of 2, so $x$ isn't actually 2. However, with $m$ and $n$ we can simply solve and find the solution of $x=3, y=1, z=2,t=2$.
Proof of 7^m = 5^n + 2*3^yNow we have the case of $7^m = 5^n + 2*3^y$ (we actually had to consider this anyways since we previously assume $x \ge 2$). By mod 4, $m$ must be odd. Mod 3, we have $n$ to be even. Mod 8, $y$ is odd. We go mod 5 now and have a contradiction! Thus, we are done with this case, and this also considers when $x=1$.
So the only solution is $\boxed{x=3, y=1, z=2, t=2}$.
mavropnevma
28.06.2012 00:59
Modulo $3$ we must have $(-1)^z \equiv 5^z \equiv 7^t \equiv 1 \pmod{3}$, so we must have $z$ even. Modulo $7$ we must have $2^x\cdot (-4)^y \equiv - (-2)^z \pmod{7}$, thus $(-1)^y 2^{x+2y} \equiv -2^z \pmod{7}$, that is $2^{x+2y-z} \equiv -(-1)^y \pmod{7}$, which requires $y$ odd, since $2^m \equiv -1 \pmod{7}$ has no solution. Let us first decide on $x=1$. Modulo $4$ we must have $2\cdot 3^y \equiv -1 + (-1)^t \pmod{4}$, therefore we must have $t$ odd. Then modulo $5$ we must have $2\cdot (-2)^y \equiv 2^t \pmod{5}$, thus $2^{1+y-t} \equiv -1 \pmod{5}$, impossible since $1-y+t$ is odd, while $2^m \equiv -1 \pmod{5}$ requires $m$ even. So we continue with $x\geq 2$. Modulo $4$ we must now have $1 \equiv (-1)^t \pmod{4}$, therefore we must have $t = 2t'$ even. Remember $z=2z'$ is also even, so $2^x\cdot 3^y = (7^{t'} - 5^{z'})(7^{t'} + 5^{z'})$. But $\gcd(7^{t'} - 5^{z'}, 7^{t'} + 5^{z'}) = 2$. Now, if $3\mid 7^{t'} - 5^{z'}$, then we must have $2\cdot 3^y + 5^{z'} = 7^{t'}$ (since $7^{t'} + 5^{z'} > 2$), which is the impossible case of the above. Therefore we need consider $7^{t'} - 5^{z'} = 2^{x'}$ (with, in parallel, $7^{t'} + 5^{z'} = 2^{x-x'}\cdot 3^{y}$), where $x'=1$ or $x'= x-1$. After this effort, we enter a new phase. Modulo $3$ we now need have $7^{t'} - 5^{z'} \not \equiv 0 \pmod{3}$, whence $z'$ odd. But modulo $16$ we do have $2^x\cdot 3^y = 49^{t'} - 25^{z'} \equiv 8 \pmod{16}$, and this forces $\boxed{x=3}$. One obvious possibility is $t'=z'= x'=1$, with the solution $\boxed{2^3\cdot 3^1 + 5^2 = 7^2}$. The case $7^{t'} - 5^{z'} = 2^{2}$ cannot occur, since modulo $3$ we would have $2\equiv 7^{t'} - 5^{z'} = 2^{2} \equiv 1 \pmod{3}$, absurd; so the only case left is $7^{t'} - 5^{z'} = 2$ (with $7^{t'} + 5^{z'} = 2^{2}\cdot 3^y$). This case remains to be settled. We can kill it with Lifting The Exponent lemma. We have $7^{t'} - 1 = 2\cdot 3^y$. Since $v_3(7-1) = 1$, and by LTE $v_3(7^{t'} - 1) = 1 + v_3(t') = y$, we will need $3^{y-1} \mid t'$, but then, for $y>1$, we would have $7^{t'} - 1 > 2\cdot 3^y$. Therefore $y=1$, and the only solution is the one boxed above. A much simpler continuation is however available. Write $7^{t'} - 5^{z'} = 2 = 7 - 5$, or $7(7^{t'-1} - 1) = 5(5^{z'-1} - 1)$. Since the order of $7$ modulo $5$ is $4$, it means that $4 \mid t'- 1$, and then $2^5 \cdot 3\cdot 5^2 = 7^4 - 1 \mid 7^{t'-1} - 1$, so $5^2 \mid 5(5^{z'-1} - 1)$, only possible when $z'= 1$ and $t'=1$, which is the boxed solution above. I do not particularly relish this type of problem; with sterile manipulations galore modulo carefully chosen numbers, in the chase for some contradiction.
Particle
02.08.2012 09:10
This problem offers you two options: either do huge calculations or use Zsigmondy's theorem. Though none of them is attractive, but, at my point of view, the first option is much more honorable. My Solution:
Taking mod $6$ shows $z$ is even.So let $z=2n$.Now we'll divide the problem into two cases:
Case:1 $x=1$
Taking mod $4$ and $5$ shows that $t$ must be odd and $y$ must be even.So\[2\cdot 3^y\equiv 4,1,2(mod\; 7)\]
\[5^z\equiv 4,2,1(mod\; 7)\]From the last two statements we can say \[2\cdot 3^y+5^z\equiv 1,2,3,4,5,6\not \equiv 0(mod\; 7)\]So a contradiction and no solution from here.
Case: 2 $x>1$
Taking mod $4$ gives $t$ is even.So let $t=2m$.And so the equation can be re-written as \[2^x3^y=(7^m+5^n)(7^m-5^n)\]
Now let $7^m+5^n=2^p3^q$ and $7^m-5^n=2^{x-p}3^{y-q}$.From the last two equation we find that
\[7^m=2^{p-1}3^q+2^{x-p-1}3^{y-q}.......(i)\]
\[5^n=2^{p-1}3^q-2^{x-p-1}3^{y-q}........(ii)\]
Notice that $2^{p-1}3^q$ and $2^{x-p-1}3^{y-q}$ must be co-prime so that $(i)$ and $(ii)$ remains valid.Hence $q=0$ or $y=q$ and $p=1$ or $x-p=1$.
Case: $2.1$ $q=0$
In this case $p=1$ is not possible because $7^m+5^n\ge 12>2=2^13^0=2^p3^q$.So $x-p=1$ and so $(i)$ and $(ii)$ convert into these equations:
\[7^m=2^{p-1}+3^y..........(iii)\]
\[5^n=2^{p-1}-3^y...........(iv)\]
By taking mod $3$, from $(iii)$ we can say $p-1$ is even, i.e. $x$ is even.(Because $x-p=1$)Also remember $p>1$.So $4|2^{p-1}$.
Now taking mod $3$ and mod $4$ on $(iv)$ gives $y$ is odd and $n$ is even.Let $p-1=2r$ and $n=2s$.So $(iv)$ can be re-written as $(2^r+5^s)(2^r-5^s)=3^y$.Notice that both $2^r+5^s$ and $2^r-5^s$ are powers of three.But their gcd must divide $2\cdot 5^s$.Then $2^r-5^s=3^0=1.......(v)$.If $r>1$, then a contradiction can be brought by taking mod $4$ on $(v)$.So $r=1$.But it will lead us to $(s,y)=(0,1)$which crosses the conditions.So no solution from here.
Case: $2.2$ $q=y$ Here also two cases: Case: $2.2.1$ $p=1$
$(i)$ and $(ii)$ will convert into these equations:
\[7^m=3^y+2^{x-2}.........(vi)\]
\[5^n=3^y-2^{x-2}..........(vii)\]
We must have $x>2$ because $(vi)$ is not valid otherwise.Taking mod $3$ on $(vi)$ gives $x-2$ is even.So $4|2^{x-2}$.Let $x-2=2d$.
Now taking mod $4$ on $(vii)$ gives $y$ is also even.So let $y=2c$.Then $(vii)$ can be re-written as
\[5^n=(3^c-2^d)(3^c+2^d)........(viii)\]Notice that both $3^c-2^d$ and $3^c+2^d$ are powers of five.But their gcd must divide $2^{d+1}$.Then $3^c-2^d=1$.So we can write \[5^n=3^c+2^d=(2^d+1)+2^d=2^{d+1}+1\]\[\Longrightarrow 2^{d+1}=5^n-1\] Notice that \[5^{2k}-1\equiv (-1)^{2k}-1\equiv 0(mod\; 6)\]
But $3\not |2^{d+1}$.So n is odd.So let $n=2u+1$.Then \[5^n-1\equiv 5^{2u}5-1\equiv 5-1=4(mod\; 8)\]As $d>0$, So $d+1=2$ and $d=1$.Then $n=c=1$.So $y=2,x=4$.But $(vi)$ is not satisfied with these values of $x$ and $y$.So again no solution.
Case: $2.2.2$ $x-p=1$
$(i)$ and $(ii)$ will convert into these equations:
\[7^m=2^{p-1}3^y+1...........(ix)\]
\[5^n=2^{p-1}3^y-1............(x)\]
From our previous case we know $p>1$.But if $p>2$, then by taking mod $4$ we can bring a contradiction to $(x)$.So $p=2$ and $x=3$.
So $(x)$ can be converted to\[5^n=2\cdot 3^y-1.......(xi)\]
It follows from LTE that $3^{y-1}|n$.But then \[5^n\ge 5^{3^{y-1}}\ge 2\cdot 3^y-1\]with equality iff $y=1$.(The last inequality can be brought by simple induction or calculus so this part is skipped)Then $n=m=1$.So $t=z=2$.
solution(s):
So only solution is $(x,y,z,t)=(3,1,2,2)$ which is a correct solution.
MilosMilicev
02.11.2016 16:45
Very very easy for P4. The better problem is when x, y, z and t are non-negative
MathAllTheWay
24.02.2018 16:32
Particle wrote: This problem offers you two options: either do huge calculations or use Zsigmondy's theorem. Though none of them is attractive, but, at my point of view, the first option is much more honorable. My Solution:
Taking mod $6$ shows $z$ is even.So let $z=2n$.Now we'll divide the problem into two cases:
Case:1 $x=1$
Taking mod $4$ and $5$ shows that $t$ must be odd and $y$ must be even.So\[2\cdot 3^y\equiv 4,1,2(mod\; 7)\]\[5^z\equiv 4,2,1(mod\; 7)\]From the last two statements we can say \[2\cdot 3^y+5^z\equiv 1,2,3,4,5,6\not \equiv 0(mod\; 7)\]So a contradiction and no solution from here.
Case: 2 $x>1$
Taking mod $4$ gives $t$ is even.So let $t=2m$.And so the equation can be re-written as \[2^x3^y=(7^m+5^n)(7^m-5^n)\]Now let $7^m+5^n=2^p3^q$ and $7^m-5^n=2^{x-p}3^{y-q}$.From the last two equation we find that
\[7^m=2^{p-1}3^q+2^{x-p-1}3^{y-q}.......(i)\]\[5^n=2^{p-1}3^q-2^{x-p-1}3^{y-q}........(ii)\]Notice that $2^{p-1}3^q$ and $2^{x-p-1}3^{y-q}$ must be co-prime so that $(i)$ and $(ii)$ remains valid.Hence $q=0$ or $y=q$ and $p=1$ or $x-p=1$.
Case: $2.1$ $q=0$
In this case $p=1$ is not possible because $7^m+5^n\ge 12>2=2^13^0=2^p3^q$.So $x-p=1$ and so $(i)$ and $(ii)$ convert into these equations:
\[7^m=2^{p-1}+3^y..........(iii)\]\[5^n=2^{p-1}-3^y...........(iv)\]By taking mod $3$, from $(iii)$ we can say $p-1$ is even, i.e. $x$ is even.(Because $x-p=1$)Also remember $p>1$.So $4|2^{p-1}$.
Now taking mod $3$ and mod $4$ on $(iv)$ gives $y$ is odd and $n$ is even.Let $p-1=2r$ and $n=2s$.So $(iv)$ can be re-written as $(2^r+5^s)(2^r-5^s)=3^y$.Notice that both $2^r+5^s$ and $2^r-5^s$ are powers of three.But their gcd must divide $2\cdot 5^s$.Then $2^r-5^s=3^0=1.......(v)$.If $r>1$, then a contradiction can be brought by taking mod $4$ on $(v)$.So $r=1$.But it will lead us to $(s,y)=(0,1)$which crosses the conditions.So no solution from here.
Case: $2.2$ $q=y$ Here also two cases: Case: $2.2.1$ $p=1$
$(i)$ and $(ii)$ will convert into these equations:
\[7^m=3^y+2^{x-2}.........(vi)\]\[5^n=3^y-2^{x-2}..........(vii)\]We must have $x>2$ because $(vi)$ is not valid otherwise.Taking mod $3$ on $(vi)$ gives $x-2$ is even.So $4|2^{x-2}$.Let $x-2=2d$.
Now taking mod $4$ on $(vii)$ gives $y$ is also even.So let $y=2c$.Then $(vii)$ can be re-written as
\[5^n=(3^c-2^d)(3^c+2^d)........(viii)\]Notice that both $3^c-2^d$ and $3^c+2^d$ are powers of five.But their gcd must divide $2^{d+1}$.Then $3^c-2^d=1$.So we can write \[5^n=3^c+2^d=(2^d+1)+2^d=2^{d+1}+1\]\[\Longrightarrow 2^{d+1}=5^n-1\]Notice that \[5^{2k}-1\equiv (-1)^{2k}-1\equiv 0(mod\; 6)\]But $3\not |2^{d+1}$.So n is odd.So let $n=2u+1$.Then \[5^n-1\equiv 5^{2u}5-1\equiv 5-1=4(mod\; 8)\]As $d>0$, So $d+1=2$ and $d=1$.Then $n=c=1$.So $y=2,x=4$.But $(vi)$ is not satisfied with these values of $x$ and $y$.So again no solution.
Case: $2.2.2$ $x-p=1$
$(i)$ and $(ii)$ will convert into these equations:
\[7^m=2^{p-1}3^y+1...........(ix)\]\[5^n=2^{p-1}3^y-1............(x)\]From our previous case we know $p>1$.But if $p>2$, then by taking mod $4$ we can bring a contradiction to $(x)$.So $p=2$ and $x=3$.
So $(x)$ can be converted to\[5^n=2\cdot 3^y-1.......(xi)\]It follows from LTE that $3^{y-1}|n$.But then \[5^n\ge 5^{3^{y-1}}\ge 2\cdot 3^y-1\]with equality iff $y=1$.(The last inequality can be brought by simple induction or calculus so this part is skipped)Then $n=m=1$.So $t=z=2$.
solution(s):
So only solution is $(x,y,z,t)=(3,1,2,2)$ which is a correct solution.
Could you please post the solution using Zsigmondy's Theorem. Thanks in advance!
Andrew.xyz
26.06.2020 10:53
We start with observing that $5^{z}\equiv 1 (mod 3)$ so $z = 2k, $where $k$ is natural. Next there are two opportunities 1) $x=1$. Then $7^{t}\equiv 3 (mod 4) \Rightarrow t$ is odd. Next $7^{t}\equiv 7 (mod 8)$ and $5^{2k}\equiv 1 (mod 8)$ so $2\times 3^{y} \equiv 6 (mod 8)$ and $y$ is odd. But now it is easy to check that there is no solutions by modulo 5. 2) $x\geq 2$. By modulo 4 we got $7^{t}\equiv 1 (mod 4)$ so $t = 2m,$ where $m$ is natural. So let $ 7^{m} - 5^{k} = 2^{a}\times 3^{b}$ and $7^{m} + 5^{k} = 2^{c}\times 3^{d}$. It is easy to see that $ 7^{m} - 5^{k}$ and $7^{m} + 5^{k}$ both can not be divisible by 4 and by 3 at the same time. So there are 4 cases. Case 1: $a = 1, b = 0$. Then we got $7^{m} - 5^{k} = 2$ (1) $7^{m} + 5^{k} = 2^{c}\times 3^{d}$ (2) So from these equations follows next equation: $5^{k} = 2^{c-1}\times 3^{d} - 1$. If $c \geq 3$ then no solutions by modulo 4. If $c = 1$ then no solutions by modulo 2, hence $c = 2$. So $5^{k} = 2\times 3^{d} - 1$ and $ 7^{m} = 2\times 3^{d} + 1$. Assume that $d \geq 2$. It is easy to get by modulo 9 that both $m$ and $k$ are divisible by 3. Using formula of difference of cubes we see that (1) has no solutions. So $d = 1$. Then immediately we got $ x = 3, y = 1, z = t = 2$. Case 2: $a = 1, d = 0$. Then we got $7^{m} - 5^{k} = 2\times 3^{b}$ (3) $7^{m} + 5^{k} = 2^{c}$ (4) So from these equations follows next equation: $5^{k} = 2^{c-1} - 3^{b}$ (5). Obviously $c \geq 4$. By modulo 4 we got that $b$ is odd. From (4) by modulo 8 we got that $m$ is odd and $k$ is even, next from this equality by modulo 3 easy to get that $c$ is odd. But then follows contradiction by modulo 5 from (5). Case 3: $c = 1, d = 0$. Of course, there is no solutions in this case. Case 4: $c = 1, b = 0$ we got two equalities: $7^{m} - 5^{k} = 2^{a}$ (6) and $7^{m} + 5^{k} = 2 \times 3^{d}$ (7). Then follows that $5^{k} = 3^{d} - 2^{a-1}$. From (7) by modulo 3 we got that $k$ is even. If $a = 1$ then no solutions by modulo 2, so $a \geq 2$. Hence from (6) by modulo 4 we got that $m$ is even. Using difference of squares formula in (6) we see that $2 \times 5^{l} = 2^{s} - 2^{r}$ for some natural $l,r,s (s \geq r)$. If $s,r \geq 2$ then no solutions by modulo 4. So $r = 1 \Rightarrow 5^{l} = 2^{s-1} -1$ and no solutions by Mihailescu's theorem. So ${x,y,z,t} = {3,1,2,2}$ is the only solution.