O'Reilly logo

Discrete Mathematics and Combinatorics by T. Sengadir

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

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

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