Difference between revisions of "Divisibility rules/Rule for 2 and powers of 2 proof"
Mathandski (talk | contribs) |
|||
(3 intermediate revisions by 3 users not shown) | |||
Line 2: | Line 2: | ||
== Proof == | == Proof == | ||
− | '''An understanding of [[Introduction to modular arithmetic | basic modular arithmetic]] is necessary for this 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.'' | ||
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: | 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: | ||
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 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:
Taking this we have
because for , . Thus, is divisible by if and only if
is. But this says exactly what we claimed: the last digits of are divisible by if and only if is divisible by .