DIVISIBILITY AND THE DIVISION ALGORITHM
We say that a nonzero b divides a if a = mb for some m, where a, b, and m are integers. That is, b divides a if there is no remainder on division. The notation b | a is commonly used to mean b divides a. Also, if b | a, we say that b is a divisor of a.
Subsequently, we will need some simple properties of divisibility for integers, which are as follows:
The Division Algorithm
Given any positive integer n and any nonnegative integer a, if we divide a by n, we get an integer quotient q and an integer remainder r that obey the following relationship:
where |x | is the largest integer less than or equal to x. Equation (4.1) is referred to as the division algorithm.
Figure 4.1a demonstrates that, given a and positive n, it is always possible to find q and r that satisfy the preceding relationship. Represent the integers on the number line; a will fall somewhere on that line (positive a is shown, a similar demonstration can be made for negative a). Starting at 0, proceed to n, 2n, up to qn, such that qn <=a and(q + 1)n > a. The distance from qn to a is r, and we have found the unique values of q and r. The remainder r is often referred to as a residue.