logo

The Proof of the Divisibility Test for 7 and 13 📂Number Theory

The Proof of the Divisibility Test for 7 and 13

Buildup

In this post, for convenience in discussing number systems, we use the following notation. [anan−1…a1a0]:=an⋅10n+an−1⋅10n−1+…+a1⋅101+a0⋅100 [a_{n} a_{n-1} … a_{1} a_{0}] := a_{n} \cdot 10^{n} + a_{n-1} \cdot 10^{n-1} +…+ a_{1} \cdot 10^{1} + a_{0} \cdot 10^{0} For example, 57145714 can be represented as follows. [5714]=5000+700+10+4=5⋅103+7⋅102+1⋅101+4⋅100 \begin{align*} [5714] =& 5000+700+10+4 \\ =& 5\cdot 10^{3} +7\cdot 10^{2} +1\cdot 10^{1} +4\cdot 10^{0} \end{align*}

Theorem

anan−1an−2−an−3an−4an−5+…+a5a4a3−a2a1a0 a_{n} a_{n-1} a_{n-2} - a_{n-3} a_{n-4} a_{n-5} +…+ a_{5} a_{4} a_{3} - a_{2} a_{1} a_{0} If it’s a multiple of 77, then [anan−1…a1a0][a_{n} a_{n-1} … a_{1} a_{0}] is also a multiple of 77, anan−1an−2−an−3an−4an−5+…+a5a4a3−a2a1a0 a_{n} a_{n-1} a_{n-2} - a_{n-3} a_{n-4} a_{n-5} +…+ a_{5} a_{4} a_{3} - a_{2} a_{1} a_{0} If it’s a multiple of 1313, then [anan−1…a1a0][a_{n} a_{n-1} … a_{1} a_{0}] is also a multiple of 1313.

Explanation

What this means is, if the number obtained by grouping digits in threes and alternately adding and subtracting them is a multiple of 77, then the original number is also a multiple of 7. Let’s understand this with an example.

For instance, looking at 745444745444, according to the rule, 745−444=7⋅301 745-444=7 \cdot 301 it’s a multiple of 7, and indeed 745444745444 is a multiple of 77 as it is 745444=7⋅106492745444=7 \cdot 106492. Even for a larger number like 1179454511794545, the rule above still applies, −11+794−545=238=7⋅34 -11+794-545 = 238 = 7 \cdot 34 is a multiple of 77, and indeed 1179454511794545 is 11794545=7⋅168493511794545=7 \cdot 1684935 which makes it a multiple of 77.

This theorem holds true for the case of 1313 as well, and actually also for the case of 1111. The reason is because the multiple determination rule for 77, 1111, and 1313 all come from the same proof. Merely changing the numbers results in exactly the same proof, so we will omit the case of 1111 and 1313.

Proof

Strategy: The proof itself uses only very basic techniques, but because it’s inherently lengthy and requires an idea, it’s not easy. A key idea is using the fact that 10011001 and 999999999999 are multiples of 77. 103+1=1000+1=1001=7⋅143(103+1)(103−1)=106−1=1000000−1=999999=7⋅142857 10^{3} +1=1000+1=1001=7\cdot 143 \\ \left( 10^{3} +1 \right) \left( 10^{3} -1 \right) = 10^{6} -1=1000000-1=999999=7\cdot 142857

[anan−1…a1a0]=[anan−1an−2]10n−2+[an−3an−4an−5]10n−5+…+[a5a4a3]103+[a2a1a0]=([anan−1an−2]103+[an−3an−4an−5])10n−5+…+([a5a4a3]103+[a2a1a0]) \begin{align*} & [a_{n} a_{n-1} … a_{1} a_{0}] \\ =& [a_{n} a_{n-1} a_{n-2} ]10^{n-2} +[a_{n-3} a_{n-4} a_{n-5}]10^{n-5} +…+[a_{5} a_{4} a_{3}]10^{3} +[a_{2} a_{1} a_{0}] \\ =& ([a_{n} a_{n-1} a_{n-2}]10^{3} +[a_{n-3} a_{n-4} a_{n-5}]) 10^{n-5} +…+([a_{5} a_{4} a_{3}]10^{3} +[a_{2} a_{1} a_{0}]) \end{align*}

Focusing only on the part inside the parentheses,

([anan−1an−2]103+[an−3an−4an−5])=[anan−1an−2]103+([anan−1an−2]−[anan−1an−2])+[an−3an−4an−5]=([anan−1an−2]103+[anan−1an−2])−([anan−1an−2]−[an−3an−4an−5])=[anan−1an−2]1001−([anan−1an−2]−[an−3an−4an−5])=[anan−1an−2]7⋅143−([anan−1an−2]−[an−3an−4an−5]) \begin{align*} & ([a_{n} a_{n-1} a_{n-2}]10^{3} +[a_{n-3} a_{n-4} a_{n-5}]) \\ &= {[a_{n} a_{n-1} a_{n-2}]10^{3} +([a_{n} a_{n-1} a_{n-2}]-[a_{n} a_{n-1} a_{n-2}])+[a_{n-3} a_{n-4} a_{n-5}]} \\ &= {([a_{n} a_{n-1} a_{n-2}]10^{3} +[a_{n} a_{n-1} a_{n-2}])- ([a_{n} a_{n-1} a_{n-2}]-[a_{n-3} a_{n-4} a_{n-5}])} \\ &= {[a_{n} a_{n-1} a_{n-2}]1001-([a_{n} a_{n-1} a_{n-2}]-[a_{n-3} a_{n-4} a_{n-5}])} \\ &= [a_{n} a_{n-1} a_{n-2}]7\cdot 143-([a_{n} a_{n-1} a_{n-2}]-[a_{n-3} a_{n-4} a_{n-5}]) \end{align*}

Thus, ([anan−1an−2]−[an−3an−4an−5]) ([a_{n} a_{n-1} a_{n-2}]-[a_{n-3} a_{n-4} a_{n-5}]) If it’s a multiple of 77, [anan−1an−2an−3an−4an−5] [a_{n} a_{n-1} a_{n-2} a_{n-3} a_{n-4} a_{n-5}] is also a multiple of 77. Let’s now generalize it.

([anan−1an−2]103+[an−3an−4an−5])10n−5=[anan−1an−2]7⋅143⋅10n−5−([anan−1an−2]−[an−3an−4an−5])10n−5 \begin{align*} & ([a_{n} a_{n-1} a_{n-2}]10^{3} +[a_{n-3} a_{n-4} a_{n-5}]) 10^{n-5} \\ &= [a_{n} a_{n-1} a_{n-2}]7\cdot 143\cdot 10^{n-5} -([a_{n} a_{n-1} a_{n-2}]-[a_{n-3} a_{n-4} a_{n-5}]) 10^{n-5} \end{align*}

If we group terms like [anan−1an−2]7⋅143⋅10n−5[a_{n} a_{n-1} a_{n-2}]7\cdot 143\cdot 10^{n-5} all together as cc,

[anan−1…a1a0]=7c+([anan−1an−2]−[an−3an−4an−5])10n−5+…+([a5a4a3]−[a2a1a0]) \begin{align*} & [a_{n} a_{n-1} … a_{1} a_{0}] \\ =& 7c+([a_{n} a_{n-1} a_{n-2}]-[a_{n-3} a_{n-4} a_{n-5}]) 10^{n-5} +…+([a_{5} a_{4} a_{3}]- [a_{2} a_{1} a_{0}]) \end{align*}

Regardless of what cc is, since 7c7c is definitely a multiple of 77, the proof is complete if the latter part is a multiple of 77. And here, the property of 999999999999 is used.

A106=A106−A+A=(106−1)A+A=999999A+A=7⋅142857A+A=7c+A \begin{align*} A 10^{6} &=A 10^{6} -A+A \\ &=( 10^{6} -1)A+A \\ &=999999A+A \\ &=7\cdot 142857A+A \\ &=7c+A \end{align*}

Since the above equation holds, the power of 1010 will yield a constant term divisible by 77, reducing the degree by 66 each time.

[anan−1…a1a0]=7c+([anan−1an−2]−[an−3an−4an−5])10n−5+…+([a5a4a3]−[a2a1a0]) \begin{align*} & [a_{n} a_{n-1} … a_{1} a_{0}] \\ =& 7c+([a_{n} a_{n-1} a_{n-2}]-[a_{n-3} a_{n-4} a_{n-5}]) 10^{n-5} +…+([a_{5} a_{4} a_{3}]- [a_{2} a_{1} a_{0}]) \end{align*}

In the above equation, all instances of n−5,n−11,…,0n-5, n-11, … ,0 are multiples of 66, thus

[anan−1…a1a0]=7c+([anan−1an−2]−[an−3an−4an−5])+…+([a5a4a3]−[a2a1a0]) \begin{align*} & [a_{n} a_{n-1} … a_{1} a_{0}] \\ =& 7c+([a_{n} a_{n-1} a_{n-2}]-[a_{n-3} a_{n-4} a_{n-5}])+…+([a_{5} a_{4} a_{3}]-[a_{2} a_{1} a_{0}]) \end{align*}

Therefore,

[anan−1an−2]−[an−3an−4an−5]+…+[a5a4a3]−[a2a1a0] [a_{n} a_{n-1} a_{n-2}]- [a_{n-3} a_{n-4} a_{n-5}]+…+[a_{5} a_{4} a_{3}]-[a_{2} a_{1} a_{0}]

If it’s a multiple of 77, then [anan−1…a1a0][a_{n} a_{n-1} … a_{1} a_{0}] is also a multiple of 77.

Considering the point of 1001=7⋅143=7⋅11⋅131001 = 7 \cdot 143 = 7 \cdot 11 \cdot 13, whether it’s the case of 1111 or 1313, the proof is virtually complete.

■