# For any $k \in \mathbb{N}$, there exist $s \in \mathbb{N}$ such that the expression $9s+3+2^{k}$ is a power of $2$

I have reason(empirical calculations) to think the following statement is true:

For any $$k \in \mathbb{N}$$, there exist $$s \in \mathbb{N}$$ such that the expression

$$9s+3+2^{k}$$

is a power of $$2$$.

To me it seems like a silly statement, but I don't know how I would go about proving it. Any ideas, or references?

THank you.

The statement that $$9s + 3 + 2^k$$ is a power of $$2$$ for some $$s\in\Bbb{N}$$ is equivalent to saying $$2^k + 3 \equiv 2^n \pmod 9$$ for some $$n\gt k$$. Since the values of $$2^k\bmod 9$$ are the periodic sequence $$1,2,4,8,7,5,1,2,4,8,7,5,\ldots$$ consisting of all values which are not multiples of $$3$$, this is true.

For example, take $$k = 5$$. Then $$2^k + 3 = 35 \equiv 8 \pmod 9$$ and the next power of $$2$$ which is congruent to $$8$$ is $$2^9 = 512$$. So in this case $$s = (512 - 35)/9 = 53$$.

• Thank you all for the replies. I will choose this one as the answer as I find it the most concise and illuminating. Different approaches, such as Eric's down below are welcomed. – ReverseFlow Mar 31 at 6:18

$$9\cdot s+3+2^k=2^{j+k} \Rightarrow 2^k(2^j-1)-3 \equiv 0 \mod 9 \Rightarrow 2^k(2^j-1) \equiv 3 \mod 9$$

$$2^k \mod 9$$ cycles through $$2,4,8,7,5,1,$$ etc. so $$2^j-1 \mod 9$$ cycles through $$1,3,7,6,4,0$$ etc.

For any residue of $$2^k$$ it is possible to find a residue of $$2^j-1$$ such that their product equals $$3 \mod 9$$, viz: $$2\cdot 6;\ 4\cdot 3;\ 8\cdot 6;\ 7\cdot 3;\ 5\cdot 6;\ 1\cdot 3$$

NB As I typed this, I see that Fred H has given a similar answer.

Euler's Theorem tells us $$2^6 \equiv 1 \pmod 9$$ and direct calculation shows so

$$2^{6k + i; i=0...5}\equiv 1,2,4,8,7,5 \pmod 9$$.

So $$2^m - 2^k \equiv 3 \pmod 9$$ if

$$k\equiv 0 \pmod 6;2^k\equiv 1\pmod 9$$ and $$m\equiv 2\pmod 6; 2^m\equiv 4\pmod 9$$.

$$k\equiv 1 \pmod 6;2^k\equiv 2\pmod 9$$ and $$m\equiv 5\pmod 6; 2^m\equiv 5\pmod 9$$.

$$k\equiv 2 \pmod 6;2^k\equiv 4\pmod 9$$ and $$m\equiv 4\pmod 6; 2^m\equiv 7\pmod 9$$.

$$k\equiv 3 \pmod 6;2^k\equiv 8\pmod 9$$ and $$m\equiv 1\pmod 6; 2^m\equiv 2\pmod 9$$ (So $$2^m - 2^k \equiv 2-8\equiv -6\equiv 3 \pmod 9$$).

$$k\equiv 4 \pmod 6;2^k\equiv 7\pmod 9$$ and $$m\equiv 0\pmod 6; 2^m\equiv 1\pmod 9$$.

$$k\equiv 5 \pmod 6;2^k\equiv 5\pmod 9$$ and $$m\equiv 3\pmod 6; 2^m\equiv 9\pmod 9$$.

So for any $$k$$ there will exist infinitely many $$m > k$$ (Actually we don't need $$m > k$$ as $$s$$ may be negative but... nice answers are nicer) so that $$2^m - 2^k \equiv 3 \pmod 9$$.

So that means for any $$k$$ there will exist $$s$$ and $$m$$ (actually infinitely many $$s$$ and $$m$$) so that

$$2^m - 2^k = 9s + 3$$ or

$$9s+3 + 2^k$$ a power of $$2$$.

(I take a dog for a walk and three people post a similar to identical answer. sigh. Anyway hopefully this answer may (or may not) provide a possible fresh take... There's always more than one way to do or explain things.)

If $$9s+3 = 3\cdot 2^k$$, this will work.

Then $$3s+1 = 2^k$$, so $$3|2^k-1$$.

This works for even $$k$$.

More generally, it works if $$9s+3 = (2^m-1)2^k$$ for some $$m$$.

To get rid of the 3 requires $$m$$ even, so write this as $$9s+3 = (4^m-1)2^k = 3\sum_{j=0}^{m-1}4^j2^k$$ or $$3s+1 = 2^k\sum_{j=0}^{m-1}4^j$$.

Mod 3, we want $$1 =2^k\sum_{j=0}^{m-1}4^j =2^km$$ so if $$2^km = 1 \bmod 3$$ we are done, and this can always be done.

$$\begin{array}{c} \boldsymbol{\large 2^k+3\equiv2^m\pmod9}\\ \begin{array}{c|c|c} k\bmod6&2^k+3\bmod9&2^k\bmod9&m\bmod6\\\hline 0&4&1&2\\ 1&5&2&5\\ 2&7&4&4\\ 3&2&8&1\\ 4&1&7&0\\ 5&8&5&3 \end{array} \end{array}$$ Since $$\phi(9)=6$$, Euler's Theorem says that $$2^6\equiv1\pmod9$$; therefore, if we know $$k\bmod6$$, we know $$2^k\bmod9$$. Thus, we can compute columns $$2$$ and $$3$$ mod $$9$$ from column $$1$$. To compute column $$4$$ for row $$A$$, read column $$2$$ from row $$A$$, and find that value in column $$3$$ of row $$B$$ and read the value in column $$1$$ from row $$B$$ and put that value in column $$4$$ of row $$A$$. Then, for each row, $$2^k+3\equiv2^m\pmod9$$ For example, $$2^{10}+3\equiv2^{12}\pmod{9}$$ because, from the table, $$k=10\equiv4\pmod6$$ and so $$m=12\equiv0\pmod6$$, so we can compute $$s=\frac{2^{12}-2^{10}-3}9=341$$ to get $$2^{10}+3+9\cdot341=2^{12}$$.

• More words around that table would be incredibly useful. What does k mod 6 tell us, and what do the colors mean? – ReverseFlow Mar 31 at 8:35
• @ReverseFlow: I have replaced the colors with a verbal description. – robjohn Mar 31 at 9:02

Suppose $$k \in \mathbb{N} = \mathbb{Z}_{>0}$$ is given.

Set \begin{align*} s &= 2^k + \frac{1}{3} \left( (-2)^{k+1} - 1 \right) \text{, and} \\ n &= (-1)^{k+1} + k + 3 \text{.} \end{align*}

Then $$s$$ and $$n$$ are positive integers and $$9s + 3 + 2^k = 2^n \text{.}$$

This looks like a job for induction, but we can show it directly.

The expression for $$n$$ is a sum of integers, so $$n$$ is an integer, and the value of the expression lies in $$[k+3-1, k+3+1]$$. Since $$k > 0$$, this entire interval contains only positive numbers, so $$n$$ is a positive integer.

For $$s$$, note that $$(-2)^{k+1} - 1 \cong 1^{k+1} - 1 \cong 1 - 1 \cong 0 \pmod{3}$$, so the division by $$3$$ yields an integer. We wish to ensure $$s > 0$$, so \begin{align*} 2^k + \frac{1}{3} \left( (-2)^{k+1} - 1 \right) \overset{?}{>} 0 \\ 2^k + \frac{1}{3} \left( (-1)^{k+1}2^{k+1} - 1 \right) \overset{?}{>} 0 \\ 1 + \frac{1}{3} \left( (-1)^{k+1}2^{1} - 2^{-k} \right) \overset{?}{>} 0 \end{align*} If $$k$$ is even, \begin{align*} 1 + \frac{1}{3} \left( -2 - 2^{-k} \right) \overset{?}{>} 0 \text{,} \end{align*} $$-2 -2^{-k} \in (-3,-2)$$, so $$1 + \frac{1}{3} \left( -2 - 2^{-k} \right) \in (0,1/3)$$, all elements of which are positive, so $$s$$ is positive when $$k$$ is even. If $$k$$ is odd, \begin{align*} 1 + \frac{1}{3} \left( 2 - 2^{-k} \right) \overset{?}{>} 0 \text{,} \end{align*} $$2 - 2^{-k} \in (1,2)$$, so $$1 + \frac{1}{3} \left( 2 - 2^{-k} \right) \in (4/3, 5/3)$$, all elements of which are positive, so $$s$$ is an integer when $$k$$ is odd. Therefore, $$s$$ is positive when $$k$$ is odd. Therefore, $$s$$ is always a positive integer.

Plugging in the above expressions into the given equation, we have $$9 \left( 2^k + \frac{1}{3} \left( (-2)^{k+1} - 1 \right) \right) + 3 + 2^k = 2^{(-1)^{k+1} + k + 3} \text{.}$$ After a little manipulation, this is $$2^{(-1)^{k+1} + k + 2} = 5 \cdot 2^k - 3(-2)^k \text{.} \tag{1}$$

First suppose $$k$$ is even, so $$k = 2m$$. Substituting this into (1) and simplifying a little, we have $$2^{-1 + 2m + 2} = 2 \cdot 2^{2m} \text{,}$$ a tautology.

Then suppose $$k$$ is odd, so $$k = 2m+1$$. Sustituting this into (1) and simplifying a little, we have $$2^{2m + 4} = 8 \cdot 2^{2m+1} \text{,}$$ a tautology.

Therefore, the given $$s$$ and $$n$$ are positive integers which satisfy the given equation.

Aside: The above choices for $$s$$ and $$n$$ do not exhaust the solution set. For instance $$(k,s,n) = (2, 131\,176\,846\,746\,379\,033\,713, 70)$$ is another solution. (This is implicit in the other answers that use the fact that the powers of $$2$$ are cyclic modulo $$9$$.)

• I get the feeling you are an analyst. :). Thank you for taking the time to write this, though I admit the other solutions are easier to digest. – ReverseFlow Mar 31 at 6:14