prime p that divides n. There must be at least one such prime p, since

n ≥ 2, and every positive integer can be written as a product of primes.

Clearly, p cannot equal any of the pi , since if it did, then p would divide

n ’ k pi = 1, which is impossible. Therefore, the prime p is not among

i=1

p1 , . . . , pk , which contradicts our assumption that these are the only primes.

2

For a prime p, we may de¬ne the function νp , mapping non-zero integers

to non-negative integers, as follows: for integer n = 0, if n = pe m, where

p m, then νp (n) := e. We may then write the factorization of n into primes

as

pνp (n) ,

n=±

p

where the product is over all primes p, with all but ¬nitely many of the

terms in the product equal to 1.

It is also convenient to extend the domain of de¬nition of νp to include

0, de¬ning νp (0) := ∞. Following standard conventions for arithmetic with

in¬nity (see Preliminaries), it is easy to see that for all a, b ∈ Z, we have

νp (a · b) = νp (a) + νp (b) for all p. (1.4)

From this, it follows that for all a, b ∈ Z, we have

b|a νp (b) ¤ νp (a) for all p,

if and only if (1.5)

and

νp (gcd(a, b)) = min(νp (a), νp (b)) for all p. (1.6)

For a, b ∈ Z a common multiple of a and b is an integer m such that

1.3 Some consequences of unique factorization 9

a | m and b | m; moreover, such an m is the least common multiple of a

and b if m is non-negative and m divides all common multiples of a and b.

In light of Theorem 1.3, it is clear that the least common multiple exists and

is unique, and we denote the least common multiple of a and b by lcm(a, b).

Note that as we have de¬ned it, lcm(a, 0) = 0, and that when both a and

b are non-zero, lcm(a, b) is the smallest positive integer divisible by both a

and b. Also, for all a, b ∈ Z, we have

νp (lcm(a, b)) = max(νp (a), νp (b)) for all p, (1.7)

and

gcd(a, b) · lcm(a, b) = |ab|. (1.8)

It is easy to generalize the notions of greatest common divisor and least

common multiple from two integers to many integers. For a1 , . . . , ak ∈ Z,

with k ≥ 1, we call d ∈ Z a common divisor of a1 , . . . , ak if d | ai for

i = 1, . . . , k; moreover, we call such a d the greatest common divisor of

a1 , . . . , ak if d is non-negative and all other common divisors of a1 , . . . , ak

divide d. It is clear that the greatest common divisor of a1 , . . . , ak exists

and is unique, and moreover, we have

νp (gcd(a1 , . . . , ak )) = min(νp (a1 ), . . . , νp (ak )) for all p. (1.9)

Analogously, for a1 , . . . , ak ∈ Z, with k ≥ 1, we call m ∈ Z a common

multiple of a1 , . . . , ak if ai | m for i = 1, . . . , k; moreover, such an m is called

the least common multiple of a1 , . . . , ak if m divides all common multiples

of a1 , . . . , ak . It is clear that the least common multiple of a1 , . . . , ak exists

and is unique, and moreover, we have

νp (lcm(a1 , . . . , ak )) = max(νp (a1 ), . . . , νp (ak )) for all p. (1.10)

We say that integers a1 , . . . , ak are pairwise relatively prime if

gcd(ai , aj ) = 1 for all i, j with i = j. Note that if a1 , . . . , ak are pairwise rel-

atively prime, then gcd(a1 , . . . , ak ) = 1; however, gcd(a1 , . . . , ak ) = 1 does

not imply that a1 , . . . , ak are pairwise relatively prime.

Consider now the rational numbers Q := {a/b : a, b ∈ Z, b = 0}. Because

of the unique factorization property for Z, given any rational number a/b,

if we set d := gcd(a, b), and de¬ne the integers a := a/d and b := b/d, then

we have a/b = a /b and gcd(a , b ) = 1. Moreover, if a/˜ = a /b , then we

˜b

have ab = a ˜ and so b | a ˜ and since gcd(a , b ) = 1, we see that b | ˜

˜ b, b, b;

˜ = db , it follows that a = da . Thus, we can represent every rational

˜ ˜

if b ˜

number as a fraction in lowest terms, that is, a fraction of the form a /b

10 Basic properties of the integers

where a and b are relatively prime; moreover, the values of a and b are

uniquely determined up to sign, and every other fraction that represents the

˜ ˜ ˜

same rational number is of the form (da )/(db ), for some non-zero integer d.

Exercise 1.10. Let n be a positive integer. Show that if a, b are relatively

prime integers, each of which divides n, then ab divides n. More generally,

show that if a1 , . . . , ak are pairwise relatively prime integers, each of which

divides n, then their product a1 · · · ak divides n.

Exercise 1.11. For positive integer n, let D(n) denote the set of positive

divisors of n. For relatively prime, positive integers n1 , n2 , show that the

sets D(n1 ) — D(n2 ) and D(n1 · n2 ) are in one-to-one correspondence, via the

map that sends (d1 , d2 ) ∈ D(n1 ) — D(n2 ) to d1 · d2 .

Exercise 1.12. Let p be a prime and k an integer 0 < k < p. Show that

the binomial coe¬cient

p p!

= ,

k!(p ’ k)!

k

which is an integer, of course, is divisible by p.

Exercise 1.13. An integer a ∈ Z is called square-free if it is not divisible

by the square of any integer greater than 1. Show that any integer n ∈ Z

can be expressed as n = ab2 , where a, b ∈ Z and a is square-free.

Exercise 1.14. Show that any non-zero x ∈ Q can be expressed as

x = ±pe1 · · · per ,

r

1

where the pi are distinct primes and the ei are non-zero integers, and that

this expression in unique up to a reordering of the primes.

Exercise 1.15. Show that if an integer cannot be expressed as a square of

an integer, then it cannot be expressed as a square of any rational number.

Exercise 1.16. Show that for all integers a, b, and all primes p, we have

νp (a + b) ≥ min{νp (a), νp (b)}, and that if νp (a) < νp (b), then νp (a + b) =

νp (a).

Exercise 1.17. For a prime p, we may extend the domain of de¬nition of νp

from Z to Q: for non-zero integers a, b, let us de¬ne νp (a/b) := νp (a) ’ νp (b).

(a) Show that this de¬nition of νp (a/b) is unambiguous, in the sense that

it does not depend on the particular choice of a and b.

(b) Show that for all x, y ∈ Q, we have νp (xy) = νp (x) + νp (y).

1.3 Some consequences of unique factorization 11

(c) Show that for all x, y ∈ Q, we have νp (x + y) ≥ min{νp (x), νp (y)},

and that if νp (x) < νp (y), then νp (x + y) = νp (x).

(d) Show that for all non-zero x ∈ Q, we have

pνp (x) ,

x=±

p

where the product is over all primes, and all but a ¬nite number of

terms in the product is 1.

Exercise 1.18. Let n be a positive integer, and let Cn denote the number of

pairs of integers (a, b) such that 1 ¤ a ¤ n, 1 ¤ b ¤ n and gcd(a, b) = 1, and

let Fn be the number of distinct rational numbers a/b, where 0 ¤ a < b ¤ n.

(a) Show that Fn = (Cn + 1)/2.

(b) Show that Cn ≥ n2 /4. Hint: ¬rst show that Cn ≥ n2 (1’ 2 ),

d≥2 1/d

and then show that d≥2 1/d2 ¤ 3/4.

Exercise 1.19. This exercise develops a characterization of least common

multiples in terms of ideals.

(a) Arguing directly from the de¬nition of an ideal, show that if I and J

are ideals of Z, then so is I © J.

(b) Let a, b ∈ Z, and consider the ideals I := aZ and J := bZ. By part

(a), we know that I © J is an ideal. By Theorem 1.5, we know that

I © J = mZ for some uniquely determined non-negative integer m.

Show that m = lcm(a, b).

Exercise 1.20. For a1 , . . . , ak ∈ Z, with k > 1, show that

gcd(a1 , . . . , ak ) = gcd(gcd(a1 , . . . , ak’1 ), ak )

and

lcm(a1 , . . . , ak ) = lcm(lcm(a1 , . . . , ak’1 ), ak ).

Exercise 1.21. Show that for any a1 , . . . , ak ∈ Z, if d := gcd(a1 , . . . , ak ),

then dZ = a1 Z + · · · + ak Z; in particular, there exist integers s1 , . . . , sk such