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$

Question

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.

Answer 1

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$.

Answer 2

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.

Answer 3

$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$

So your observation is true.

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

Answer 4

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.)

Answer 5

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$.)

Answer 6

$$ \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}$.