Divisibility rules/Rule for 2 and powers of 2 proof

From AoPSWiki

A number $N$ is divisible by $2^n$ if the last ${n}$ digits of the number are divisible by $2^n$ .

Proof

An understanding of basic modular arithmetic is necessary for this proof.

Let the base-ten representation of $N$ be $\underline{a_ka_{k-1}\cdots a_1a_0}$ where the $a_i$ are digits for each $i$ and the underline is simply to note that this is a base-10 expression rather than a product. If $N$ has no more than $n$ digits, then the last $n$ digits of $N$ make up $N$ itself, so the test is trivially true. If $N$ has more than $n$ digits, we note that:

$N = 10^k a_k + 10^{k-1} a_{k-1} + \cdots + 10 a_1 + a_0.$

Taking this $\mod 2^n$ we have

$N$	$= 10^k a_k + 10^{k-1} a_{k-1} + \cdots + 10 a_1 + a_0$
	$\equiv 10^{n-1} a_{n-1} + 10^{n-2} a_{n-2} + \cdots + 10 a_1 + a_0 \pmod{2^n}$

because for $i \geq n$ , $10^i \equiv 0 \pmod{2^n}$ . Thus, $N$ is divisible by $2^n$ if and only if

$10^{n-1} a_{n-1} + 10^{n-2} a_{n-2} + \cdots + 10 a_1 + a_0 = \underline{a_{n-1}a_{n-2}\cdots a_1a_0}$

is. But this says exactly what we claimed: the last $n$ digits of $N$ are divisible by $2^n$ if and only if $N$ is divisible by $2^n$ .

Personal tools

Navigation

Search

Toolbox

Divisibility rules/Rule for 2 and powers of 2 proof

From AoPSWiki

Proof

See also