Back to the school of divisibility!

       \ \ \ \ \ \ We all have learned about divisibility tests for many certain numbers in our elementary school. In this note, I will be discussing about the method that those tests are derived from. For every derivation that I will be discussing, we will be taking the variable number of the form

N=anan−1an−2⋯a2a1a0‾\large N = \overline {a_n a_{n-1} a_{n-2} \cdots a_2 a_1 a_0}

OR\text{OR}

N=10nan+10n−1an−1+10n−2an−2+⋯+102a2+10a1+a0N = 10^n a_n + 10^{n-1} a_{n-1} + 10^{n-2} a_{n-2} + \cdots + 10^2 a_2 + 10 a_1 + a_0

I will just present you with those special cases that you are familiar with and you can apply this idea to create divisibility test for any positive integer you may want to. Also I will be using the term 'number' only and only for the set of positive integers or natural numbers in this context. Also keep in mind that you must have at least some basic knowledge of modular arithmetic to understand the derivations.

Let's begin!

Divisibility by 2‾\large \underline{\text{Divisibility by 2}}

Statement

Any number with 2, 4, 6, 82, \ 4, \ 6, \ 8 and 00 as the unit digit is divisible by 22.

Proof

We have,

N=10nan+10n−1an−1+10n−2an−2+⋯+102a2+10a1+a0N = 10^n a_n + 10^{n-1} a_{n-1} + 10^{n-2} a_{n-2} + \cdots + 10^2 a_2 + 10 a_1 + a_0

Taking (mod2)\pmod{2} of NN we get,

N≡0+0+0+⋯+0+0+a0(mod2)As 10k where k≥1 is always divisible by 2N≡a0(mod2)\begin{aligned} N & \equiv 0+0+0+ \cdots +0+0+ a_0 \pmod{2} \qquad \qquad \qquad \small \color{#3D99F6}{\text{As} \ 10^k \ \text{where} \ k \ge 1 \ \text{is always divisible by} \ 2} \\ N & \equiv a_0 \pmod{2} \end{aligned}

Therefore, N≡0(mod2)N \equiv 0 \pmod{2} if a0≡0(mod2)a_0 \equiv 0 \pmod{2}.

Since, a0a_0 is a single digit number. The only values that satisfy are 0, 2, 4, 60, \ 2, \ 4, \ 6 and 88.

The same approach can be used for 55 and 1010 as well due to the fact that 10k10^k where k≥1k \ge 1 is always divisible by 55 and 1010 as well and hence, the values fitting for a0a_0 in this case are 00 and 55 for the number 55 and 00 for the number 1010, thus proving the divisibility tests of 55 and 1010.

                                                                                                                                                                                              Q.E.D. \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{Q.E.D.}

Divisibility by 3‾\large \underline{\text{Divisibility by 3}}

Statement

Any number whose sum of digits is divisible by 33 is also divisible by 33.

Proof

We have,

N=10nan+10n−1an−1+10n−2an−2+⋯+102a2+10a1+a0N = 10^n a_n + 10^{n-1} a_{n-1} + 10^{n-2} a_{n-2} + \cdots + 10^2 a_2 + 10 a_1 + a_0

Taking (mod3)\pmod{3} of NN we get,

N≡1×an(mod3)+1×an−1(mod3)+1×an−2(mod3)+⋯+1×a2(mod3)+1×a1(mod3)+1×a0(mod3)                                                                                                               As 10k−1 where k≥1 is always divisible by 3≡(an+an−1+an−2+⋯+a2+a1+a0)(mod3)\begin{aligned} N & \equiv 1 \times a_n\pmod{3} + 1 \times a_{n-1}\pmod{3} + 1 \times a_{n-2}\pmod{3} + \cdots + 1 \times a_2\pmod{3} + 1 \times a_1\pmod{3} + 1 \times a_0\pmod{3} \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \small \color{#3D99F6}{\text{As} \ 10^k-1 \ \text{where} \ k \ge 1 \ \text{is always divisible by} \ 3} \\ & \equiv \left( a_n + a_{n-1} + a_{n-2} + \cdots + a_2 + a_1 + a_0 \right) \pmod{3} \end{aligned}

Therefore, N≡0(mod3)N \equiv 0 \pmod{3} if an+an−1+an−2+⋯+a2+a1+a0≡0(mod3) a_n + a_{n-1} + a_{n-2} + \cdots + a_2 + a_1 + a_0 \equiv 0 \pmod{3}.

Thus, the sum of digits must be divisible by 33 for the number to be divisible by 33.

The same approach can be used for 99 as well due to the fact that 10k−110^k - 1 where k≥1k \ge 1 is always divisible by 99 as well and hence, the sum of digits of the number in this case must be divisible by 99 so that the number itself is divisible by 99, thus proving the divisibility test of 99.

                                                                                                                                                                                              Q.E.D. \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{Q.E.D.}

Divisibility by 4‾\large \underline{\text{Divisibility by 4}}

Statement

Any number whose digits in the tens and units place taken in that order respectively, if divisible by 44, then the number is also divisible by 44.

Eg- The number 1156411564 is divisible by 44 because 6464 is divisible by 44.

Proof

We have,

N=10nan+10n−1an−1+10n−2an−2+⋯+102a2+10a1+a0N = 10^n a_n + 10^{n-1} a_{n-1} + 10^{n-2} a_{n-2} + \cdots + 10^2 a_2 + 10 a_1 + a_0

Taking (mod4)\pmod{4} of NN we get,

N≡0+0+0+⋯+0+10a1+a0(mod4)As 10k where k≥2 is always divisible by 4N≡10a1+a0(mod4)\begin{aligned} N & \equiv 0+0+0+ \cdots +0+10 a_1+ a_0 \pmod{4} \qquad \qquad \qquad \small \color{#3D99F6}{\text{As} \ 10^k \ \text{where} \ k \ge 2 \ \text{is always divisible by} \ 4} \\ N & \equiv 10 a_1 + a_0 \pmod{4} \end{aligned}

Therefore, N≡0(mod4)N \equiv 0 \pmod{4} if 10a1+a0=a1a0‾≡0(mod4)10a_1 + a_0 = \overline {a_1 a_0} \equiv 0 \pmod{4}.

Thus, the if the tens and units place of a number taken in that order is divisible by 44 then the number is also divisible by 44.

The same approach can be used for 2525 as well due to the fact that 10k10^k where k≥2k \ge 2 is always divisible by 2525 as well and hence, if the digits in the tens and units place of a number taken in that order respectively, if divisible by 2525, then the number is also divisible by 2525.

                                                                                                                                                                                              Q.E.D. \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{Q.E.D.}

Divisibility by 6‾\large \underline{\text{Divisibility by 6}}

Statement

Any number which is divisible by 22 and 33 both is also divisible by 66 as well.

Proof

This doesn't require any proof other that the fact that if

N≡0(mod2)N \equiv 0 \pmod{2} and N≡0(mod3)N \equiv 0 \pmod{3}, then N≡0(mod2×3=6)N \equiv 0 \pmod{2 \times 3 = 6}. As 22 and 33 are co-prime numbers.

                                                                                                                                                                                              Q.E.D. \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{Q.E.D.}

Divisibility by 7‾\large \underline{\text{Divisibility by 7}}

Statement

Any number whose absolute difference between twice the units digit and the number formed by the rest of the digits, if it is 00 or divisible by 77, then the number is also divisible by 77.

Eg- The number 343343 is divisible by 77 because 34−2×3=2834 - 2 \times 3 = 28 is also divisible by 77.

Proof

We have,

N=10nan+10n−1an−1+10n−2an−2+⋯+102a2+10a1+a0N = 10^n a_n + 10^{n-1} a_{n-1} + 10^{n-2} a_{n-2} + \cdots + 10^2 a_2 + 10 a_1 + a_0

Let,

N=10nan+10n−1an−1+10n−2an−2+⋯+102a2+10a1+a0=7kfor some integer kN = 10^n a_n + 10^{n-1} a_{n-1} + 10^{n-2} a_{n-2} + \cdots + 10^2 a_2 + 10 a_1 + a_0 = 7k \qquad \quad \small \color{#3D99F6}{\text{for some integer} \ k}

N=10(10n−1an+10n−2an−1+10n−3an−2+⋯+10a2+a1)+a0=7kN = 10 \left( 10^{n-1} a_n + 10^{n-2} a_{n-1} + 10^{n-3} a_{n-2} + \cdots + 10 a_2 + a_1 \right) + a_0 = 7k

Add and subtract 20a020 a_0 on the L.H.S. to get,

N=10(10n−1an+10n−2an−1+10n−3an−2+⋯+10a2+a1)+20a0−20a0+a0=7kN = 10 \left( 10^{n-1} a_n + 10^{n-2} a_{n-1} + 10^{n-3} a_{n-2} + \cdots + 10 a_2 + a_1 \right) + 20 a_0 - 20 a_0 + a_0 = 7k

N=10(10n−1an+10n−2an−1+10n−3an−2+⋯+10a2+a1−2a0)+21a0=7kN = 10 \left( 10^{n-1} a_n + 10^{n-2} a_{n-1} + 10^{n-3} a_{n-2} + \cdots + 10 a_2 + a_1 - 2 a_0 \right) + 21 a_0 = 7k

N=10(10n−1an+10n−2an−1+10n−3an−2+⋯+10a2+a1−2a0)=7k−21a0N = 10 \left( 10^{n-1} a_n + 10^{n-2} a_{n-1} + 10^{n-3} a_{n-2} + \cdots + 10 a_2 + a_1 - 2 a_0 \right) = 7k - 21 a_0

N=10(10n−1an+10n−2an−1+10n−3an−2+⋯+10a2+a1−2a0)≡0(mod7)N = 10 \left( 10^{n-1} a_n + 10^{n-2} a_{n-1} + 10^{n-3} a_{n-2} + \cdots + 10 a_2 + a_1 - 2 a_0 \right) \equiv 0 \pmod{7}

N=10(anan−1an−2⋯a2a1‾−2a0)≡0(mod7)N = 10 \left( \overline{a_n a_{n-1} a_{n-2} \cdots a_2 a_1} - 2 a_0 \right) \equiv 0 \pmod{7}

Since, 10≡3(mod7)10 \equiv 3 \pmod{7}, therefore, for NN to be divisible by 77, anan−1an−2⋯a2a1‾−2a0≡0(mod7)\overline{a_n a_{n-1} a_{n-2} \cdots a_2 a_1} - 2 a_0 \equiv 0 \pmod{7}.

Thus, for a number if the absolute difference between twice the units digit and the number formed by the rest of the digits, is 00 or divisible by 77, then that number is also divisible by 77.

                                                                                                                                                                                              Q.E.D. \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{Q.E.D.}

Divisibility by 8‾\large \underline{\text{Divisibility by 8}}

Statement

Any number whose digits in the hundreds, tens and units place taken in that order respectively, if divisible by 88, then the number is also divisible by 88.

Eg- The number 7415274152 is divisible by 88 because 152152 is divisible by 88.

Proof

We have,

N=10nan+10n−1an−1+10n−2an−2+⋯+102a2+10a1+a0N = 10^n a_n + 10^{n-1} a_{n-1} + 10^{n-2} a_{n-2} + \cdots + 10^2 a_2 + 10 a_1 + a_0

Taking (mod8)\pmod{8} of NN we get,

N≡0+0+0+⋯+102a2+10a1+a0(mod8)As 10k where k≥3 is always divisible by 8N≡100a2+10a1+a0(mod8)\begin{aligned} N & \equiv 0+0+0+ \cdots +10^2 a_2+10 a_1+ a_0 \pmod{8} \qquad \qquad \qquad \small \color{#3D99F6}{\text{As} \ 10^k \ \text{where} \ k \ge 3 \ \text{is always divisible by} \ 8} \\ N & \equiv 100 a_2 + 10 a_1 + a_0 \pmod{8} \end{aligned}

Therefore, N≡0(mod8)N \equiv 0 \pmod{8} if 100a2+10a1+a0=a2a1a0‾≡0(mod8)100 a_2 + 10a_1 + a_0 = \overline {a_2 a_1 a_0} \equiv 0 \pmod{8}.

Thus, the if the hundreds, tens and units place of a number taken in that order is divisible by 88 then the number is also divisible by 88.

The same approach can be used for 125125 as well due to the fact that 10k10^k where k≥3k \ge 3 is always divisible by 125125 as well and hence, if the digits in the hundreds, tens and units place of a number taken in that order respectively, if divisible by 125125, then the number is also divisible by 125125.

                                                                                                                                                                                              Q.E.D. \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{Q.E.D.}

Divisibility by 11‾\large \underline{\text{Divisibility by 11}}

Statement

Any number whose absolute difference of the sum of digits occurring in the even positions and the sum of digits occurring in odd positions, if it is 00 or divisible by 1111, then the number is also divisible by 1111.

Proof

We have,

N=10nan+10n−1an−1+10n−2an−2+⋯+102a2+10a1+a0N = 10^n a_n + 10^{n-1} a_{n-1} + 10^{n-2} a_{n-2} + \cdots + 10^2 a_2 + 10 a_1 + a_0

Taking (mod11)\pmod{11} of NN we get,

N≡±an∓an−1±an−2⋯∓a2±a1∓a0(mod11)As 10k≡+1(mod11) if k is even and 10k≡−1(mod11) if k is oddN \equiv \pm a_n \mp a_{n-1} \pm a_{n-2} \cdots \mp a_2 \pm a_1 \mp a_0 \pmod{11} \qquad \qquad \small \color{#3D99F6}{\text{As} \ 10^k \equiv +1 \pmod{11} \ \text{if} \ k \ \text{is even and} \ 10^k \equiv -1 \pmod{11} \ \text{if} \ k \ \text{is odd}}

  • Suppose nn is even, then we have:

N≡an−an−1+an−2−⋯+a2−a1+a0(mod11)N≡(an+an−2+⋯+a2+a0)−(an−1+an−3+⋯+a3+a1)(mod11)N \equiv a_n - a_{n-1} + a_{n-2} - \cdots + a_2 - a_1 + a_0 \pmod{11} \\ N \equiv \left( a_n + a_{n-2} + \cdots + a_2 + a_0 \right) - \left( a_{n-1} + a_{n-3} + \cdots + a_3 + a_1 \right) \pmod{11}

Therefore, N≡0(mod11)N \equiv 0 \pmod{11} if (an+an−2+⋯+a2+a0)−(an−1+an−3+⋯+a3+a1)≡0(mod11)\left( a_n + a_{n-2} + \cdots + a_2 + a_0 \right) - \left( a_{n-1} + a_{n-3} + \cdots + a_3 + a_1 \right) \equiv 0 \pmod{11}, given that nn is even.

  • Suppose nn is odd, then we have:

N≡−an+an−1−an−2+⋯+a2−a1+a0(mod11)N≡(an−1+an−3+⋯+a2+a0)−(an+an−2+⋯+a3+a1)(mod11)N \equiv -a_n + a_{n-1} - a_{n-2} + \cdots + a_2 - a_1 + a_0 \pmod{11} \\ N \equiv \left( a_{n-1} + a_{n-3} + \cdots + a_2 + a_0 \right) - \left( a_n + a_{n-2} + \cdots + a_3 + a_1 \right) \pmod{11}

Therefore, N≡0(mod11)N \equiv 0 \pmod{11} if (an−1+an−3+⋯+a2+a0)−(an+an−2+⋯+a3+a1)≡0(mod11)\left( a_{n-1} + a_{n-3} + \cdots + a_2 + a_0 \right) - \left( a_n + a_{n-2} + \cdots + a_3 + a_1 \right) \equiv 0 \pmod{11}, given that nn is odd.

From the above two conditions, we infer that for a number to be divisible by 1111, its absolute difference of the sum of digits occurring in the even positions and the sum of digits occurring in odd positions, should be 00 or divisible by 1111.

                                                                                                                                                                                              Q.E.D. \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{Q.E.D.}

Divisibility by 12‾\large \underline{\text{Divisibility by 12}}

Statement

Any number which is divisible by 33 and 44 both is also divisible by 1212 as well.

Proof

This doesn't require any proof other that the fact that if

N≡0(mod3)N \equiv 0 \pmod{3} and N≡0(mod4)N \equiv 0 \pmod{4}, then N≡0(mod3×4=12)N \equiv 0 \pmod{3 \times 4 = 12}. As 33 and 44 are co-prime numbers.

                                                                                                                                                                                              Q.E.D. \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{Q.E.D.}

Divisibility by 13‾\large \underline{\text{Divisibility by 13}}

Statement

Any number whose sum of four times the units digit and the number formed by the rest of the digits, if it is divisible by 1313, then the number is also divisible by 1313.

Eg- The number 169169 is divisible by 1313 because 16+4×9=5216 + 4 \times 9 = 52 is also divisible by 1313.

Proof

We have,

N=10nan+10n−1an−1+10n−2an−2+⋯+102a2+10a1+a0N = 10^n a_n + 10^{n-1} a_{n-1} + 10^{n-2} a_{n-2} + \cdots + 10^2 a_2 + 10 a_1 + a_0

Let,

N=10nan+10n−1an−1+10n−2an−2+⋯+102a2+10a1+a0=13kfor some integer kN = 10^n a_n + 10^{n-1} a_{n-1} + 10^{n-2} a_{n-2} + \cdots + 10^2 a_2 + 10 a_1 + a_0 = 13k \qquad \quad \small \color{#3D99F6}{\text{for some integer} \ k}

N=10(10n−1an+10n−2an−1+10n−3an−2+⋯+10a2+a1)+a0=13kN = 10 \left( 10^{n-1} a_n + 10^{n-2} a_{n-1} + 10^{n-3} a_{n-2} + \cdots + 10 a_2 + a_1 \right) + a_0 = 13k

Add and subtract 40a040 a_0 on the L.H.S. to get,

N=10(10n−1an+10n−2an−1+10n−3an−2+⋯+10a2+a1)+40a0−40a0+a0=13kN = 10 \left( 10^{n-1} a_n + 10^{n-2} a_{n-1} + 10^{n-3} a_{n-2} + \cdots + 10 a_2 + a_1 \right) + 40 a_0 - 40 a_0 + a_0 = 13k

N=10(10n−1an+10n−2an−1+10n−3an−2+⋯+10a2+a1+4a0)−39a0=13kN = 10 \left( 10^{n-1} a_n + 10^{n-2} a_{n-1} + 10^{n-3} a_{n-2} + \cdots + 10 a_2 + a_1 + 4 a_0 \right) - 39 a_0 = 13k

N=10(10n−1an+10n−2an−1+10n−3an−2+⋯+10a2+a1+4a0)=13k+39a0N = 10 \left( 10^{n-1} a_n + 10^{n-2} a_{n-1} + 10^{n-3} a_{n-2} + \cdots + 10 a_2 + a_1 + 4 a_0 \right) = 13k + 39 a_0

N=10(10n−1an+10n−2an−1+10n−3an−2+⋯+10a2+a1+4a0)≡0(mod13)N = 10 \left( 10^{n-1} a_n + 10^{n-2} a_{n-1} + 10^{n-3} a_{n-2} + \cdots + 10 a_2 + a_1 + 4 a_0 \right) \equiv 0 \pmod{13}

N=10(anan−1an−2⋯a2a1‾+4a0)≡0(mod13)N = 10 \left( \overline{a_n a_{n-1} a_{n-2} \cdots a_2 a_1} + 4 a_0 \right) \equiv 0 \pmod{13}

Since, 10≡10(mod13)10 \equiv 10 \pmod{13}, therefore, for NN to be divisible by 1313, anan−1an−2⋯a2a1‾+4a0≡0(mod13)\overline{a_n a_{n-1} a_{n-2} \cdots a_2 a_1} + 4 a_0 \equiv 0 \pmod{13}.

Thus, for a number if the sum of four times the units digit and the number formed by the rest of the digits, is divisible by 1313, then that number is also divisible by 1313.

                                                                                                                                                                                              Q.E.D. \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{Q.E.D.}

Based on the same approach, a divisibility test can be made for each and every number by just observing their patterns over successive powers of 1010.

Hope you enjoyed reading this.

                                                                                                                                                                                              Thank you \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ Thank \ you

#NumberTheory

Note by Tapas Mazumdar
4 years, 8 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list
  • bulleted
  • list

1. numbered
2. list
  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai−1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 ∑i=13 \sum_{i=1}^3
\sin \theta sin⁡θ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

WOOOOOAHHH! You just shown the proof for most of the divisibility rules. You should post your note as another separate wiki called "Proof of divisibilities rules"!

Pi Han Goh - 4 years, 8 months ago

Log in to reply

Well, that wiki has already been made. They have proved what I have proved in another way.

Btw, thanks. :)

Tapas Mazumdar - 4 years, 8 months ago

Log in to reply

I agree that adding the proofs for these divisibility rules will be helpful for those who want to learn about the underlying number theoretic. It would be great if you can contribute to Proof Of Divisibility Rules and we can link it from there.

Calvin Lin Staff - 4 years, 8 months ago

Log in to reply

@Calvin Lin – Thanks for encouraging me to write this wiki. You can check it out here. Feel free to share your opinion about the wiki and it would be very kind of you if you can contribute by citing problems and examples.

Tapas Mazumdar - 4 years, 8 months ago

Thanks for encouraging me to write this wiki. You can check it out here. Feel free to share your opinion about the wiki and it would be very kind of you if you can contribute by citing problems and examples.

Tapas Mazumdar - 4 years, 8 months ago

Excellent!

I hope my grade for 4 and 5 teachers knew it, I always troubled them asking for the proof :P

Swapnil Das - 4 years, 8 months ago

Log in to reply

Haha, well I had asked my teachers too about this once. But they told that it wasn't in our syllabus and shut my mouth.

Tapas Mazumdar - 4 years, 8 months ago

Log in to reply

Syllabus based school studies is what preventing India from becoming a developing country to a developed country.

Harsh Shrivastava - 4 years, 8 months ago

Log in to reply

@Harsh Shrivastava – That is a weak part of our system. If a student is keen to learn more about a certain concept, their teachers must put their best efforts to help them go through these concepts. Moreover, it is the fact that our teachers have the burden of keeping things straight to syllabus and that's part of the problem that even they don't think it is important for them to help a child go through the concepts that are beyond the school syllabus.

Tapas Mazumdar - 4 years, 8 months ago

Nicely written!

Harsh Shrivastava - 4 years, 8 months ago

Log in to reply

Thank you! :D

Tapas Mazumdar - 4 years, 8 months ago
×

Problem Loading...

Note Loading...

Set Loading...