Difference between revisions of "Divisibility rules/Rule 1 for 13 proof"

 
Line 1: Line 1:
===Proof===
+
To test if a number <math>N</math> is divisible by 13, multiply the last digit by 4 and add it to the rest of the number.  If this new number is divisible by 7, then so is <math>n</math>. This process can be repeated for large numbers, as with the second divisibility rule for 7.
Let <math>n = d_0\cdot10^0 + d_1\cdot 10^1 +d_2\cdot 10^2 + \ldots</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+...</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.
+
 
 +
== 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.
 +
 
 +
== See also ==
 +
[[Divisibility rules | Back to divisibility rules]]

Revision as of 18:41, 16 August 2006

To test if a number $N$ is divisible by 13, multiply the last digit by 4 and add it to the rest of the number. If this new number is divisible by 7, then so is $n$. This process can be repeated for large numbers, as with the second divisibility rule for 7.

Proof

Let $N = d_0\cdot10^0 + d_1\cdot 10^1 +d_2\cdot 10^2 + \cdots$ be a positive integer with units digit $d_0$, tens digit $d_1$ and so on. Then $k=d_110^0+d_210^1+d_310^2+\cdots$ is the result of truncating the last digit from $N$. Note that $N = 10k + d_0 \equiv d_0 - 3k \pmod {13}$. Now $N \equiv 0 \pmod {13}$ if and only if $4N \equiv 0 \pmod {13}$, so $n \equiv 0 \pmod{13}$ if and only if $4d_0 - 12k \equiv 0 \pmod{13}$. But $-12k \equiv k \pmod{13}$, and the result follows.

See also

Back to divisibility rules