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"
(No difference)

Revision as of 09:08, 17 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

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