Editing Divisibility rule (section)

==Proofs==

===Proof using basic algebra===

Many of the simpler rules can be produced using only algebraic manipulation, creating [[binomial (polynomial)|binomial]]s and rearranging them.  By writing a number as the [[positional notation|sum of each digit times a power of 10]] each digit's power can be manipulated individually.

====Case where all digits are summed====

This method works for divisors that are factors of 10&nbsp;−&nbsp;1 = 9.

Using 3 as an example, 3 divides 9&nbsp;=&nbsp;10&nbsp;−&nbsp;1. That means <math>10 \equiv 1 \pmod{3}</math> (see [[modular arithmetic]]). The same for all the higher powers of 10: <math>10^n \equiv 1^n \equiv 1 \pmod{3}.</math> They are all [[congruence relation|congruent]] to 1 modulo 3. Since two things that are congruent  modulo 3 are either both divisible by 3 or both not, we can interchange values that are congruent modulo 3. So, in a number such as the following, we can replace all the powers of 10 by 1:

: <math>100\cdot a + 10\cdot b + 1\cdot c \equiv (1)a + (1)b + (1)c \pmod{3},</math>

which is exactly the sum of the digits.

====Case where the alternating sum of digits is used====

This method works for divisors that are factors of 10 + 1 = 11.

Using 11 as an example, 11 divides 11&nbsp;=&nbsp;10&nbsp;+&nbsp;1. That means <math>10 \equiv -1 \pmod{11}</math>. For the higher powers of 10, they are congruent to 1 for even powers and congruent to −1 for odd powers:

: <math>10^n \equiv (-1)^n \equiv \begin{cases}
 1 & \text{if } n \text{ is even}, \\
 -1 & \text{if } n \text{ is odd}
\end{cases} \pmod{11}.</math>

Like the previous case, we can substitute powers of 10 with congruent values:

: <math>1000\cdot a + 100\cdot b + 10\cdot c + 1\cdot d \equiv (-1)a + (1)b + (-1)c + (1)d \pmod{11},</math>

which is also the difference between the sum of digits at odd positions and the sum of digits at even positions.

====Case where only the last digit(s) matter====

This applies to divisors that are a factor of a power of 10. This is because sufficiently high powers of the base are multiples of the divisor, and can be eliminated.

For example, in base 10, the factors of 10<sup>1</sup> include 2, 5, and 10. Therefore, divisibility by 2, 5, and 10 only depend on whether the last 1 digit is divisible by those divisors. The factors of 10<sup>2</sup> include 4 and 25, and divisibility by those only depend on the last 2 digits.

====Case where only the last digit(s) are removed====

Most numbers do not divide 9 or 10 evenly, but do divide a higher power of 10<sup>''n''</sup> or 10<sup>''n''</sup>&nbsp;−&nbsp;1. In this case the number is still written in powers of 10, but not fully expanded.

For example, 7 does not divide 9 or 10, but does divide 98, which is close to 100.  Thus, proceed from

: <math>100 \cdot a + b,</math>

where in this case ''a'' is any integer, and ''b'' can range from 0 to 99.  Next,

: <math>(98 + 2) \cdot a + b,</math>

and again expanding

: <math>98 \cdot a + 2 \cdot a + b,</math>

and after eliminating the known multiple of 7, the result is

: <math>2 \cdot a + b,</math>

which is the rule "double the number formed by all but the last two digits, then add the last two digits".

====Case where the last digit(s) is multiplied by a factor====

The representation of the number may also be multiplied by any number relatively prime to the divisor without changing its divisibility.  After observing that 7 divides 21, we can perform the following:

: <math>10 \cdot a + b,</math>

after multiplying by 2, this becomes

: <math>20 \cdot a + 2 \cdot b,</math>

and then

: <math>(21 - 1) \cdot a + 2 \cdot b.</math>

Eliminating the 21 gives

: <math> -1 \cdot a + 2 \cdot b,</math>

and multiplying by −1 gives

: <math> a - 2 \cdot b.</math>

Either of the last two rules may be used, depending on which is easier to perform. They correspond to the rule "subtract twice the last digit from the rest".

===Proof using modular arithmetic===

This section will illustrate the basic method; all the rules can be derived following the same procedure. The following requires a basic grounding in [[modular arithmetic]]; for divisibility other than by 2's and 5's the proofs rest on the basic fact that 10 mod ''m'' is invertible if 10 and ''m'' are relatively prime.

====For 2<sup>''n''</sup> or 5<sup>''n''</sup>====

Only the last ''n'' digits need to be checked.

: <math>10^n = 2^n \cdot 5^n \equiv 0 \pmod{2^n \text{ or } 5^n}.</math>

Representing ''x'' as <math>10^n \cdot y + z,</math>

: <math>x = 10^n \cdot y + z \equiv z \pmod{2^n \text{ or } 5^n},</math>

and the divisibility of ''x'' is the same as that of ''z''.

====For 7====

Since 10 × 5 ≡ 10 × (−2) ≡ 1 (mod 7), we can do the following:

Representing ''x'' as <math>10 \cdot y + z,</math>

: <math>-2x \equiv y -2z \pmod{7},</math>

so ''x'' is divisible by 7 if and only if ''y'' − 2''z'' is divisible by 7.