This is the second note in the series Number Theory: Divisibility. All numbers involved in this note are integers, and letters used in this note stand for integers without further specification.
Recap of Properties:
If and then that is, divisibility is transitive.
If and then that is, the set of multiples of an integer is closed under addition and subtraction operations.
By using this property repeatedly, we have, if and , then , for any integers and . In general, if are multiples of , then
If , then or . Thus, if and , then .
Clearly, for any two integers and , is not always divisible by . But we have the following result, which is called the division algorithm. It is the most important result in elementary number theory.
(The division algorithm) Let and be integers, and . Then there is a unique pair of integers and , such that
The integer is called the (incomplete) quotient when is divided by , called the remainder. Note that the values of has kinds of possibilities, . If , then is divisible by .
It is easy to see that the quotient in the division algorithm is in fact (the greatest integer not exceeding ), and the heart of the division algorithm is the inequality about the remainder : . We will go back to this point later on.
The basic method of proving is to factorize into the product of and another integer. Usually, in some basic problems this kind of factorization can be obtained by taking some special value in algebraic factorization equations. The following two factorization formulae are very useful in proving this kind of problems.
If is a positive integer, then
If is a positive odd number, then
Example 1: Prove that is divisible by .
Proof: By , we have
Therefore, divides .
Example 2: Let and be integers such that . Show that
Proof: Take , in , and substitute by . We have
By , we have
and we are done.
Example 3: For a positive integer , let denote the sum of digits of . Show that if and only if .
Proof: Write (where , and ), then . We have
For , from we get . So every term of the terms in the RHS of is a multiple of , thus implies that their sum is also a multiple of , that is, . Hence, the result can be obtained easily.
Example 4: Let be an odd integer. Prove that for any positive integer , is not divisible by .
Proof: When the statement is obviously true. For , denote the sum by . Then
Since is a positive odd integer, from we know that for every , is divisible by
Thus has remainder when divided by , which implies that is not divisible by (note that ).