2. Aurifeuillian Factorizations.

Back

For each base b, certain of the numbers bn_1 factor in a way di_erent from the

factorization obtained in (3) or (4). This second factorization is due to the existence

of special polynomial identities, discovered by and named after Aurifeuille [11, p. v].

These identities show how to write _n(x) in a form which becomes a di_erence of

squares when x has certain values. In particular, putting x = 22k􀀀1 in the identity

x2 + 1 = _2(x2) = (x + 1)2 􀀀 2x

yields the factorization

(5) 24k􀀀2 + 1 = (22k􀀀1 􀀀 2k + 1)(22k􀀀1 + 2k + 1):

Similarly, replacing x by 32k􀀀1 and 122k􀀀1 in the identity

x3 + 1 = (x + 1)_3(􀀀x) = (x + 1)[(x + 1)2 􀀀 3x]

yields the factorizations

(6) 36k􀀀3 + 1 = (32k􀀀1 + 1)(32k􀀀1 􀀀 3k + 1)(32k􀀀1 + 3k + 1)

and

(7) 126k􀀀3 + 1 = (122k􀀀1 + 1)(122k􀀀1 􀀀 22k􀀀13k + 1)(122k􀀀1 + 22k􀀀13k + 1):

For compactness we write formulas (5), (6), (7) with h = 2k 􀀀 1 as

22h + 1 = L2hM2h 33h + 1 = (3h + 1)L3hM3h 123h + 1 = (12h + 1)L3hM3h

III C 2 AURIFEUILLIAN FACTORIZATIONS lxx

where

L2h; M2h = 2h + 1 _ 2k and L3h; M3h = 3h + 1 _ 3k or 12h + 1 _ 2h3k:

In the same way we may set x = 5h; 6h; 7h; 10h and 11h in the respective

identities

x5 􀀀1 = (x 􀀀 1)_5(x) = (x 􀀀 1)[(x2 + 3x + 1)2 􀀀 5x(x + 1)2]

x6 + 1 = (x2 + 1)_6(x2) = (x2 + 1)[(x2 + 3x + 1)2 􀀀 6x(x + 1)2]

x7 + 1 = (x + 1)_7(􀀀x) = (x + 1)[(x + 1)6 􀀀 7x(x2 + x + 1)2]

x10 + 1 = (x2 + 1)_10(x2) and x11 + 1 = (x + 1)_11(􀀀x)

where _10(x2) = (x4 + 5x3 + 7x2 + 5x+ 1)2 􀀀 10x(x3 + 2x2 + 2x + 1)2

and _11(􀀀x) = (x5+5x4􀀀x3􀀀x2+5x+1)2􀀀11x(x4+x3􀀀x2+x+1)2

and obtain the factorizations

55h􀀀1 = (5h􀀀1)L5hM5h; L5h;(8) M5h = 52h+3:5h+1_5k(5h+1)

(9) 66h+1 = (62h+1)L6hM6h; L6h;M6h = 62h+3:6h+1_6k(6h+1)

(10) 77h+1 = (7h+1)L7hM7h; L7h;M7h = (7h+1)3_7k(72h+7h+1)

(11) 1010h+1 = (102h+1)L10hM10h; where L10h;M10h

= 104h+5:103h+7:102h+5:10h+1_10k(103h+2:102h+2:10h+1)

(12) 1111h+1 = (11h+1)L11hM11h; where L11h;M11h

= 115h+5:114h􀀀113h􀀀112h+5:11h+1_11k(114h+113h􀀀112h+11h+1):

The appropriate formulas for L and M are also given at the end of each relevant

main table.

The binomials with an Aurifeuillian factorization can be completely factored

more readily than most other bn _ 1, because they break into two roughly equal

pieces. For this reason, Table 2LM has been extended to 2400, twice as far as the

other base 2 tables. The Aurifeuillian factorizations for the larger bases (in Tables

3+, 5􀀀, 6+, 7+, 10+, 11+ and 12+) are not given in a separate table, but are

incorporated in a special format in the tables themselves and are carried somewhat

farther than the consecutively indexed entries, the extensions being listed below a

line of dashes in the respective tables. (The line of dashes is omitted if it comes at

a page boundary.)

Since the factorizations produced in (5) to (12) cut across those produced in

(3) and (4), it is important to analyze how the two factorizations relate to each

other.

Example 1. Since 156 = 22:39, we have from (4) that

278 + 1 =

Y

dj39

_4d(2) = _4(2)_12(2)_52(2)_156(2)

= (5)(13)(53:157:1613)(13_:313:1249:3121:21841)

and from (5) that

278 + 1 = L78M78 = (13:53:157:13_:313:1249) (5:1613:3121:21841):

lxxi III C 2 AURIFEUILLIAN FACTORIZATIONS

The fact that the second factorization splits both the algebraic and primitive

parts of 278 + 1 suggests that in order to describe this multiplicative structure,

the primitive parts of Ln and Mn should be de_ned so that Ln and Mn can be

expressed as a product of primitive parts as in (3). To do this we denote the

respective primitive parts by L_

n and M_

n. For base b, let "d = "d(b) = [1+(bjd)]=2,

where d is odd, (b; d) = 1 and (bjd) is the Jacobi symbol. (Recall that (bj1) = 1.)

Also, let n = 2sm, m odd, s _ 0. Then we have the formulas (which we state

without proof)

(13) L_

n =

Y0

djm

[(Ln=d)"d(Mn=d)1􀀀"d ]_(d)

and

(14) M_

n =

Y0

djm

[(Ln=d)1􀀀"d(Mn=d)"d ]_(d);

so that

(15) Ln =

Y0

djm

[(L_

n=d)"d(M_

n=d)1􀀀"d ]

and

(16) Mn =

Y0

djm

[(L_

n=d)1􀀀"d(M_

n=d)"d ]:

In each case the prime on the product sign indicates that the product is taken over

the divisors d of m such that (b; d) = 1. It is easily shown that _4n(b) = L_

2nM_

2n

for odd n and that (L_

n;M_

n) = 1.

In Table 2LM (as in the other Aurifeuillian tables) we write the subscript n as

a line number in front of L and M for ease of use, and list the L's and M's on the

right of (15) and (16) with d <m inside parentheses and the known prime factors

of the primitive part after the parentheses as before. (In the _rst column of this

table the line number 4k 􀀀 2 is written only in front of the L, not the M). Hence,

using (13) to (16), the _rst _ve pairs of lines of Table 2LM would be:

2L 1 6L (2M) 1 10L (2M) 5_ 14L (2L) 113 18L (2L,6M) 37

M 5 M (2L) 13 M (2L) 41 M (2M) 29 M (2M,6L) 109

Now, since L_

2 = L_

6 = 1, we can simplify the presentation by omitting 2L and 6L

and writing 2 and 6 for M_

2 and M_

6. These _ve pairs of lines then become:

2 5 6 (2) 13 10L (2) 5_ 14L 113 18L (6) 37

M 41 M (2) 29 M (2) 109

The other simpli_cation of this kind that can be made in the Aurifeuillian tables is

in Table 3+, where the entry

3 (1)L.M

L 1

M 7

III C 2 AURIFEUILLIAN FACTORIZATIONS lxxii

is abbreviated as 3 (1) 7.

Example 2. With b = 2 and n = 78 = 2:39 we have from (15) that

L78 =

Y0

dj39

[(L_

78=d)"d(M_

78=d)1􀀀"d] = L_

2:M_

6:M_

26:L_

78 (17)

= (1)(13)(53:157)(13_

:313:1249);

since M_

6 = M6=L2 = 13 and M_

26 = M26=L2 = 53:157. Also, by interchanging L

and M in (17) we obtain immediately

M78 =M_

2:L_

6:L_

26:M_

78 = (5)(1)(1613)(3121:21841);

since L_

26 = L26=M2 = 1613. These factorizations are given in Table 2LM as

78L (6,26M) 13_:313:1249

M (2,26L) 3121:21841:

Note here that L_

78:M_

78 = _156(2), as it should.

For b > 2, formulas (6) to (12) are given in a three-line format:

n (: : :) L.M

L (: : :) L_

n

M (: : :) M_

n

where the _rst line contains the triple product in (6) to (12) and the second and

third lines give the factorizations of the L and M indicated in the _rst line.

Example 3. With b = 6 and n = 210, we have from (9), (13) and (14) that

L210 =

Y0

dj35

[(L_

210=d)"d(M_

210=d)1􀀀"d ]; where "d = [1+(6jd)]=2:

Thus, L210 =M_

6:M_

30:L_

42:L_

210 and therefore we have directly

M210 = L_

6:L_

30:M_

42:M_

210:

Hence, the factorization of 6210 + 1 = (670 + 1) L210M210 is given in Table 6+ as

210 (2,10,14,70) L.M

L (6M,30M,42L) L_

210

M (6L,30L,42M) M_

210 :

Here the decomposition of the algebraic factor 670 + 1 is of course obtained from

(4).

In computing L_

n and M_

n the following \crossover" theorem [36, p. 181; 37,

p. 46] is sometimes useful. Assume that (b; k) = 1.

If (bjk) = +1; Ln divides Lkn and Mn divides Mkn:

If (bjk) = 􀀀1; Ln divides Mkn and Mn divides Lkn:

lxxiii III D ACKNOWLEDGEMENTS

Навигация