252 Answers to Exercises and Solutions to Problems
representation of n as a product of primes, or n/p1 < n, and we can ap-
ply the induction hypothesis to obtain the desired representation. By an
extension of Exercise (c), it can be shown that the only primes dividing n
must be the pi and thence that the representation is unique.
(e)418 = 2.11.19 1606 = 2.11.73
20119 = 11.31.59 34782 = 2.3.11.17.316.4. (a) If pa and pb are the highest powers of the prime p dividing m
and n respectively, then pmin(alb) and ~“~(~1~) are the highest powers of p
dividing u and v respectively.
(b) and (c) are straightforward consequences of (a).
6.6. (a) x = 2 + 5k where k is an integer.
(b) (i) no solution. (ii) x E 2 (mod 3).
(d) There exist u and v such that g = au + mu. Let x = (b/g)u.
(e) uu z au (mod m) + m I u(u - v) + m I (u - v) (since gcd(u, m) =
- =F u 3 v (mod m).
7.4. (d) F[t] is th e set of all polynomials in the n variables tl with co-
efficients in F. We prove that F[t] is an integral domain by induction on
the number of variables. It is true for n = 0 (see Exercise 5). Suppose it
is true for n - 1 variables. Let f and g be two nonzero polynomials over
F. Write f(t) = art; +... and g(t) = b,tf, +. .., where the coefficients
are polynomials in the n - 1 variables tl,... , t,-1 and a, # 0, b, # 0.
Then f(t)g(t) = urbstL+’ +.... By the induction hypotheses, the leading
coefficient is nonzero, so fg # 0.
7.5. (a) If ab = 0, a # 0, then b = u-lab = 0.
(b) ac = bc + (u - b)c = 0 + a - b = 0 + a = b.
7.6. (c) Z, is a field if and only if m is prime.
(d) If m is composite, then ub = m - 0 (mod m) is possible for numbers
a and b, neither of which are divisible by m.
7.7. The following polynomials cannot be expressed as a product of polyno-
mials of lower degree: t, t+l, t2+t+l, t3+t+l, t3+t2+1, t4+t3+t2+t+l,
t4 + t3 + 1, t4 + t + 1. Since the leading coefficient is 1 and there are two
choices for each other coefficient, there are 2d polynomials altogether of
degree d.
Solutions to Problems
Chapter 18.1.tanA+tanB=-p,tanAtanB=q.Ifq=l,A+B~?r/2(mod?r),
which yields the result q. If q # 1, the expansion formula for tan(A + B)
yields -p = (1 - q) tan(A + B), whencesin2(A + B) + psin(A + B) cos(A + B) + q cos2(A + B)