Divisibility and multiple test proofs

Divisibility Tests

Divisibility by 2: A number is divisible by 2 if its last digit is any of 0, 2, 4, 6, or 8.
Divisibility by 3: A number is divisible by 3 if the sum of its digits is divisible by 3.
Divisibility by 4: A number is divisible by 4 if the number formed by its last two digits is divisible by 4.
Divisibility by 5: A number is divisible by 5 if its last digit is either 0 or 5.
Divisibility by 6: A number is divisible by 6 if it is divisible by both 2 and 3.
Divisibility by 8: A number is divisible by 8 if the number formed by its last three digits is divisible by 8.
Divisibility by 9: A number is divisible by 9 if the sum of its digits is divisible by 9.
Divisibility by 10: A number is divisible by 10 if its last digit is 0.

A positive integer n is a multiple of integers m and k if there exist integers x and y such that n = xm and n = yk.
A common mistake is to assume that if n is a multiple of m and a multiple of k, then n is a multiple of m x k; this is incorrect without additional assumptions.

To prove these tests, we need the concept of congruences, which are properties of number divisibility.
Congruences allow us to say that if a number a is congruent to a number b modulo n (written as a = b (mod n)), then a and b have the same remainder when divided by n.
For example, the divisibility by 3 test can be proven by the property that if a = b (mod 3) and c = d (mod 3), then a+c = b+d (mod 3). If we set a, b, c, and d as the digits of the number, then saying the sum of the digits is divisible by 3 is equivalent to saying the original number is divisible by 3.
Similar congruence arguments can establish the rest of the divisibility tests.

A proof of multiples involves induction and the definition of a multiple.
To prove n is a multiple of m, show for some integer k, n = k x m.
To show that n is a multiple of both m and k, demonstrate n = x m and n = y k, where x and y are both integers.
Counterexamples disprove the often-assumed property that a multiple of two numbers is also a multiple of their product. For example, 12 is a multiple of 3 and 4, but not of their product, 12.