Exercises 43
Table 1. Mann-Shanks criterion: Columns containing only bold entries
are indexed by prime numbers.
0 1 2 3 4 5 6 7 8 9 10 11 12 13
0 1
1 1 1
2 1 2 1
3 1 3 3 1
4 1 4 6 4 1
5 1 5 10 10
6 1 6
33. (Louisiana State University Problem Solving Group [PSG02]) Prove
that
54n
+
53n
+
52n
+
5n
+ 1 is composite for every natural number n.
If you know some algebraic number theory, establish the follow-
ing generalization: If q 1 is a squarefree natural number with q
1 (mod 4), then
Φq(qn)
is composite for every natural number n.
Hint (due to J. A. Rouse):
qn
ζ is a difference of squares in Z[ζ],
where ζ denotes a primitive qth root of unity.
34. Table 1 illustrates a primality criterion discovered by Mann & Shanks
[MS72]: Place the rows of Pascal’s triangle in an infinite table, where
the zeroth row (consisting of the single element 1) is placed in column
0. Each successive row is shifted two units right. An element of the nth
row is written in boldface when it is divisible by n. Then the column
number is prime exactly when all entries in its column are written in
boldface. Prove this!
35. (Hayes [Hay65]) Suppose that R is a principal ideal domain with in-
finitely many prime ideals. Show that every nonconstant polynomial
A over R can be written as the sum of two irreducible polynomials of
the same degree as A. Hint: Arrange for both summands to satisfy the
Eisenstein criterion with respect to the same prime.
Previous Page Next Page