Difference between revisions of "Divisibility rules/Rule for 2 and powers of 2 proof"
(Added category) |
Mathandski (talk | contribs) |
||
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.'' | ||
Revision as of 16:41, 3 May 2020
A number is divisible by
if the last
digits of the number are divisible by
.
Contents
Proof
Basic Idea
Let the number be
where k and p are integers and
. Since
is
,
is a multiple of
, meaning
is also a multiple of
. As long as p is a multiple of
, then
is a multiple of
. Since
has
trailing 0's,
is the last
digits of the number
.
Concise
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
.