If $n$ is an odd integer prove that $n - 2^k$ is divisible by $3$ So let $n$ be a odd integer. Show that $n - 2^k$ is divisible by $3$ if $k$ is SOME SPECIFIC positive integer. $k \ge 0$.  So there only has to exist one. For example:
$$7 - 2^2 = 3$$ is divisible by $3$
The approach is modular arithemetic, but it is hard since,
$$2 \equiv 2 \pmod{3}$$
$$n \equiv p \pmod{3}$$
It is hard to combine these? What should I do? 
 A: Hint $\ {\rm mod}\ 3\!:\ 2^2\equiv 1\,$ so $\,2^k\equiv 2^0\equiv 1$ or $\,2^k\equiv 2^1 \equiv 2$. Thus $\,n\equiv 2^k\iff 3\nmid n$
A: There are none if $n$ is a multiple of $3$. There are infinitely many otherwise, or a finite amount if you further require $n - 2^k$ to be positive.
If $n = 6m + 1$, then $k = 2$ will do; then $n - 2^k = 6m + 1 - 4 = 6m - 3$.
If $n = 6m + 5$, then $k = 1$ works; then $n - 2^k = 6m + 5 - 2 = 6m + 3$.
A: If $n$ is an odd integer not divisible by $3$, then $n $ is $1$ or $2$ mod $3$ and thus $n-2^2$ or $n-2^1$ is $0$ modulo $3$. 
On the other hand if $n$ is divisible by $3$ then $n-2^k$ is not divisible by $3$ for every $k$ since otherwise $n-(n-2^k) = 2^k$ would also be divisible by $3$, which is absurd. 
(Actually, the "odd" in the first part is irrelevant.)
A: The way to combine congruences is by simple arithmetic: if the modulus is the same, you can add, subtract and multiply congruences all day long. For the powers of $2$ we have $2^k \equiv 2 \bmod 3$ if $k$ is odd and $2^k \equiv 1 \bmod 3$ if $k$ is even. Then, there are three possibilities for $n$:


*

*If $n \equiv 0 \bmod 3$, for no $k$ can $3 \mid (n - 2^k)$ hold true.

*If $n \equiv 1 \bmod 3$, for any even $k$ we'll have $3 \mid (n - 2^k)$.

*If $n \equiv 2 \bmod 3$, for any odd $k$ we'll have $3 \mid (n - 2^k)$.


In your example with $7$, you can also use $2^4$ (which gives $7 - 16 = -9$), $2^6$ (gives $-57$), $2^8$ (gives $-249$), etc.
A: Let $[n]_3$ be the equivalence class of $n$ modulo 3. Then
$[n-2^k]_3 = [n]_3 - [(-1)^k]_3$. Since $[(-1)^k]_3$ is either $[1]_3$ or $[2]_3$, we see that if $[n]_k = [0]_3$ then $[n-2^k]_3 \neq [0]_3$ for all $k$.
If $[n]_3 = [1]_3$, then pick $k=0$, otherwise pick $k=1$.
A: So if $n$ is an odd integer, you have to prove that there exists some integer exponent $k$ such that $3|(n - 2^k)$? Trouble is, it depends on what $n$ is. There are either infinitely many solutions or none at all.
Let's look at this modulo 6: there are three possibilities: $n \equiv 1, 3 \textrm{ or } 5 \pmod 6$. For the powers of 2, we have $2^k \equiv 2 \textrm{ or } 4 \pmod 6$ for $k > 0$. We want $n - 2^k \equiv 0 \textrm{ or } 3 \pmod 6$.
But how to combine all these? It's actually quite easy: we just subtract! Just be sure to mind the wrap-around.
For example, if $n \equiv 1 \pmod 6$ and $2^k \equiv 4 \pmod 6$, then $n - 2^k \equiv 1 - 4 \equiv 3 \pmod 6$.
But what if $n \equiv 3 \pmod 6$? No $k$ can work: if $2^k \equiv 2 \pmod 6$, then $n - 2^k \equiv 3 - 2 \equiv 1 \pmod 6$, and if $2^k \equiv 4 \pmod 6$, then $n - 2^k \equiv 3 - 4 \equiv 5 \pmod 6$. Don't forget $k = 0$, but that's of no help here: $n - 1 \equiv 3 - 1 \equiv 2 \pmod 6$.
The solution for $n \equiv 5 \pmod 6$ should be easy enough for you to figure out now.
One of the other answerers mentioned a requirement for $n - 2^k$ to be positive, but you didn't. I don't know the rules of the contest, so I assume negative values are perfectly acceptable. For example, $-9 \equiv 3 \pmod 6$ since $(-2) \times 6 + 3 = -12 + 3 = -9$.
