2.1 Topics in Number Theory 2

Definition 2.1.2 (division algorithm for integers)ifa and b are integers with b 1, then

ordinary long division of a by b yields integers q (the quotient) and r (the remainder) such that a = qb + r, where 0 r<b.

Moreover, q and r are unique. The remainder of the division is denoted a mod b, and the

quotient is denoted a div b.

Example 2.1.2 if a = 73, b = 17, then q = 4 and r = 5. Hence 73 mod 17 = 5 and

73 div17 = 4.

Definition 2.1.3 An integer c is a common divisor of a and b if c|a and c|b.

Definition 2.1.4 A non-negative integer d is the greatest common divisor of integers a

and b, denoted d = gcd(a, b), if

1. d is a common divisor of a and b; and

2. whenever c|a, and c|b, then c|d.

Equivalently, gcd(a, b) is the largest positive integer that divides both a and b, with the

exception that gcd(0, 0) = 0.

Example 2.1.3 The common divisors of 12 and 18 are {±1, ±2, ±3, ±6}, and gcd(12, 18) =

6.

Definition 2.1.5 A non-negative integer d is the least common multiple of integers a and

b, denoted l = lcm(a, b), if

1. a|l and b|l; and

2. whenever a|c, and b|c, then l|c.

Equivalently, lcm(a, b) is the smallest non-negative integers divisible by both a and b.

Theorem 2.1.1 If a and b are positive integers, then lcm(a, b)=a · b/gcd(a, b).

Example 2.1.4 Since gcd(12, 18) = 16, it follows that lcm(12, 18) = 12 · 18/6 = 36.