Difference between revisions of "Divisibility rules/Rule for 2 and powers of 2 proof"

Revision as of 23:21, 16 August 2006

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

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

Let $N = a_ka_{k-1}\cdots a_1a_0$ be the base-ten expression for $N$ , where the $a_i$ are digits.

Thus

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

Taking $N$ mod $2^n$ gives

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

Thus, if the last $n$ digits of $N$ are divisible by $2^n$ then $N$ is divisible by $2^n$ .

@@ Line 13: / Line 13: @@
 | <math>N</math> || <math>= 10^k a_k + 10^{k-1} a_{k-1} + \cdots + 10 a_1 + a_0</math>
 |-
-| || <math>\displaystyle \equiv 10^{n-1} a_{n-1} + 10^{n-2} a_{n-2} + \cdots + a_1 + a_0 \mod 2^n </math>
+| || <math>\displaystyle \equiv 10^{n-1} a_{n-1} + 10^{n-2} a_{n-2} + \cdots + a_1 + a_0 </math>
 |-
-| || <math>= a_{n-1}a_{n-2}\cdots a_1a_0</math>
+| || <math>\equiv a_{n-1}a_{n-2}\cdots a_1a_0 \pmod{2^n} </math>
 |}
+Thus, if the last <math>n</math> digits of <math>N</math> are divisible by <math>2^n</math> then <math>N</math> is divisible by <math>2^n</math>.
+== See also ==
+* [[Divisibility rules | Back to divisibility rules]]
 == See also ==
 * [[Divisibility rules | Back to divisibility rules]]