Difference between revisions of "Divisibility rules/Rule for 5 and powers of 5 proof"
m |
|||
(One intermediate revision by the same user not shown) | |||
Line 4: | Line 4: | ||
''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 the [[base numbers | base-ten]] representation of <math>N</math> be <math>a_ka_{k-1}\cdots a_1a_0</math> where the <math>a_i</math> are digits for each <math>i</math>. | + | 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> | <center><math> N = 10^k a_k + 10^{k-1} a_{k-1} + \cdots + 10 a_1 + a_0. </math></center> | ||
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>\equiv 10^{n-1} a_{n-1} + 10^{n-2} a_{n-2} + \cdots + 10 a_1 + a_0 | + | | || <math>\equiv 10^{n-1} a_{n-1} + 10^{n-2} a_{n-2} + \cdots + 10 a_1 + a_0 \pmod{5^n}</math> |
− | |||
− | |||
|} | |} | ||
− | Thus if the last <math>n</math> digits of <math>N</math> are divisible by <math>5^n</math> | + | because for <math>i \geq n</math>, <math>10^i \equiv 0 \pmod{5^n}</math>. Thus, <math>N</math> is divisible by <math>5^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>5^n</math> if and only if <math>N</math> is divisible by <math>5^n</math>. | ||
== See also == | == See also == | ||
* [[Divisibility rules | Back to divisibility rules]] | * [[Divisibility rules | Back to divisibility rules]] |
Latest revision as of 09:58, 17 August 2006
A number is divisible by
if the last
digits are divisible by that power of 5.
Proof
An understanding of basic modular arithmetic is necessary for this proof.
Let the base-ten representation of be
where the
are digits for each
and the underline is simply to note that this is a base-10 expression rather than a product. If
has no more than
digits, then the last
digits of
make up
itself, so the test is trivially true. If
has more than
digits, we note that:
![$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 this we have
![]() |
![]() |
![]() |
because for ,
. Thus,
is divisible by
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}$](http://latex.artofproblemsolving.com/1/2/f/12fc0f5913011d282abb009ef802e2c608b9cfde.png)
is. But this says exactly what we claimed: the last digits of
are divisible by
if and only if
is divisible by
.