Elementary Number Theory with Programming

4DIVISORS AND PRIME DECOMPOSITION

We present an ancient theorem on the representation of positive integers as products of prime numbers. The consequences of this theorem are important for a host of reasons.

DIVISORS

A factor of a number is called a divisor. Thus, 10 has the divisors 1, 2, 5, and 10. The divisors of n other than n are called proper divisors. The proper divisors of 10 are, therefore, 1, 2, and 5, while its divisors are 1, 2, 5, and 10. A divisor of n is said to divide n. Thus, 5 divides 10, while 7 does not divide 10. The symbol for “divides” is a vertical line. When a divides b, we write a | b. Whenever a divides b, observe that b is a multiple of a, that is, b = ka, for some integer k. Thus, 5 | 10, while 10 = 2 × 5. In fact, this is an “if and only if” statement:

• a divides b if and only if b is a multiple of a.

In symbols, we have, using the two-way implication arrow,

(4.1)

Here is a nice way to think about (4.1). Even though 20 divides 100, one may write 100 = 4 × 25, preventing us from seeing the 20. On the other hand, we can write 100 = 5 × 20, thereby showing us the divisor (or factor) 20.

Example:

Let N = 17 × 31 × 101. Show that 31 | N. While this seems obvious enough, let’s use (4.1). Let k = 17 × 101. Then N = 31k in which case 31 | N. I had a student who did this problem by multiplying 17, 31, and 101 to find N and then dividing N by 31 yielding ...