Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

(duplicate section)
Line 2: Line 2:
  
 
== Proof ==
 
== Proof ==
−
''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.''
  
−
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.
+
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:
  
−
Thus <center><math> N = 10^k a_k + 10^{k-1} a_{k-1} + \cdots + 10 a_1 + a_0. </math></center>
+
<center><math> N = 10^k a_k + 10^{k-1} a_{k-1} + \cdots + 10 a_1 + a_0. </math></center>
  
−
Taking <math>N</math> mod <math>2^n</math> gives
+
Taking this <math>\mod 2^n</math> we have
  
−
{| class="wikitable" style="margin: 1em auto 1em auto;height:100px"
+
{| 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>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 + 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>
−
|-
 
−
| || <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>.
+
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 ==
 
== See also ==
 
* [[Divisibility rules | Back to divisibility rules]]
 
* [[Divisibility rules | Back to divisibility rules]]

Revision as of 09:41, 26 November 2008

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

See also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Divisibility_rules/Rule_for_2_and_powers_of_2_proof&oldid=28423"