0

Recreationally, I have been studying Fermat numbers and have been trying to come up with a construction to produce arbitrarily large composite Fermat numbers. It's been leading me to many Diophantine equations, which are a new and interesting topic for me.

For example, given two integers $a$ and $b$, I would like to solve for all integers $k$ which satisfy $$ak+b=2^n$$ for any natural number $n$. That is to say, when is $ak+b$ a power of 2? I'm unsure what class of Diophantine equation this falls into, hence web searching has not been very helpful. I looked up "Exponential Diophantine equations", but the results have been seemingly for different types of equations than this one.

Initially, I am not even sure when there exists a solution at all. At the very least, I believe $\gcd(a,b)$ must be a power of 2 itself for there to exist solutions.

In summary, I'm really asking four questions.

(Assuming that it is one), what class of Diophantine equations is this?

When does there exist a solution?

How many solutions can exist?

Given they exist, what are the methods used to find their solutions?

Any insight or links to relevant resources would be greatly appreciated.

Graviton
  • 4,462
  • I doubt that there is an infinite family of Fermat numbers known to be composite since the smallest possible prime factor gets ever bigger. I am not even sure whether it is known whether infinite many Fermat numbers are composite although it would be more then crazy if this would not be the case and we would have only primes from some point on. – Peter Aug 26 '22 at 06:26
  • 1
    @Peter Indeed it is unknown if there are infinitely many composite Fermat numbers, such is why I am trying to come up with a construction (for fun, of course, as I doubt I'll make any significant progress). – Graviton Aug 26 '22 at 06:28
  • 1
    Interesting. This is the same situation as with the Mersenne numbers $2^p-1$ with prime $p$. Whether infinite many composites of this form exist is also unknown. – Peter Aug 26 '22 at 06:30
  • 2
    $ak+b=2^n$ means $2^n\equiv b\mod a$. WLOG we can assume that $a,b$ are both odd since we can factor out the power of $2$ dividing both $a$ and $b$ and it is impossible that exactly one of $a$ and $b$ is even (assuming $a,b,k$ are positive integers). This is a discrete logarithm problem which is conjectured to be hard. – Peter Aug 26 '22 at 06:42
  • @Peter Ah thank you! It being hard is still useful to know. – Graviton Aug 26 '22 at 06:51
  • 1
    I just noticed that the case $a$ odd and $b$ even is possible, so we can only assume WLOG that $a$ is odd. But the rest of the comment holds. – Peter Aug 26 '22 at 06:58
  • You can assume $a$ is odd; if $a$ is even then $b$ must also be even, and then it suffices to solve the problem for $\tfrac a2$ and $\tfrac b2$. The problem is equivalent to finding all positive integers $n$ such that $2^n\equiv b\pmod{a}$, as then $k=\frac{2^n-b}{a}$. Then it suffices to find the smallest positive integers $n_1$ and $n_2$ such that $2^{n_1}\equiv b\pmod{a}$ and $2^{n_2}\equiv1\pmod{a}$. Such an $n_1$ may or may not exist, depending on $b$, but such an $n_2$ exists because $a$ is odd. The solutions are then the positive integers $n$ of the form $n=n_1+mn_2$, with integral $m$. – Servaes Aug 27 '22 at 20:19

1 Answers1

0

If you're give $\ a$, $b$, and $\ n\ $, then there's no solution unless $\ 2^n\equiv b\pmod{a}\ $, in which case the unique value of $\ k\ $ satisfying the equation $$ ak+b=2^n\ , $$ is given by $$ k=\frac{2^n-b}{a}\ . $$ This is guaranteed to be an integer whenever $\ 2^n\equiv b\pmod{a}\ $. As Peter notes in the comments, finding values of $\ n\ $ which satisfy this equation is an instance of the discrete logarithm problem. Efficient methods of solving it are known when $\ a\ $ has only relatively small prime divisors, but not if it has at least one sufficiently large prime divisor.

lonza leggiera
  • 28,646
  • 2
  • 12
  • 33
  • 1
    the question as I understand does not limit $k$ – YOu will not know Aug 26 '22 at 09:25
  • 1
    It wasn't clear to me whether $\ n\ $ was supposed have been given or was to be determined, although I did suspect the latter. Unfortunately, I inadvertently saved my partial answer before I had completed it. – lonza leggiera Aug 26 '22 at 09:34
  • Thanks for the response! However, perhaps I should have been more clear in my question. $n$ is not given. That is to say, I do not necessarily care which power of 2 $ak+b$ equals, just that it equals some (integer) power of 2. – Graviton Aug 26 '22 at 09:57