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

Get Discrete Mathematics and Combinatorics now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.