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

Revision as of 09:44, 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 \mod 2^n$
	$= a_{n-1}a_{n-2}\cdots a_1a_0$

@@ Line 4: / Line 4: @@
 ''An understanding of [[Introduction to modular arithmetic | basic modular arithmetic]] is necessary for this proof.''
-Let <math>N = a_ka_{k-1}\cdots a_1a_0</math> where the <math>a_i</math> are [[base numbers | base-ten]] numbers.
+Let <math>N = a_ka_{k-1}\cdots a_1a_0</math> be the [[base numbers | base-ten]] expression for <math>N</math>, where the <math>a_i</math> are [[digit]]s.
 Thus <center><math> N = 10^k a_k + 10^{k-1} a_{k-1} + \cdots + 10 a_1 + a_0. </math></center>