# Number theory

## The integers

The set of integers {... ,-3,-2,-1,0.1,2,3,...} is denoted by the symbol Z.

• 2.79 Definition Let a, b be integers. Then a divides b (equivalently: a is a divisor of b, or a is a factor of b) if there exists an integer c such that b = ac. If a divides b, then this is denoted by a.
• 2.80 Example (i) -3|18, since 18 = (-3)(-6). (ii) 173|0, since 0 = (173)(0). □

The following are some elementary' properties of divisibility.

• 2.81 Fact (properties of divisibility) For all a, b, c e Z, the following are true:
• (i) a|o.
• (ii) If a and bc, then a|c.
• (iii) If a and a|c, then a(bx + cy) for all x. у € Z.
• (iv) If a and ba, then a = ±b.

2.82 Definition (division algorithm for integers) If a and h are integers with h > 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.

• 2.83 Fact Let a, b € Z with b Ф 0. Then a div b = ji/b and a mod b = a — b[a/b.
• 2.84 Example If a = 73, b = 17, then <7 = 4 and r = 5. Hence 73 mod 17 = 5 and 73 div 17 = 4. □
• 2.85 Definition An integer c is a common divisor of a and b if c|a and c.
• 2.86 Definition A non-negative integer d is the greatest common divisor of integers a and b, denoted d = gcd(o, b), if
• (i) d is a common divisor of a and b; and
• (ii) whenever c|a and c, then cd.

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

2.87 Example The common divisors of 12 andl8 are {±1, ±2, ±3, ±6},andgcd(12,18) = 6.

• 2.88 Definition A non-negative integer d is the least common multiple of integers a and b, denoted d = lcm(a, b), if
• (i) ad and bd and
• (ii) whenever a|c and bc, then dc.

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

• 2.89 Fact If a and b are positive integers, then lcm(a, b) = a - bj gcd(o, b).
• 2.90 Example Since gcd(12,18) = 6, it follows that lcm(12,18) = 12 • 18/6 = 36. □
• 2.91 Definition Two integers a and bare said to be rc/flf;vely prime or copriwe if gcd(a, b) = 1.
• 2.92 Definition An integer p > 2 is said to be prime if its only positive divisors are 1 and p. Otherwise, p is called composite.

The following are some well known facts about prime numbers.

• 2.93 Fact If p is prime and pab, then either p|a or p (or both).
• 2.94 Fact There are an infinite number of prime numbers.

2.95 Fact (prime number theorem) Let tv(x) denote the number of prune numbers < x. Then

This means that for large values of x, n(x) is closely approximated by the expression xj In x. For instance, when a: = Ю10,тг{х) = 455,052,511, whereas \_xj lii.rj = 434,294,481. A more explicit estimate for n(x) is given below.

2.96 Fact Let тг(.т) denote the number of primes < x. Then for x > 17 and for x > 1

2.97 Fact (fundamental theorem of arithmetic) Every integer n > 2 has a factorization as a product of prime powers:

where the p, are distinct primes, and the e, are positive integers. Furthermore, the factorization is unique up to rearrangement of factors.

2.98 Fact If a = p f pf • ■ ■ pekk, b = p{lp^2 ■ ■ ■ ркк, where each e* > 0 and /, > 0, then and

• 2.99 Example Let a = 4864 = 28 • 19, b = 3458 = 2 • 7 • 13 • 19. Then gcd(4864,3458) =
• 2 • 19 = 38 and lcm(4864,3458) = 28 • 7 • 13 • 19 = 442624. □
• 2.100 Definition For n > 1, let ф(п) denote the number of integers in the interval [1, n] which are relatively prime to n. The function ф is called the Euler phi function (or the Euler totient function).
• 2.101 Fact (properties of Euler phi function)
• (i) If p is a prime, then ф(р) = p — 1.
• (ii) The Euler phi function is multiplicative. That is, if gcd(m, ?г) = 1, then ф(тп) = ф(т) ■ ф{п).
• (iii) If n = р'ф р'ф2 ■ • ■ p'k is the prime factorization of n, then

Fact 2.102 gives an explicit lower bound for ф(п).

2.102 Fact For all integers n > 5,