Editing Divisibility rule (section)

===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.