228 CHAPTER 7 NUMBER THEORY
Problems and Exercises
7.1. 9 Write out a formal proof of the FfA.
7.1.10 Review Example 3.2.4 on page 77, an inter
esting problem involving GCD, LCM and the extreme
principle.
7.1.11 Prove that the fraction (n 3 + 2n)/(n^4 +3n^2 + I)
is in lowest terms for every positive integer n.
7.1.12 The Euclidean Algorithm. Repeated use of the
division algorithm allows one to easily compute the
GCD of two numbers. For example, we shall compute
(333,51 ):333 = 6·51 + 27;
51 = I. 27 + 24;
27 =1·24+3;
24 = 8·3+0.We start by dividing 333 by 51. Then we divide 51 by
the remainder from the previous step. At each succes
sive step, we divide the last remainder by the previous
remainder. We do this until the remainder is zero, and
our answer-the GCD-is the final non-zero remain
der (in this case, 3).
Here is another example. To compute (89,24),
we haveso the GCD is I.
89 = 3 ·24 + 17;
24 = 1·17 +7;
17=2· 7+3;
7=2·3+1;This method is called the Euclidean Algorithm.
Explain why it works!
7.1.13 Linear Diophantine Equations. Since 171. II,
there exist integers x. y such that 17x + Ily = I. For
example, x = 2, y = -3 work. Here is a neat trick
for generating more integer solutions to 17x+ 11y= I:
Just letx=2+ llt, y=-3- 17t,
where t is any integer.
(a) Verify that x = 2 + Ilt,y = -3 - 17t will be a
solution to 17x + Ily = I, no matter what tis.
This is a simple algebra exercise, and is reallyjust a nice example of the add zero creatively
tool.
(b) Show that all integer solutions to 17x + Ily = I
have this form; i.e., if x and y are integers sat
isfying 17x+ Ily = I, then x = 2+ Ilt,y =
-3 - 17t for some integer t.
(c) It was easy to find the solution x = 2,y = -3
by trial and error, but for larger numbers we
can use the Euclidean algorithm in reverse. For
example, use the example in Problem 7.1.12 to
find x, y such that 89x + 24y = I. Start by writ
ing I as a linear combination of 3 and 7; then
write 3 as a linear combination of 7 and 17; etc.
(d) Certainly if x = 2,y = -3 is a solution to 17x+
Ily = I, then x = 2u,y = -3u is a solution
to 17 x + II y = u. And as above, verify that
all solutions are of the form x = 2u + Ilt,y =
-3u- 17t.
(e) This method can certainly be generalized to any
linear equation of the form ax + by = c, where
a, b, c are constants. First we divide both sides
by the GCD of a and b; if this GCD is not a di
visor of c there cannot be solutions. Then we
find a single solution either by trial and error, or
by using the Euclidean algorithm.
(f) To see another example of generating infinitely
many solutions to a diophantine equation, look
at the problems about Pell's Equation (7.4.17-
7.4.22).
7.1.14 Consider the set F := {a + bH,a,b E Z}.
Define the norm function N by N(a + bH) = a^2 +
6b^2 • This is a "natural" definition; it is just the square
of the magnitude of the complex number a + biV6, and
it is a useful thing to play around with, because its val
ues are integers.
(a) Show that the "norm of the product is equal to
the product of the norm"; i.e., if a, f3 E F, then
N(af3) = N(a)N(f3).
(b) Observe that if a E F is not an integer (i.e .. if it
has a non-zero imaginary part), then N (a) � 6.
(c) An F -prime is an element of F that has no fac
tors in F other than I and itself. Show that 2
and 5 are F -primes.
(d) Show that 7 and 31 are not F -primes.