Difference between revisions of "Divisibility rules/Rule for 2 and powers of 2 proof"
(→Proof) |
(duplicate section) |
||
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>N</math> || <math>= 10^k a_k + 10^{k-1} a_{k-1} + \cdots + 10 a_1 + a_0</math> | ||
|- | |- | ||
− | | || <math> | + | | || <math>\equiv 10^{n-1} a_{n-1} + 10^{n-2} a_{n-2} + \cdots + a_1 + a_0 </math> |
|- | |- | ||
| || <math>\equiv a_{n-1}a_{n-2}\cdots a_1a_0 \pmod{2^n} </math> | | || <math>\equiv a_{n-1}a_{n-2}\cdots a_1a_0 \pmod{2^n} </math> | ||
Line 19: | Line 19: | ||
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>. | 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 == | == See also == | ||
* [[Divisibility rules | Back to divisibility rules]] | * [[Divisibility rules | Back to divisibility rules]] |
Revision as of 12:38, 17 June 2008
A number is divisible by
if the last
digits of the number are divisible by
.
Proof
An understanding of basic modular arithmetic is necessary for this proof.
Let be the base-ten expression for
, where the
are digits.
Thus
![$N = 10^k a_k + 10^{k-1} a_{k-1} + \cdots + 10 a_1 + a_0.$](http://latex.artofproblemsolving.com/2/9/8/298c376ff3a0f4ffb08ae3357165f9f92c517586.png)
Taking mod
gives
![]() |
![]() |
![]() | |
![]() |
Thus, if the last digits of
are divisible by
then
is divisible by
.