A friend of mine recently gave me the follwing diophantine equation ($k, l, etc. \in \Bbb N$) and asked me whether I could solve it, i.e. "find all solutions" (I'm still a high school student, so please bear with me and please suggest improvements regarding this question in case parts of the question should remain unclear):

$$(6k-1)2^{2n-1} = 18l-2$$

The only thing I managed to do though was reforming it to:

$$(6k-1)2^{2(n-1)} = 9l-1$$

Solving linear diophantine equation is no problem and if $n$ is set to a certain number, I would even say it is very obious to find all solutions to the resulting equation, e.g. if $n=1$ then there is a solution at every $k=3m$ and $l=2m$. But if $n$ isn't set I simply can't find an approach to this problem, at least currently. Therefore, my friend and I would really appreciate if someone could help us out on this. Thank you!


HINT $$ \frac{9l-1}{6k-1} = 4^{n-1} $$ so $${9l-1} = 4^{n-1}r$$ with some integer $r$.

For $n-1$ = 2, there are only two numbers, mod $16$, that satisfy $9l\equiv 1$

Any number that satisfies $9l=1 \pmod {64}$ must be one of eight possibilities (four cases for each of the two numbers that work mod $16$). Only one of these, $l\equiv 57$, works mod $64$.

Now try the four cases stemming from $57$, in mod $256$. You will find there is just one solution. Now move to mod $1024$ and there is again one solution.

If you keep going you may find some power $4^m$ for which there is no solution; each new power involves checking only a few numbers. Once you have a power for which there are no solutions, you can stop --- no higher power of 4 will work either.

That reduces the problem to the cases where $n-1\in\{0,1,2,3,4,\dots, m-1\}$ and you know how to handle each of those.

If you don't come to a "stopper," (and I believe you won't) you will see a pattern emerge. That may let you solve all the cases without considering individual powers past $4^{10}$ or so.


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.