Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Divisibility rules/Rule 1 for 13 proof"
m
Line 1: Line 1:
−
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.
+
To test if a number <math>N</math> 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 <math>n</math>. This process can be repeated for large numbers, as with the second divisibility rule for 7.
  
 
== Proof ==
 
== Proof ==

Revision as of 23:41, 23 February 2008

To test if a number $N$ 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 $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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Divisibility_rules/Rule_1_for_13_proof&oldid=23575"