Difference between revisions of "Divisibility rules/Rule 1 for 13 proof"
m |
m |
||
| Line 2: | Line 2: | ||
== Proof == | == Proof == | ||
| + | ''An understanding of [[Introduction to modular arithmetic | basic modular arithmetic]] is necessary for this proof.'' | ||
| + | |||
Let <math>N = d_0\cdot10^0 + d_1\cdot 10^1 +d_2\cdot 10^2 + \cdots</math> be a positive integer with units digit <math>d_0</math>, tens digit <math>d_1</math> and so on. Then <math>k=d_110^0+d_210^1+d_310^2+\cdots</math> is the result of truncating the last digit from <math>N</math>. Note that <math>N = 10k + d_0 \equiv d_0 - 3k \pmod {13}</math>. Now <math>N \equiv 0 \pmod {13}</math> if and only if <math>4N \equiv 0 \pmod {13}</math>, so <math>n \equiv 0 \pmod{13}</math> if and only if <math>4d_0 - 12k \equiv 0 \pmod{13}</math>. But <math>-12k \equiv k \pmod{13}</math>, and the result follows. | Let <math>N = d_0\cdot10^0 + d_1\cdot 10^1 +d_2\cdot 10^2 + \cdots</math> be a positive integer with units digit <math>d_0</math>, tens digit <math>d_1</math> and so on. Then <math>k=d_110^0+d_210^1+d_310^2+\cdots</math> is the result of truncating the last digit from <math>N</math>. Note that <math>N = 10k + d_0 \equiv d_0 - 3k \pmod {13}</math>. Now <math>N \equiv 0 \pmod {13}</math> if and only if <math>4N \equiv 0 \pmod {13}</math>, so <math>n \equiv 0 \pmod{13}</math> if and only if <math>4d_0 - 12k \equiv 0 \pmod{13}</math>. But <math>-12k \equiv k \pmod{13}</math>, and the result follows. | ||
== See also == | == See also == | ||
[[Divisibility rules | Back to divisibility rules]] | [[Divisibility rules | Back to divisibility rules]] | ||
Revision as of 11:42, 17 June 2008
To test if a number 
is divisible by 13, then take off the last digit, multiply it by 4 and add it to the rest of the number. If this new number is divisible by 13, then so is 
. This process can be repeated for large numbers, as with the second divisibility rule for 7.
Proof
An understanding of basic modular arithmetic is necessary for this proof.
Let 
be a positive integer with units digit 
, tens digit 
and so on. Then 
is the result of truncating the last digit from . Note that 
. Now 
if and only if 
, so 
if and only if 
. But 
, and the result follows.
