We all feel quite competent performing basic arithmetic operations such as division so one may wonder why a section of the text appears to be devoted to this topic. The fact is that we have learned our skills by rote and may not completely understand the principles behind the simplistic operations that we take for granted. The solutions to many sophisticated problems require an understanding of these principles. The area of mathematics that seeks to understand these principles is called number theory.

We all have an intuitive understanding of what it means for one number to divide evenly into another. Definition 1 on page 112 gives a formal definition of that idea. The examples and theorem that follow in the text further our understanding.

Every positive integer greater than 1 is either a prime or a composite number. A prime is evenly divisible only by itself and 1.

Theorem 2 states the Fundamental Theorem of Arithmetic. Every positive integer is equal to a product of primes.

We normally write the product in a special way; smallest primes first and duplicate factors written as a power.

Examples:

1. Give the prime factorization of 12.

12 = 2² * 3

 

2. Give the prime factorization of 792

Theorem 4 is The Division Algorithm. It is really not an algorithm at all but an ordinary theorem. Let a and d be positive integers. There are unique integers q and r such that a = d * q + r where (0<=r<d)

This theorem simply formalizes what we know to be ordinary division. I.e. if one divides a number a by a divisor, d, one obtains a quotient q and a remainder r where the remainder is less than the divisor.

Example:

51 divided by 9 gives a quotient of 5 and a remainder of 6. 51 = 9 * 5 + 6

These are just what their names imply. The greatest common divisor (GCD) of two integers a and b is the largest number that (evenly) divides both a and b. The least common multiple (LCM) of two integers a and b is the smallest integer, c, such that such that a divides c and b divides c.

There are numerous methods of finding the greatest common divisor and least common multiple (see your text, pages 116 and 117). One simple method is to first write out the prime factorization of a and the prime factorization of b. The greatest common divisor may be found by taking only the prime factors which a and b have in common. This implies that one take the smallest exponent for primes that appear in both factorizations. I.e. the factors of the GCD must be factors of both a and b.

Examples:

1. Find the GCD of 60 and 792.

First find the prime factorizations of the two numbers.

60 = 12 = 2² * 3 * 5 and 792 = 792 = 2³ * 3² * 11

2. Find the LCM of 60 and 792.

Again, first find the prime factorizations of the two numbers.

60 = 12 = 2² * 3 * 5 and 792 = 792 = 2³ * 3² * 11

Modular arithmetic is much like ordinary integer arithmetic in most respects. The discerning difference is the presence of a special number called the modulus (or mod for short) and the fact a modular arithmetic system contains only the integers that lie between 0 and the mod. 0 is included but the mod is excluded. For example, mod 5 arithmetic utilizes the numbers 0, 1, 2, 3, 4. Your text gives an excellent formal description of modular arithmetic on pages 118 – 120. Intuitively one may consider every integer to be equivalent to one of the numbers in the modulo system. This equivalence may be determined by the following procedure. Divide the integer under consideration by the modulus. The remainder is the integer that is equivalent to the original integer. This equivalence is called a congruence in modular arithmetic parlance.

Examples:

1. What integers make up the mod 7 system?

Answer: The mod 7 system consists of the integers in the set {0, 1, 2, 3, 4, 5, 6}

 

2. What integer in the mod 7 system is congruent to 100?