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?


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

  • $\begingroup$ But how is $n \equiv 2^{k} \pmod{2^{k+1}}$? How do I derve that? $\endgroup$ – Polygamma Feb 4 '15 at 18:04
  • $\begingroup$ @Polygamma I gave a proof by induction to that question. Expanding on the intuition behind this. $\endgroup$ – AlexR Feb 4 '15 at 18:06
  • $\begingroup$ @Polygamma $\,\ 2^k (1+ 2\Bbb Z)\, =\, 2^k + 2^{k+1} \Bbb Z\ \ $ $\endgroup$ – Bill Dubuque Feb 4 '15 at 18:08
  • $\begingroup$ 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? $\endgroup$ – 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}}$.

  • $\begingroup$ 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 $\endgroup$ – Polygamma Feb 4 '15 at 18:04
  • 1
    $\begingroup$ 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}}$. $\endgroup$ – 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$


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

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}$
  • $\begingroup$ hi! I didnt notice this answer, until your comment. What is the theorem/definition behind $n = 2^{k} m$? $\endgroup$ – Polygamma Feb 4 '15 at 18:07
  • $\begingroup$ @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}}$$ $\endgroup$ – AlexR Feb 4 '15 at 18:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.