4
$\begingroup$

This is another contest math-problem.

The only problem that I cannot find the way to tackle this problem.

Can anybody try to provide the solution to solve this problem?

Thanks

$\endgroup$
  • $\begingroup$ Please check that the equation is the all right now? And by the way you can check some LaTEX tutorials to make things look better $\endgroup$ – Stefan4024 Jun 15 '14 at 20:09
  • 1
    $\begingroup$ @Stefan4024,yes the equation is right. Sorry for the bad writing, Stefan. $\endgroup$ – akusaja Jun 16 '14 at 15:29
4
$\begingroup$

Since $x,y,z \in \mathbb{N}$ we get that $5|5^x7^y$, so we have: $3^z \equiv 4 \mod 5$. Since $ord_5(3) = 4$ and $3^2 \equiv 4 \pmod 5$ we get $\fbox{$z = 4n + 2$}$. Obviously $z$ is even so we have $\fbox{$z=2k$}$. Then we have:

$$5^x7^y = 3^{2k} - 4 = (3^k - 4)(3^k + 4)$$

Now let $d = (3^k - 4,3^k + 4)$, then $d$ divides their diference, so $d\mid 8$. But both numbers are obviously odd, hence $(3^k - 4,3^k + 4) = 1$. Since we have 2 different prime factors on the left side we have $4$ cases:

Case 1:

\begin{cases} 3^k - 4 = 5^x \\ 3^k + 4 = 7^y \end{cases}

Working wrt modulo 5 and 7 respectively we get $k=4n + 2$ and $k=6n + 1$, an obvious contradiction.

Case 2:

\begin{cases} 3^k + 4 = 5^x \\ 3^k - 4 = 7^y \end{cases}

Working modulo $3$ we get: $5^x \equiv 2^x \equiv 1 \pmod 3 \implies \fbox{$x=2m$}$

So we get: $3^k = (5^m - 2)(5^m + 2)$. As previously we get that the two factors on the right side are comprime. Since $5^m + 2 > 1$ we get that the only possibilty is:

\begin{cases} 5^m - 2 = 1 \\ 5^m + 2 = 3^k \end{cases}

For the first equation we have: $5^m = 3$ a contradiction.

Case 3:

\begin{cases} 3^k + 4 = 1 \\ 3^k - 4 = 5^x7^y \end{cases}

An obvious contradiction for the first equation.

Case 4:

\begin{cases} 3^k + 4 = 5^x7^y \\ 3^k - 4 = 1 \end{cases}

From the second equation we get $3^k = 5$ a contradiction, because $k \in \mathbb{N}$

Hence this equation doesn't have a solution in $\mathbb{N}$

$\endgroup$
  • 1
    $\begingroup$ You have a sign error in $3^z \equiv -4 \mod 5$. Also, you reused the name $k$ in case 1. $\endgroup$ – user2357112 Jun 16 '14 at 2:05
  • $\begingroup$ @Stefan4024, I can only find (x,y,z)= (1,0,2) as the solution. But, I cannot find the other, how can I get the other solution by using your method? thanks $\endgroup$ – akusaja Jun 16 '14 at 15:34
  • $\begingroup$ As much as I know 0 isn't a positive integer. If you want to include 0, then my approach prove that if we have solution then at least on of the exponents is 0. And the rest should not be too difficult. Can you do that on your own? $\endgroup$ – Stefan4024 Jun 16 '14 at 16:30
  • $\begingroup$ oh, yes, i forgot that 0 is not a positive integer. So, based on your 4 cases, can we conclude that this problem didn't have a solution, @Stefan4024 ? thanks $\endgroup$ – akusaja Jun 16 '14 at 19:34
  • $\begingroup$ Yes, this equation doens't have a solution in positive integers ;) $\endgroup$ – Stefan4024 Jun 16 '14 at 21:23
1
$\begingroup$

Considering the equation modulo $5$ shows that $z = 2+4m$ for some integer $m$. Considering the equation modulo $7$ shows that $z = 4 + 6n$ for some integer $n$. Thus we have $2 + 4m = 4 + 6n$. This is a linear Diophantine equation, and the solutions to the original equation may be found by first solving this.

Edit: I seem to have overlooked the fact that the linear diophantine equation reads $2m - 3n = 1$. Because of the negative sign, there are infinitely many positive solutions and thus this attack method does not seem to help.

$\endgroup$
  • $\begingroup$ Hey there :) I know a tiny bit about polynomial residues, but I am really surprised to see that exponentiation can be just as powerfully (and simply) worked. I can see how you could reduce something like 7^{n} mod 5 to 2^{n} mod 5, but then, how would you proceed in studying the behavior? I am surprised you made it so simple because I thought that studying exponentiation under a modulus is inherently a computationally difficult task to do (cryptography etc.). Sorry, I know very little about maths, but could you explain your methods a bit or lead me to a good source on this :)? Thanks! $\endgroup$ – Just_a_fool Jun 15 '14 at 20:42
  • 1
    $\begingroup$ Minor correction, you should have gotten $z = 2+4m$ and $z = 4+6n$ $\endgroup$ – JimmyK4542 Jun 15 '14 at 20:42
  • $\begingroup$ Doh! Of course, thanks @JimmyK4542. The exponent is modulo the order of the multiplicative group, not the additive group! Silly mistake. $\endgroup$ – RghtHndSd Jun 15 '14 at 20:45
  • $\begingroup$ @Just_a_fool: Remember that something like $5 \cdot 7^y$ is always zero modulo 5. So for example, modulo 5 the equation reads $-1 = 3^z$. By writing out $z=1,2,3...$, see if you can figure out what's going on. $\endgroup$ – RghtHndSd Jun 15 '14 at 20:49
  • $\begingroup$ @rghthndsd Thanks. whoops… I see I performed the classic case of not sincerely trying a question before asking! :p $\endgroup$ – Just_a_fool Jun 15 '14 at 21:26
0
$\begingroup$

Given; $5^x \cdot 7^y +4= 3^z$ we get, $(-1)^x +1 \equiv 0 \pmod3$ hence $x$ must be odd, again, $(-1)^y \equiv (-1)^z \pmod 4$ hence $y$ and $z$ have the same parity. Again $-1 \equiv 3^z \pmod 5$ or $1 \equiv 3^{2z} \pmod 5$ hence by Euler-Fermat theorem $2|z$. Again since $y$ and $z$ are even we have, $5^x \equiv 4 \pmod 8$, since $x$ is odd, we have two cases; either $x=4k+1$ or $x=4k+3$, note that $5^{4k} \equiv 1 \pmod 8$, the two cases each yield $5^x \equiv 5 \pmod 8$ a contradiction, hence $x$ cannot be greater than $0$, i.e $x=0$. The given equation then becomes $7^{2m} +4= 3^{2n}$ or $(7^m)^2 +2^2= (3^n)^2$, a pythagora's equation with solution, $2=2uv$, $7^m=u^2-v^2$ and $3^n=u^2+v^2$ from which it is obvious that $m$ and $n$ do not exist, and hence, $y(=2m)$ and $z(=2n)$ do not exist

$\endgroup$
  • $\begingroup$ I don't see how you go from $3 \equiv 3^z \pmod 6$ to $2|z-1$. $3 \equiv 3^z \pmod 6$ only tells you that $z > 0$. $\endgroup$ – user2357112 Jun 16 '14 at 2:09
  • $\begingroup$ Wait a sec: modulo 8, $7^y$ with an even y is 1. So we get $5^x+4\equiv3^z\pmod8$. Being $z$ even, $3^z\equiv1\pmod8$, since it is $9^{\frac{z}{2}}\equiv1^{\frac{z}{2}}\pmod8$. So $5^x+4\equiv1\pmod8\implies5^x\equiv-3\equiv\fbox{$5$}\pmod8$, not 4. Am I making a mistake somewhere? $\endgroup$ – MickG Aug 18 '14 at 13:51
  • $\begingroup$ So that only gives us $x$ is odd, being that the condition for $5^{x-1}\equiv1\pmod8$, since $5^2=25\equiv1\pmod8$, but we already know that. $\endgroup$ – MickG Aug 18 '14 at 13:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.