7
$\begingroup$

Find all positive integer solutions to $$7^y + 2 = 3^x.$$


ATTENTION: MY SOLUTION HAS A TERRIBLE MISTAKE WHICH I HAVE OVERLOOKED!

Obviously, $x > y$. Then, we have $3^x = 7^y + 2 \equiv 0 \pmod {3^y}$. Also, $$7^y = (6 + 1)^y = \sum_{k = 0}^{y} {y \choose k} 6^k \equiv \sum_{k = 0}^{y - 1} {y \choose k} 6^k \pmod {3^y}.$$ We claim that the highest power of $3$ that divides ${y \choose k}$ is at most $2$. Indeed, $$\sum_{i = 1}^{\infty} \left [\frac {y} {3^i} \right] - \left (\sum_{i = 1}^{\infty} \left [\frac {y - k} {3^i} \right] + \sum_{i = 1}^{\infty} \left [\frac {k} {3^i} \right] \right) \leqslant 2.$$ Hence, $$7^y \equiv \sum_{k = 0}^{y - 1} {y \choose k} 6^k \leqslant 2 \sum_{k = 0}^{y - 1} 6^k = \frac {2} {5} (6^y - 1).$$ Since $(5, 3^y) = 1$, we have by Euler's Theorem that $$5^{\phi (3^y)} = 5^{3^y - 3^{y - 1}} \equiv 1 \pmod {3^y}.$$ Then, $2 \cdot 3^{y - 1} \equiv \frac {2} {5} (6^y - 1) \pmod {3^y}$ and $$0 \equiv 7^y + 2 \leqslant 2 \cdot 3^{y - 1} + 2 \pmod {3^y}.$$ Take $s > 0$ an integer for which $$3^{y} s \leqslant 2 \cdot 3^{y - 1} + 2.$$ It follows from this that $0 \leqslant 3^{y} (s - 1) \leqslant 2 - 3^{y - 1}$. Hence, $y < 2$. So the solutions are $$(x, y) = (1, 0), (2, 1).$$

"Notes on Olympiad Problems", Nima Bavari, Tehran, 2006.

$\endgroup$
8
  • $\begingroup$ @someone math.stackexchange.com/help/self-answer $\endgroup$
    – user98186
    Commented Nov 29, 2015 at 12:46
  • $\begingroup$ Looks like either a homework question, or someone desperately trying to prove they are smart. $\endgroup$
    – gnasher729
    Commented Nov 29, 2015 at 12:53
  • $\begingroup$ Did you follow the link in the comment? @gnasher729 $\endgroup$ Commented Nov 29, 2015 at 12:55
  • $\begingroup$ @ThomasAndrews Thanks a lot. $\endgroup$
    – user98186
    Commented Nov 29, 2015 at 12:56
  • $\begingroup$ (+1) This was a fun (I had a hard time and used an hour darn) problem. $\endgroup$
    – rkm0959
    Commented Nov 29, 2015 at 13:59

1 Answer 1

15
$\begingroup$

Okay so I got this solution after modular bashing for an hour. This better be right.

Since the cases $x,y \le 2$ are already investigated above easily, we look at $x,y \ge 3$.

Rewrite this equation to $$7(7^{y-1}-1)=9(3^{x-2}-1)$$

Now, since $7|3^{x-2}-1$, and the order of $3$ modulo $7$ is $6$, we have $6|x-2$.

This gives $13|3^6-1|3^{x-2}-1$, so $13|7^{y-1}-1$.

Now we have $12|y-1$ since the order of $7$ modulo $13$ is $12$. This gives $19|7^{12}-1|7^{y-1}-1$.

Now we have $19|3^{x-2}-1$, so $18|x-2$, since the order of $3$ modulo $19$ is $18$.

Now $37|3^{18}-1|3^{x-2}-1$. This gives $37|7^{y-1}-1$.

Now we have $9|y-1$. Now we have $27|7^9-1|7^{y-1}-1$, since the order of $7$ modulo $37$ is $9$.

However, $9(3^{x-2}-1) \equiv -9 \pmod{27}$, so it cannot be a multiple of $27$.

We now have a contradiction, so the answer is $(x,y)=(1,0),(2,1)$, as desired. GG!!

$\endgroup$
5
  • $\begingroup$ Nice solution! +1 $\endgroup$
    – user98186
    Commented Nov 29, 2015 at 13:51
  • $\begingroup$ Could you add explanation, how you received $7 \mid 3^{x-2} - 1 \Rightarrow 6 \mid x-2$? $\endgroup$
    – Tacet
    Commented Nov 29, 2015 at 14:06
  • 1
    $\begingroup$ I will add that in. Thank you :) $\endgroup$
    – rkm0959
    Commented Nov 29, 2015 at 14:45
  • $\begingroup$ I got it. Thank you. Nice answer. +1 @NimaBavari Maybe you should accept this answer? $\endgroup$
    – Tacet
    Commented Nov 29, 2015 at 14:59
  • 1
    $\begingroup$ Gyumin, I was able to use your method on another problem, very nice. The numbers were such that I would probably not have finished without using a computer to factor numbers and find the orders of 2 and 3 mod certain primes. Here, and thank you for the technique description: math.stackexchange.com/questions/1941354/… $\endgroup$
    – Will Jagy
    Commented Sep 26, 2016 at 18:28