Divisibility Properties of Integers

Basic properties

Theorem 1
  1. If a is not 0, then a | 0 and a | a
  2. 1 | b for any b
  3. If a | b, then a | bc for any c
  4. If a | b and b | c, then a | c
  5. If a | b and a | c, then a | (bx+cy) for any x and y
The proof is straightforward.

Theorem 2
If a | b and b is not 0, then |a| is smaller than or equal to |b|.
Proof. If a | b and b is not zero, there exists and integer c with |c| > 0 such that ac=b. But then |b|=|a|*|c| is not smaller than |a|.

Corollary 1
If a and b are positive integers and a | b and b | a, then a=b.

The greatest common divisor

Definition 1
If d is the largest common divisor of a and b, it is called the greatest common divisor of a and b and is denoted by (a,b).

Theorem 3
If a and b are not both zero and if d=(a,b), then d is the least element in the set of all positive integers of the form ax+by.
 Proof. Let C be the set of all positive integers of the form ax+by. By hypothesis, at least one of a,b is different from zero. Suppose a is nonzero. If a > 0, then a is a member of C and if a < 0, -a is a member of C. Therefore, C is not empty and so, by the well-ordering principle, C must have a least element. Let

be the least element of C. It suffices to show that d=e.

There exist integers q and r with 0 <= r < e such that a=eq+r. Thus,

which is of the form ax+by. If r is not zero, then it is a member of C, which contradicts the assumption that e is the smallest member of C. Thus, r=0 and e | a. Similarly, one can show that e | b. Hence, e is a common divisor of a and b, so e does not exceed d. On the other hand, since e=ax0 + by0 and d | a and d | b, it follows from Theorem 1(v) that d | e. Hence, d does not exceed e by Theorem 2, so d=e.

Theorem 4
d=(a,b) if and only if d > 0, d | a, d | b, and f | d for every common divisor of a and b.
Proof. We assume that a and b are not both zero.
(i) Suppose, first, that d=(a,b). Then d | a and d | b, and by Theorem 3, d=ax+by > 0 for some integers x and y. But then, if f | a and f | b, then f | d by Theorem 1(v).
(ii) Conversely, suppose d > 0, d | a, d | b, and f | d for every common divisor f of a and b. Then d is a common divisor of a and b and, by Theorem 2, |f| does not exceed d. Thus, d=(a,b) by Definition 1.