Assume the contrary, and suppose $a$ is such that $2^a-m$ has the maximal number of prime divisors, say $p_1,\ldots,p_u$ (we can take $m$ odd without loss of generality, and then all $p_i$ will be odd and also coprime to $m$). Find $N$ large enough that $p_i^N\not|\ 2^a-m,\ \forall i\in\overline{1,u}$, and $b$ such that $p_i^N|2^b-1,\ \forall i\in\overline{1,u}$. For all $k\ge 1,\ 2^{a+kb}-m$ must be a number of the form $p_1^{\alpha_1}\cdot\ldots\cdot p_u^{\alpha_u}$. If $k$ is large enough, some $\alpha_i$ will become greater than $N$, but then, since $2^{kb}\equiv 1\pmod{p_i^N}$, we'll have to have $2^a\equiv m\pmod{p_i^N}$, contradicting the choice of $N$.

Thank you very much.

It's trivialised by Kobayashi's theorem

Another solution: Let $m$ be fixed. Clearly, we can assume without loss of generality $m$ to be odd, by letting $m=2^{v}m'$ with $2\nmid m'$, and studying $2^k-m = 2^v (2^{k-v}-m')$. I'll inductively construct a sequence $(k_n)_{n=1}^\infty$ of integers, such that $2^{k_n}-m$ has at least $n$ distinct prime divisors. Let $k_1$ be arbitrary, set $s_1 = 2^{k_1}-m$, which is odd; and suppose $s_i=2^{k_i}-m$ for all $i$. Now, observe that, if we select $k_2\equiv k_1\pmod{\varphi(s_1^2)}$ (where $\varphi(\cdot)$ is Euler's totient function) , then $2^{k_2}-m\equiv 2^{k_1}-m=s_1\pmod{s_1^2}$. Thus, $s_2=2^{k_2}-1$ is of form, $\ell_2 s_1^2 + s_1 = s_1(\ell s_1+1)$, for some $\ell\in\mathbb{Z}^+$. Since $\ell s_1+1$ is coprime to $s_1$, it has an additional prime divisor, not dividing $s_1$. Continuing in this manner, we eventually take $k_n\equiv k_{n-1}\pmod{\varphi(s_{n-1}^2)}$ where $s_{n-1}=2^{k_{n-1}}-m$; and conclude.

Try it for 1hr - So Bashy Solution - We will proceed by Induction on $m$ by fixing a $n$ - Base cases are trivial, Suppose $2^k$ - $n$ = $x$ has $m$ different prime divisors , let $\kappa$ = $ { p_1 , p_2 , p_3 , .....p_m } $ denotes the set of all prime divisors of $x$ . We will construct a $l$, such that $2^l$ - $n$ has $m+1$ prime divisors belonging to the set $\kappa$ $\cup$ ${q}$, where $q$ is a prime which have $2$ as its primitive root and $q \not\in$ $\kappa$ . Construction - This has solution by CRT - $$\begin{cases} l \equiv k ( mod p_1 -1)\\ l \equiv k ( mod p_2 - 1)\\ . \\ . \\ . \\ . \\ . \\ . \\ l \equiv k ( mod p_m -1 ) \\ l \equiv k +x ( mod q - 1)\\ \end{cases} $$ where $x \not\equiv 0 mod ( q - 1)$ . Note - Here you will note that while applying CRT , there is a catch , how can we ensure that the $ gcd ' s$ of all the numbers in $ mod $ is $1$. The main thing that to take granted is the all the residues are same i.e $k$ , so we can decompose each of $p_i -1 $ into their prime factors and then apply CRT , more formally - we can decompose - $$ l \equiv k ( mod pq) $$into $ l \equiv k ( mod p) $ and $$ l \equiv k ( mod q) $$. So we have successfully created our construction and we are done by Induction. $\blacksquare$ Remarks - - The motivation behind this weird solution is so long , so I will explain the most weird part - I have chosen $q$ as a prime number with $2$ as a primitive root , because while solving I got $ 2^{l-k} \not\equiv 1 (mod q ) $ , so if I choose $q$ has a prime number having $2$ as it's primitive root , then we can get rid of powers and get this equivalent to $ l - k \not\equiv 0 ( mod q-1) $.

shobber wrote: Prove that for any given positive integer $m$ and $n$, there is always a positive integer $k$ so that $2^k-m$ has at least $n$ different prime divisors.

MatBoy-123 wrote: Try it for 1hr - So Bashy Solution - We will proceed by Induction on $m$ by fixing a $n$ - Base cases are trivial, Suppose $2^k$ - $n$ = $x$ has $m$ different prime divisors , let $\kappa$ = $ { p_1 , p_2 , p_3 , .....p_m } $ denotes the set of all prime divisors of $x$ . We will construct a $l$, such that $2^l$ - $n$ has $m+1$ prime divisors belonging to the set $\kappa$ $\cup$ ${q}$, where $q$ is a prime which have $2$ as its primitive root and $q \not\in$ $\kappa$ . Construction - This has solution by CRT - $$\begin{cases} l \equiv k ( mod p_1 -1)\\ l \equiv k ( mod p_2 - 1)\\ . \\ . \\ . \\ . \\ . \\ . \\ l \equiv k ( mod p_m -1 ) \\ l \equiv k +x ( mod q - 1)\\ \end{cases} $$ where $x \not\equiv 0 mod ( q - 1)$ . Note - Here you will note that while applying CRT , there is a catch , how can we ensure that the $ gcd ' s$ of all the numbers in $ mod $ is $1$. The main thing that to take granted is the all the residues are same i.e $k$ , so we can decompose each of $p_i -1 $ into their prime factors and then apply CRT , more formally - we can decompose - $$ l \equiv k ( mod pq) $$into $ l \equiv k ( mod p) $ and $$ l \equiv k ( mod q) $$. So we have successfully created our construction and we are done by Induction. $\blacksquare$ Remarks - - The motivation behind this weird solution is so long , so I will explain the most weird part - I have chosen $q$ as a prime number with $2$ as a primitive root , because while solving I got $ 2^{l-k} \not\equiv 1 (mod q ) $ , so if I choose $q$ has a prime number having $2$ as it's primitive root , then we can get rid of powers and get this equivalent to $ l - k \not\equiv 0 ( mod q-1) $. You can't always pick a q such that 2 is a primitive root because it is not proven that infinitely primes where 2 is a primitive root exist. You can look at Artin's Conjecture for more information.