Discrete Mathematics and Combinatorics

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 ...