In order to see whether I understood the concept of solving Diophantine equations I just thought of an relatively "easy" example of an equation:
Find each $(x,y) \in \mathbb{N}^2$ ( $x,y \neq 0$) such that:
$$ 3x + 1 = 8^y$$
Beforehand - I checked with a program up to $(10000, 10000)$ and the only solution is $(21, 2)$
But when I tried to solve it mathematically - I encountered a dead end.. I hope you will show me the correct path to solve this question.
My try:
So we know that $3x + 1 = (2^3)^y = 2^{3y}$ and thus:
$ 2 \mid 3x+1$ meaning that $x$ needs to be odd - or else this would not be true.
- $2 \nmid x$
Now we can look at the equation $ \text{mod 3}$:
$$ 3x + 1 \equiv 1 (\mod 3)$$
$$ 8^y = (2^{y})^3 \equiv C ( \mod 3)$$ We need to solve for $C$
Through trial and error I got the conclusion that:
$$ 2^1 \equiv 2 ( \mod 3) \\ 2^2 \equiv 1 ( \mod 3)\\ 2^3 \equiv 2 ( \mod 3) \\ \text{etc ..}$$ And so:
$$2^y \equiv 1 ( \mod 3) ~~~ \text{if} ~~~~ 2 \mid y \\ 2^y \equiv 2 ( \mod 3) ~~~ \text{if} ~~~~ 2 \nmid y$$
And because the LHS mod $3$ is $1$ : $y$ must be even.
So we can note: $x = 2k + 1$ and $y = 2l$ ($k,l \in \mathbb{N}$)
Back to the original equation:
$$ 3(2k + 1) + 1 = 8^{2l} \\ 6k + 4 = 2^{6l} $$
Thus $k$ must be even, or else $6k + 4$ will be odd which is impossible as it is equal to a power of $2$.
Continuing where we left off ( dividing by $2$):
$$ 3k + 2 = 2^{6l - 1} \\ 3k = 2^{6l - 1} -2 = 2( 2^{6l-2} - 1)$$
Note we can factor:
$$ 2^{6l -2} - 1 = (2^{3l-1} + 1 )(2^{3l-1} - 1 )$$
Here is where I stopped - I am thinking I am going through loop holes and not really making progress.. I would appreciate if you can lead me into the correct way! Thank you!
If we solve for $x$, you get
$$x = \frac{(8^y - 1)}{3}$$
and we find the pairs $$(0,0)\qquad (21,2)\qquad (1365,4)\qquad (87381,6)\qquad (5592405,8)\qquad (357913941,10)\qquad (22906492245,12)\qquad(1466015503701,14)\qquad (93824992236885,16)\qquad ...$$
I have included zero here but as you can see, any even number $y$ yields an integer for $x$.