1. Algebraic and Primitive Factors.

Back

The way in which bn 􀀀 1 factors is determined in part by the polynomial

factorization

xn 􀀀1 =

Y

djn

(2) _d(x); n _ 1;

where _d(x) is the d th cyclotomic polynomial, given by the formula

_d(x) =

Y

_jd

(x_ 􀀀 1)_(d=_)

where _ is the Mobius function [55, p. 28]. Since _d(x) is irreducible over the

integers for d _ 1, the polynomial factorization in (2) is complete. Of course, it

does not follow that the factorization

bn 􀀀1 =

Y

djn

(3) _d(b)

is complete, since the integer _d(b) may not be prime.

(a) Let n _ 3 be odd and let 1; d1; : : : ; ds be the proper divisors of n. Then

the factorization (3) is presented in Table b􀀀 in the format

n (1; d1; : : : ; ds) p1: p2 : : :

where p1 : p2 : : : is the product of the known factors of _n(b), the primitive part

in the factorization. The algebraic part is then (bn􀀀1)=_n(b). The divisor d = 1

is omitted from the parentheses in Table 2􀀀, because the factor _1(2) = 1 is trivial.

Since in this format a factor _d(b) with d < n is indicated only by its subscript,

each of its prime factors needs to be entered only once in the table (after the

parentheses on line d), rather than throughout the table at each place where _d(b)

occurs.

A prime divisor p of bn􀀀1; n _ 2, is called primitive if p-bk􀀀1 for any k < n.

Otherwise, it is called algebraic. It is clear that any prime p dividing _d(b) in

(3) for d < n will be algebraic, since then p will divide bd 􀀀 1 because _d(b) does.

On the other hand, any primitive factor of bn 􀀀 1 will have to divide the primitive

part _n(b). It is not true, however, that every prime factor of _n(b) is primitive.

An algebraic prime factor of _n(b) is called intrinsic and is indicated in the main

tables by an asterisk, except when p = n = 2. For example, _21(2) = 7_:337. Note

that 7 divides 23 􀀀 1, so 7 is an algebraic factor of _21(2).

A primitive prime divisor p of bn 􀀀 1 is said to have rank n, and we write

r(p) = n. A prime p is an intrinsic factor of _m(b) if and only if m = pkr(p); k _ 1.

Furthermore, when p is intrinsic, it divides _m(b) just once, if m >2.

(b) To _nd the factorization of b2n 􀀀1 = (bn 􀀀 1)(bn +1) requires the table of

the factorizations of bn + 1; n _ 1. Thus, writing 2n = 2tm;m odd, and using (2),

we obtain

xn + 1 = (x2n 􀀀 1)=(xn 􀀀 1) =

Y

dj2n

_d(x)=

Y

djn

_d(x);

lxix III C 2 AURIFEUILLIAN FACTORIZATIONS

so

xn + 1 =

Y

djm

_2td(x):

This result shows that the primitive part of bn + 1 is _2n(b), and

(4) bn + 1 =

Y

djm

_2td(b):

If the proper divisors of m are 1; d1; : : : ; ds, then, since _2n(b) is the primitive part

of bn + 1, the factorization in (4) is given in Table b+ in the format

n (2t􀀀1; 2t􀀀1d1; : : : ; 2t􀀀1ds) p1: p2 : : :

where as before p1: p2 : : : is the product of the known prime factors of _2n(b).

It should be noted that the very long table for the factorization of 2n + 1

has been broken into three tables, as in the earlier tables [11], which give the

factorization of 22k􀀀1 + 1; 24k􀀀2 + 1 and 24k + 1. They are labeled respectively

\Table 2+ (odd)", \Table 2LM" and \Table 2+(4k)". For each other base b,

however, there is only the single \Table b+".

Навигация