## CHAPTER 7

## Number Theory

#### Learning Objectives

On completing this chapter, you should be able to:

state the definitions of a factor and a multiple of an integer

state and prove the division algorithm

define the ideas of the greatest common divisor (gcd) and the least common multiple (lcm)

define a pair of relatively prime numbers

use the Euclidean algorithm to find the gcd

find the gcd and lcm of pairs of numbers by prime factorization

define a prime number

define congruence classes and congruence relations

solve linear congruence equations for small numbers

state and prove Fermat's theorem and its generalization due to Euler

##### 7.1 INTRODUCTION AND MOTIVATION

There was a time when Number Theory was considered a very pure subject in the sense ...