# How does this conclusion work (number theory)

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?

## 4 Answers

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

• But how is $n \equiv 2^{k} \pmod{2^{k+1}}$? How do I derve that? – Polygamma Feb 4 '15 at 18:04
• @Polygamma I gave a proof by induction to that question. Expanding on the intuition behind this. – AlexR Feb 4 '15 at 18:06
• @Polygamma $\,\ 2^k (1+ 2\Bbb Z)\, =\, 2^k + 2^{k+1} \Bbb Z\ \$ – Bill Dubuque Feb 4 '15 at 18:08
• I love the use of color and overbraces, but would you perhaps mind changing the colors to red/blue for the sake of the colorblind? – Emily Feb 4 '15 at 18:25

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

• AndreNicolas, how does $2^k + r2^{k+1}$ make it so that $2^k + t2^{k+1} \equiv 2^k \pmod{2^{k+1}}$. See: $(2^k + t2^{k+1})/(2^{k+1}) = 2^{-1} + t$ where is the remainder? Thanks – Polygamma Feb 4 '15 at 18:04
• Recall that $a\equiv b\pmod{m}$ if $m$ divides $a-b$. Let $a=n=2^k+t2^{k+1}$ and $b=2^k$. Then $a-b=t2^{k+1}$. So $2^{k+1}$ divides $a-b$, and therefore $n=a\equiv 2^k\pmod{2^{k+1}}$. – André Nicolas Feb 4 '15 at 18:22

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$

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}$
• hi! I didnt notice this answer, until your comment. What is the theorem/definition behind $n = 2^{k} m$? – Polygamma Feb 4 '15 at 18:07
• @Polygamma The uniqueness of prime factorisation: Every natural number $n$ can be uniquely represented as the product of primes: $$n = \prod_{k=1}^\infty p_k^{\alpha_k}$$ Now since the product of odd numbers is odd and $2$ is the only even prime ($p_1 = 2$, since it's the first prime): $$n = 2^{\alpha_1} \cdot \underbrace{\prod_{k=2}^\infty p_k^{\alpha_k}}_{\text{product of odd numbers}}$$ – AlexR Feb 4 '15 at 18:10