# 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* • ■ ■ *p*^{e}k^{k}, *b **= p{ ^{l}p^^{2} ■ ■ ■ р*

_{к}

^{к}, where each e* > 0 and /, > 0, then and

- 2.99 Example Let a = 4864 = 2
^{8}• 19,*b =*3458 = 2 • 7 • 13 • 19. Then gcd(4864,3458) = - 2 • 19 = 38 and lcm(4864,3458) = 2
^{8}• 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*=*р'ф р'ф*is the prime factorization of n, then^{2}■ • ■ p'k

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

2.102 Fact For all integers *n* > 5,