The Art and Craft of Problem Solving

226 CHAPTER 7 NUMBER THEORY

Then there exist integers x, y such that px + ay = 1. Now we need to use the hypothesis

that plab. Let's get ab into the picture by multiplying the last equality by b:

pxb+aby =b.

But now we have written b as the sum of two quantities, each of which are multiples

of p. Consequently, b is a multiple of p, a contradiction. _

Finally, we can prove the FTA. Statement 7.1.6 is the key idea that we need. Let's

avoid notational complexity by considering a concrete example. Let n = 23. 76. How

do we show that this factorization is unique? First of all, we can show that n couldn't

contain any other prime factors. For suppose that, say, 171 n. Then repeated applica­

tions of 7.1.6 would force the conclusion that either 1712 or 171 7, which is impossible,

as no two different primes can divide one another. The other possibility is that n has

2 and 7 as factors, but there is a factorization with different exponents; for example,

maybe it is also true that n = 28. 73. In this case we would have

23. 76 = 2^8. 73 ,

and after dividing out the largest exponents of each prime that we can from each side,

we get

73 = 2^5.

This reduces to the first case: we cannot have two factorizations with different primes.

You should check with a few more examples that this argument can be completely

generalized. We can rest; FTA is true. _

This important property of integers was a consequence of the division algorithm,

which in tum was a consequence of the well-ordering principle and the fact that 1 is

an integer. That's all that we needed!

Here is a simple application of FTA-style reasoning-a solution to Problem 5 .4.13

on page 173.

Example 7.1.7 Recall that polynomial with integer coefficients is called monic if the

term with highest degree has coefficient equal to 1. Prove that if a monic polynomial

has a rational zero, then this zero must in fact be an integer.

Solution: Let the polynomial be f(x) := x" +an- 1 x"- 1 + ... +alx+aO. Let u/v

be a zero of this polynomial. The crux move: without loss of generality, assume that

u .1 v. Then we have

un an_IUn- 1 alU

- + +···+-+ao=O.

o 0 - 1 V

The natural step now is to get rid of fractions, by multiplying both sides by �. This

gives us

or

U n = - a( n-I n-I n)

n-Iu v+··· +al uv +aov.