- #1

Math100

- 756

- 204

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

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