How does this conclusion work (number theory)

Question

From An AOPS website on a Putnam Question,

The specific identity Kent Merryfield uses is:

For any $n\in\mathbb N$ we can find a nonnegative integer $k$ such that $n\equiv 2^k \pmod{2^{k+1}}$. This is true when $k$ is the largest integer such that $2^k$ divides $n$.

I dont understanding the reasoning, the intuition behind this, but I also dont understand how to derive (prove) that conclusion he makes?

Can anyone help me?

Also, what branch of number theory is this?

Answer 1

Let $2^k$ be the largest power of $2$ that divides $n$. Then $n\equiv 2^k\pmod{2^{k+1}}$.

Proof: We have $n=2^k q$ where $q=1+2t$ is odd. Thus $n=2^k+t2^{k+1}$, and therefore $n\equiv 2^k\pmod{2^{k+1}}$.

Answer 2

Intuition:
We know that for $n$ odd, $n\equiv 1 \pmod2$. Now if $n=2^k m$ for some odd $m$ we know that $2^k|n$ by construction of $n$ but also $\frac{n}{2^{k+1}} = \frac{2^k m}{2^{k+1}} = \frac m2$ is not an integer, so $n\nmid 2^{k+1}$. To find the precise remainder we note that $n = 2^k(2l + 1) = 2^{k+1}l + 2^k$ for some $l$ such that $m=2l+1$.

Proof:
Since the prime factorisation of $n$ is unique, we can write $n = 2^km$ where $k\in\mathbb N_0, m\text{ odd}$ and $m$ is the product of the odd prime factors of $n$.

We can now prove by induction on $k$ that $n \equiv 2^k \pmod{2^{k+1}}$:

• The base case is $k=0$, i.e. $n=m$ is odd. Then clearly $n\equiv 1 \pmod 2 \checkmark$.
• Now let $n = 2^km \equiv 2^k \pmod{2^{k+1}}$.
  We need to prove that $2n = 2^{k+1}m \equiv 2^{k+1} \pmod{2^{k+2}}$. For this write $m=2l + 1$ with $l\in\mathbb N_0$: $$n = 2^{k+1}(2l+1) = 2^{k+2}l + 2^{k+1} \stackrel{(\ast)}\equiv 2^{k+1} \pmod{2^{k+2}}$$ In $(\ast)$ we used that $a\equiv b\pmod n$ is defined as $a-b | n$. This implies that $a + k\cdot n \equiv a \pmod n$ for any $a$ and $k$. $\begin{array}{cr}\hspace{15cm}&\Box\end{array}$

Answer 3

$ n\equiv 2^k\!\pmod{\!2^{k+1}}\!\!\iff\! 2^{k+1}\!\mid n\!-\!2^k\Rightarrow \color{#0a0}{2^k\mid n},\ \color{#c00}{2^{k+1}\nmid n}\ $ so $\,\overbrace{\color{#0a0}{2^k}\!\cdot\color{#c00}{\rm odd}}^{\large n}= 2^k(1\!+\!2j) = 2^k\! +\! 2^{k+1}j $

Answer 4

Intuition: $n$ is either odd or even. That is, either $n\equiv 0\bmod 2$ or $n\equiv 1\bmod 2$.

• If $n\equiv 1\bmod 2$, then $1$ is the highest power of $2$ dividing $n$.

• If $n\equiv 0\bmod 2$, then modulo $4$, we must either have $n\equiv 0\bmod 4$ or $n\equiv 2\bmod 4$.

  • If $n\equiv 2\bmod 4$, then $2$ is the highest power of $2$ dividing $n$.

  • If $n\equiv 0\bmod 4$, then modulo $8$, we must either have $n\equiv 0\bmod 8$ or $n\equiv 4\bmod 8$.

    • If $n\equiv 4\bmod 8$, then $4$ is the highest power of $2$ dividing $n$.

    • $\vdots$