View source for Divisibility rules/Rule for 2 and powers of 2 proof

A number <math>N</math> is divisible by <math>2^n</math> if the last <math>{n}</math> digits of the number are divisible by <math>2^n</math>.

== Proof ==
=== Basic Idea ===
Let the number <math>N</math> be <math>(10^n)k + p</math> where k and p are integers and <math>p<(10^n)</math>. Since <math>\frac{10^n}{2^n}</math> is <math>5^n</math>, <math>(10^n)</math> is a multiple of <math>2^n</math>, meaning <math>(10^n)k</math> is also a multiple of <math>2^n</math>. As long as p is a multiple of <math>2^n</math>, then <math>N</math> is a multiple of <math>2^n</math>. Since <math>(10^n)k</math> has <math>n</math> trailing 0's, <math>p</math> is the last <math>n</math> digits of the number <math>n</math>.

=== Concise ===
''An understanding of [[Introduction to modular arithmetic | basic modular arithmetic]] is necessary for this proof.''

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

<center><math> N = 10^k a_k + 10^{k-1} a_{k-1} + \cdots + 10 a_1 + a_0. </math></center>

Taking this <math>\mod 2^n</math> we have 

{| class="wikitable" style="margin: 1em auto 1em auto"
| <math>N</math> || <math>= 10^k a_k + 10^{k-1} a_{k-1} + \cdots + 10 a_1 + a_0 </math>
|-
| || <math>\equiv 10^{n-1} a_{n-1} + 10^{n-2} a_{n-2} + \cdots + 10 a_1 + a_0 \pmod{2^n}</math>
|}

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

<center><math>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}</math></center>

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

== See also ==
* [[Divisibility rules | Back to divisibility rules]]
[[Category:Divisibility Rules]]