Conditions for the existence of solutions to a peculiar Diophantine equation

Question

If $a$ and $b$ are even natural numbers, how can I determine when the equation $$a+kb =2^n$$ has at least one solution where $k$ and $n$ are natural numbers? It's necessary for $a$ and $b$ to not have any common prime factors other than $2$. Is that sufficient as well? Any direction pointing would be much appreciated!

Answer 1

Consider the case of $a=2,b=4.$ Here $a$ and $b$ are even and not divisible by primes other than $2.$ However:

$2+k \cdot 4$ is $2$ mod $4.$ If we require as you do that $k \ge 1$ then note there are no powers of $2$ which are greater than $2$ but are $2$ mod $4.$

Answer 2

Note $a$ and $b$ just not having any common prime factors other than $2$ is insufficient. For example, $a = 6$ and $b = 14$ gives

$$6 + 14k = 2^n \iff 3 + 7k = 2^{n-1} \tag{1}\label{eq1A}$$

However, $2^n$ modulo $7$ (i.e., when divided by $7$) has only values $1$, $2$ or $4$, so there's no integral solution to \eqref{eq1A}.

There are $2$ main things to check to determine if there's at least one solution for a particular $a$ and $b$. The first is with the number of factors of $2$ of $a$ (call this $i$) and of $b$ (call this $j$). If $i \lt j$, then normally there's no solution since dividing both sides by $2^{i}$ leaves an odd number, with this only being $1$ if $0$ is included in your definition of natural numbers (plus you assign it to $k$) and there's no odd prime factors in $a$, so there's then a solution of $k = 0$ and $n = i$. Otherwise, there's no solution (a basic example of this is given in coffeemath's answer).

With $i \ge j$ instead, the next check starts with dividing both sides by $2^{j}$ to get

$$a_1 = \frac{a}{2^{j}}, \; b_1 = \frac{b}{2^{j}} \tag{2}\label{eq2A}$$

Since $b_1$ is odd, Euler's theorem states $2^{\varphi(b_1)} \equiv 1 \pmod{b_1}$, where $\varphi$ is Euler's totient function. As $2^{0} \equiv 2^{\varphi(b_1)} \equiv 1 \pmod{b_1}$, the remainders repeat for larger powers than $\varphi(b_1)$. Thus, we need only to check the powers of $2$ up to $\varphi(b_1)$ to determine which one, if any, is congruent to $a_1$ modulo $b_1$. If there are none, like with my example of $7$ above, then there is no solution. Otherwise, with this power, call it $m$ (so $2^{m} \equiv a_1 \pmod{b_1}$), use

$$n_1 = q(\varphi(b_1)) + m \tag{3}\label{eq3A}$$

where $q$ is a positive integer large enough for $2^{n_1} \gt a_1$. Since $2^{n_1} \equiv \left(2^{\varphi(b_1)}\right)^{q}2^{m} \equiv 2^{m} \equiv a_1 \pmod{b_1}$, this means $2^{n_1} - a_1$ is a positive integer which is a multiple of $b_1$, so

$$k = \frac{2^{n_1} - a_1}{b_1}, \; n = n_1 + j \tag{4}\label{eq4A}$$

is a solution. Note increasing $q$ in \eqref{eq3A} shows there are an actually an infinite number of solutions in this case.

Checking the powers of $2$ up to $\varphi(b_1)$ may not be simple, or even very easy, for very large values of $b_1$, especially cases where it's required to rule out a solution if $a_1$ doesn't match any congruence. However, I offhand don't know of any easy way to simplify or speed up that process, at least not in general.