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.