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

m (Proof)
 
(2 intermediate revisions by 2 users not shown)
Line 2: Line 2:
  
 
== Proof ==
 
== 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.''
 
''An understanding of [[Introduction to modular arithmetic | basic modular arithmetic]] is necessary for this proof.''
  
Line 24: Line 28:
 
== See also ==
 
== See also ==
 
* [[Divisibility rules | Back to divisibility rules]]
 
* [[Divisibility rules | Back to divisibility rules]]
 +
[[Category:Divisibility Rules]]

Latest revision as of 16:46, 3 May 2020

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

Proof

Basic Idea

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

Concise

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

See also