Show that ## 2^{n} ## divides an integer ## N ##.

[Math100]

Homework Statement

Show that $2^{n}$ divides an integer $N$ if and only if $2^{n}$ divides the number made up of the last $n$ digits of $N$.
[Hint: $10^{k}=2^{k} 5^{k}\equiv 0\pmod {2^{n}}$ for $k\geq n$.]

Relevant Equations

None.

Proof:

Suppose $2^{n}$ divides an integer $N$.
Let $N=a_{m}10^{m}+a_{m-1}10^{m-1}+\dotsb +a_{1}10+a_{0}$ for $0\leq a_{k}\leq 9$.
Then $2^{n}\mid N\implies 2^{n}\mid (a_{m}10^{m}+a_{m-1}10^{m-1}+\dotsb +a_{1}10+a_{0})$.
Note that $10^{k}=2^{k} 5^{k}\equiv 0\pmod {2^{n}}$ for $k\geq n$.
This means $2^{n}\mid 10^{n}\implies 2^{n}\mid (2^{n} 5^{n})$.
Thus
\begin{align*}
&2^{n}\mid [10^{n}(a_{n+i}10^{i}+\dotsb +a_{n}]\\
&2^{n}\mid (a_{n+i}10^{n+i}+\dotsb +a_{n}10^{n})\\
&2^{n}\mid (a_{n-1}10^{n-1}+\dotsb +a_{0}).\\
\end{align*}
Conversely, suppose $2^{n}$ divides the number made up of the last $n$ digits of $N$.
Then $2^{n}\mid (a_{n-1}10^{n-1}+\dotsb +a_{0})$.
This means $a_{n+i}10^{n+i}+\dotsb +a_{n}10^{n}=10^{n}(a_{n+j}10^{j}+\dotsb +a_{n})=2^{n} 5^{n}(a_{n+j}10^{j}+\dotsb +a_{n})$.
Thus
\begin{align*}
&2^{n}\mid (a_{n+i}10^{n+i}+\dotsb +a_{n}10^{n})\\
&2^{n}\mid (a_{n+i}10^{n+i}+\dotsb +a_{n-1}10^{n-1}+\dotsb +a_{n}10^{n})\\
&2^{n}\mid N.\\
\end{align*}
Therefore, $2^{n}$ divides an integer $N$ if and only if $2^{n}$ divides the number made up of the last $n$ digits of $N$.

 

[fresh_42]

How do we know that $N$ has $n$ digits? $2^3\,|\,16$ but $16$ has only $2$ digits. How can your criteria be an equivalence?

Let us assume $N$ has $m$ digits and $n\leq m.$

Thus
\begin{align*}
&2^{n}\mid [10^{n}(a_{n+i}10^{i}+\dotsb +a_{n}]\\
&2^{n}\mid (a_{n+i}10^{n+i}+\dotsb +a_{n}10^{n})\\
&2^{n}\mid (a_{n-1}10^{n-1}+\dotsb +a_{0}).\\
\end{align*}

Here, I got lost. What is i? You have to define the variables that you use. You also made a counting error.

We have $m\geq n$ and also $2^m\geq 2^n.$ Now $N= (a_{m}10^{m}+a_{m-1}10^{m-1}+\dotsb +a_{n+1}10^{n+1}+a_n 10^n)+(a_{n-1}10^{n-1}+a_{n-2}10^{n-2}+\dotsb +a_{1}10+a_{0}).$ From $2^{m}\geq 2^n$ we get $2^n\,|\,10^n,10^{n+1},10^{n+2},\ldots,10^m$ so $N\equiv (a_{n}10^{n}+a_{n-1}10^{n-1}+\dotsb +a_{1}10+a_{0}) \pmod{2^n}.$

This is already what we have to show.

Remark:
If $2^n\,|\,N$ then $0\equiv N\equiv (a_{n}10^{n}+a_{n-1}10^{n-1}+\dotsb +a_{1}10+a_{0}) \pmod{2^n}.$

If $2^n\,|\, (a_{n}10^{n}+a_{n-1}10^{n-1}+\dotsb +a_{1}10+a_{0}) \pmod{2^n}$ then $N\equiv (a_{n}10^{n}+a_{n-1}10^{n-1}+\dotsb +a_{1}10+a_{0}) \equiv 0 \pmod{2^n}.$

The zero is on the left in one direction and on the right in the other direction.

Conversely, suppose $2^{n}$ divides the number made up of the last $n$ digits of $N$.
Then $2^{n}\mid (a_{n-1}10^{n-1}+\dotsb +a_{0})$.
This means $a_{n+i}10^{n+i}+\dotsb +a_{n}10^{n}=10^{n}(a_{n+j}10^{j}+\dotsb +a_{n})=2^{n} 5^{n}(a_{n+j}10^{j}+\dotsb +a_{n})$.
Thus
\begin{align*}
&2^{n}\mid (a_{n+i}10^{n+i}+\dotsb +a_{n}10^{n})\\
&2^{n}\mid (a_{n+i}10^{n+i}+\dotsb +a_{n-1}10^{n-1}+\dotsb +a_{n}10^{n})\\
&2^{n}\mid N.\\
\end{align*}
Therefore, $2^{n}$ divides an integer $N$ if and only if $2^{n}$ divides the number made up of the last $n$ digits of $N$.

 

[Math100]

How do we know that $N$ has $n$ digits? $2^3\,|\,16$ but $16$ has only $2$ digits. How can your criteria be an equivalence?

Let us assume $N$ has $m$ digits and $n\leq m.$Here, I got lost. What is i? You have to define the variables that you use. You also made a counting error.

We have $m\geq n$ and also $2^m\geq 2^n.$ Now $N= (a_{m}10^{m}+a_{m-1}10^{m-1}+\dotsb +a_{n+1}10^{n+1}+a_n 10^n)+(a_{n-1}10^{n-1}+a_{n-2}10^{n-2}+\dotsb +a_{1}10+a_{0}).$ From $2^{m}\geq 2^n$ we get $2^n\,|\,10^n,10^{n+1},10^{n+2},\ldots,10^m$ so $N\equiv (a_{n}10^{n}+a_{n-1}10^{n-1}+\dotsb +a_{1}10+a_{0}) \pmod{2^n}.$

This is already what we have to show.

Remark:
If $2^n\,|\,N$ then $0\equiv N\equiv (a_{n}10^{n}+a_{n-1}10^{n-1}+\dotsb +a_{1}10+a_{0}) \pmod{2^n}.$

If $2^n\,|\, (a_{n}10^{n}+a_{n-1}10^{n-1}+\dotsb +a_{1}10+a_{0}) \pmod{2^n}$ then $N\equiv (a_{n}10^{n}+a_{n-1}10^{n-1}+\dotsb +a_{1}10+a_{0}) \equiv 0 \pmod{2^n}.$

The zero is on the left in one direction and on the right in the other direction.

I forgot to quantify the variable $i$.

 

[fresh_42]

I forgot to quantify the variable $i$.

I assume $m=n+i$ and $j=i.$ It was already late over here and I'm a bit tired. Guess I have been a bit harsher than necessary, sorry. Your proof looks ok except for the counting error. The last $n$ digits are $a_{n-1},a_{n-2},\ldots,a_1,a_0.$

 

[Mark44]

@Math100, here are some ideas to think about.
If n = 1, $2^n = 2^1 = 2$ has to divide only the last digit, call it $d_0$. That's trivial, since if 2 divides the last digit, the number N is even.
If n = 2, $2^n = 2^2 = 4$ has to divide the last two digits, $d_1d_0$. This means that $d^2$, if there is such a digit in N, is in the hundreds' place. 4 divides $d_2 \times 100$, so if 4 also divides $d_1d_0$, 4 also divides N.
And so on, which I leave to you. Each larger value of n corresponds to a higher power of 10, which has another factor of 2. A proof by induction might be appropriate here.

Keep in mind that this is an "if and only if" type of proof, so you have to also prove the converse. I.e., you need to prove that if $2^n$ divides the last n digits of N, then $2^n$ divides N, and if $2^n$ divides N, then $2^n$ divides the last n digits of N.

 

[Math100]

How do we know that $N$ has $n$ digits? $2^3\,|\,16$ but $16$ has only $2$ digits. How can your criteria be an equivalence?

Let us assume $N$ has $m$ digits and $n\leq m.$Here, I got lost. What is i? You have to define the variables that you use. You also made a counting error.

We have $m\geq n$ and also $2^m\geq 2^n.$ Now $N= (a_{m}10^{m}+a_{m-1}10^{m-1}+\dotsb +a_{n+1}10^{n+1}+a_n 10^n)+(a_{n-1}10^{n-1}+a_{n-2}10^{n-2}+\dotsb +a_{1}10+a_{0}).$ From $2^{m}\geq 2^n$ we get $2^n\,|\,10^n,10^{n+1},10^{n+2},\ldots,10^m$ so $N\equiv (a_{n}10^{n}+a_{n-1}10^{n-1}+\dotsb +a_{1}10+a_{0}) \pmod{2^n}.$

This is already what we have to show.

Remark:
If $2^n\,|\,N$ then $0\equiv N\equiv (a_{n}10^{n}+a_{n-1}10^{n-1}+\dotsb +a_{1}10+a_{0}) \pmod{2^n}.$

If $2^n\,|\, (a_{n}10^{n}+a_{n-1}10^{n-1}+\dotsb +a_{1}10+a_{0}) \pmod{2^n}$ then $N\equiv (a_{n}10^{n}+a_{n-1}10^{n-1}+\dotsb +a_{1}10+a_{0}) \equiv 0 \pmod{2^n}.$

The zero is on the left in one direction and on the right in the other direction.

But for the second part of the proof which starts with 'Conversely...', how should I prove this? Starting out with $2^{n}\mid (a_{n}10^{n}+a_{n-1}10^{n-1}+\dotsb +a_{1}10+a_{0})\pmod {2^{n}}$. At first, I thought that using the hint would be easier but you said that there are counting errors.

 

[fresh_42]

But for the second part of the proof which starts with 'Conversely...', how should I prove this? Starting out with $2^{n}\mid (a_{n}10^{n}+a_{n-1}10^{n-1}+\dotsb +a_{1}10+a_{0})\pmod {2^{n}}$. At first, I thought that using the hint would be easier but you said that there are counting errors.

Your error is that you wrote $a_n$ but it should be $a_{n-1}$.
$$|\{a_0,a_1,a_2,\ldots,a_{n-2},a_{n-1},a_n\}|=n+1\quad \; , \;\quad |\{a_0,a_1,a_2,\ldots,a_{n-2},a_{n-1}\}|=n$$
$n$ digits means to stop at $n-1$ since we started counting at $0.$