7.4 DIOPHANTINE EQUATIONS 243On the other hand, it is true that if v .l w and u^2 = VW, then v and W must be perfect
squares (this is easy to check by looking at PPFs). So in our problem, as in many
problems, we should now focus our attention on the GCDs of the critical quantities,
which at this moment are z + y and z -y.
Let g := GCD(z + y,z - y). Since z - y and z + y are even, we have 21 g. On the
other hand, g must divide the sum and difference of z - y and z + y. This means that
gl2z and gl2y. But y .l z, so g = 2.
Returning to (5), what can we say about two numbers if their GCD is 2 and their
product is a perfect square? Again, a simple analysis of the PPFs yields the conclusion
that we can write
z + y = 2 r^2 , z - y = 2 i,
where r .l s. Solving for y and z yields y = r^2 - s^2 , z = r^2 + s^2. We're almost done, but
there is one minor detail: if rand s are both odd, this would make y and z both even,
which violates primitivity. So one of r, s must be even, one must be odd.
Finally, we can conclude that all primitive solutions to (4) are given by
x = 2 rs , y = r^2 - s^2 , z = r^2 + s^2 ,
where rand s are relatively prime integers, one odd, one even. •
Factoring, modulo n filtering (especially parity), and GCD analysis are at the heart
of most diophantine equation investigations, but there are many other tools available.
The next example involves inequalities, and a very disciplined use of the tool of com
paring exponents of primes in PPFs. We will use a new notation. Let liin mean that t
is the greatest exponent of p that divides n. For example, 32 11360.
Example 7.4.4 (Putnam 1992) For a given positive integer m, find all triples (n,x,y)
of positive integers, with n relatively prime to m, which satisfy
(6)Solution: What follows is a complete solution to this problem, but we warn you
that our narrative is rather long. It is a record of a "natural" course of investigation: we
make several simplifications, get a few ideas that partially work, and then gradually
eliminate certain possibilities. In the end, our originally promising methods (parity
analysis, mostly) do not completely work, but the partial success points us in a com
pletely new direction, one that yields a surprising conclusion.
OK, let's get going. One intimidating thing about this problem are the two expo
nents m and n. There are so many possibilities! The AM-GM inequality (see page 176 )
helps to eliminate some of them. We have�+i 2 2xy,
which means that