O'Reilly logo

Elementary Number Theory with Programming by Jeanine Meyer, Marty Lewinter

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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,

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.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required