A NOTE ON THE PRIMALITY OF 62" + 1 AND 102" + 1

H. C. WILLIAMS*

University

of Manitoba,

Winnipeg,

(Submitted
1.

Manitoba,

November

Canada R3T 2N2

1986)

INTRODUCTION

In 1877, Lucas [3] presented the first practical test for the primality of
numbers Fn = 2 2

the Fermat

+ 1.

We give a version of this test below, using

the slightly modified form which Lucas used later in [5, p. 313] and with some
minor errors corrected.
Test (T1.1) for the Primal ity of Fn = 2 2 * + 1 (r = 2n)
Let SQ = 6 and define S^+1
composite if Fn\Si

the prime

is a prime when Fn\Sr_1;

Fn

for all 7' < r - 1.

script for which Fn\St,

t+1

= ? - 2.

Fn is

Finally, if t is the least sub-

divisors of Fn must have the form

+ 1.

2 q

Three weeks after Lucas' announcement of this test, Pepin [8] pointed out
that the test was possibly not effective; that is, it might happen that a prime
Fn would divide St , where t is too small for the primality of Fn to be proved.
He provided the following effective primality test.
Test (T1.2) for the Primality of Fn
Let SQ = 5 2 and define S^+1=
S

v-1

E -1 (mod

? (mod Fn).

Fn is a prime if and only if

F ).

n n

Pepin also noted that his test would be valid with SQ = 10 2 .

Somewhat later, Proth [9], [10] gave, without a complete proof, another
effective test for the primality of Fn.
with S

= 3 .

His test is essentially that of Pepin

The proof of Proth s test was completed by Lucas [7], who also

noted [5, p. 313] that Pepin's test would be valid for SQ = a 2 when the Jacobi
symbol (a/F ) = - 1 .
While effective tests for the primality of Fn have been known for almost
100 years, little seems to have been done concerning the development of effec-

*Research
296

supported

by NSERC of Canada, Grant #A7649

[Nov.

A NOTE ON THE PRIMALITY OF 62" + 1 AND 1O2* + 1

tive tests for the primality of other integers of the form (2a) 2 + 1. The two
smallest values of a after 1 for which this form could possibly yield primes
distinct from the Fermat numbers are a = 3 and a = 5.
numbers by (?n = 6

+ 1 and Hn = 10

form 2A5

+ 1.

Riesel [11] denoted these

+ 1; he also provided a small table of fac-

Now Gn is of the form A3r+

tors for some of these numbers.

r

1 and Hn is of the

These are forms of integers for which Lucas [4], [5], [6] pre-

sented primality

tests.

These tests, which are given in a modified and cor-

rected form (there are several errors in LucasT statements of these tests) make
use of the Fibonacci numbers {Um}, where UQ = 0 , U

= 1, and Uk,

= Uk + Uk_

Note that neither Test T1.3 nor Test Tl.4 is an effective test for the primality of N.
Test (T1.3) for the Primality of A 3 r + 1
Let N = A3r

+ 1 with N E 1 (mod 10). Put S0

fine

Sk_1

E S{

N is a prime when N\Sr_1;

E USA/UA

(mod N) and de-

+ 3 (mod N).

- 3Sl

(1.1)

if t is the least subscript such that

the prime factors of N must be of the form 2q3

t+1

+ 1 or

There are a number of puzzling aspects of this test.

restrict himself to a test for numbers N E 1 (mod 5)?

2q3

t+1

N\St,
- 1.

First, why did Lucas

Of course, as we shall

see below, it is necessary for N E 1 (mod 5) in order to use the Fibonacci

numbers in a primality

test for N9

but

other Lucas

sequences could also be

used. For example, if N E -1 (mod 4 ) , we could use P = 4, Q = 1; if N E 5 (mod

8 ) , we could use P = 10,Q = 1; and if N E 1 (mod 8 ) , we could use P = 6, Q = 1
(see Section 2 ) . It may be that because of Lucas 1 great interest in Fibonacci
numbers, he restricted his values of N to those that could be tested by making
use of

them.

Also, why did Lucas give this test in a form which, unlike Tl.l

and T1.4, does not allow for the inclusion of a test for the compositeness of
Nt

Finally, to the authorfs knowledge, nowhere among the vast number of iden-

tities that Lucas developed for the Lucas functions does he mention the simple
identity on which (1.1) is based.
Lucas also gave:
Test (T1.4) for the Primality of N = 2A5 r + 1
Put SQ E UA (mod N) and define ^
a prime when the first Sk
(i < r)

1988]

+1

E 25S\

+ 255^ + 5Sk

divisible by N is Sp;

(mod N) . N is

if none

of the

Si

is divisible by N9 N is composite; if t is the least subscript

297

A NOTE ON THE PRIMALITY OF 62" + 1 AND 10*" + 1

such that N\St9

t

then
t

+ 1 or 2q5

2q5

The purpose

the prime

factors of N must be of the form

I.

of this paper is to derive tests for the primality of Gn and

Hn s which are very much in the spirit of LucasT test for the primality of Fn .
We will do this by modifying tests T1.3 and Tl-4.
our tests will be effective.

Further, like PepinTs test,

In order to achieve this, we shall be guided by

the methods developed by Williams [12], [13], and [14].

here that the techniques we use here

It should be mentioned

could also be applied, as in the manner

of [14], to other numbers of the form Arn + 1.

2.
In order

SOME PROPERTIES OF THE LUCAS FUNCTSONS

to develop

primality tests for Gn and Hn, we will require some

properties of the Lucas functions Vn and Un.

Most of these properties are well

known and are included here for reference.

Let a, 3 be the zeros of x2

- Px + Q, where P, Q are coprime integers. We

define
Vn = a" + B n , Un = (a* - 3n)/(a - 3 ) ,
and put A = (a - 3 ) 2 = -P2 - 4.

(2.1)

The following identities can be found in [5]

or verified by direct substitution from (2.1):

V2 -- hV2n = kQn,
v
n
v2n = V2 - 2Q\

(2.2)

u2n = unvn,

(2.4)

3n

= Vn(V

(2.3)

- 3(3") ,

(2.5)

(2.6)

Usn = Un(MJ + 3Q ),
2
n
Usn = Un(V - Q ),
V5n =
U

Vn(Vkn
2

Sn

- 5Q U
k

= Un(A U

Usn =

Un (Vkn

(2.7)
+

+ 5Q"AU
n 2

- 3Q V

If we put Xn = U3n/Un,

2n

(2.8)

5Q ),
2

2n

(2.9)

5Q ),

2n

(2.10)

+ Q ) .
then

Xn = hU2n + 3Qn,

(2.H)

by (2.6), and
X3n
by ( 2 . 1 1 ) .
X3n
298

= MJ23n + 3Q3n

= MJ2X2n + 3Q3n

= X2n{Xn - 3Qn) + 3Q3n ,

Hence,
= X3n - 3QnX2 + 3Q3n;

(2.12)
[Nov.

A NOTE ON THE PRIMALITY OF 62" + 1 AND 1Q2" + 1

also
X

= USn^2n

2n

by ( 2 . 4 ) ,

= & 3n ^ J ( ^ / / ) = X (X - 2Qn) ,

( 2 . 5 ) , and ( 2 . 2 ) .

X&n = X\{Xn

H e n c e , by ( 2 . 1 2 ) , we g e t

- 2Qn)3

- 3Q2nX2(Xn

- 2Qn)2

To o b t a i n a r e s u l t a n a l o g o u s t o ( 2 . 1 2 )
Yn = A2Ukn + 5QnAU2 +
by ( 2 . 9 ) ;

+ 3Q6n.

(2.13)

f o r Yn = U5n/Un>

we n o t e

that

5Q2n,

thus,
= AZU^

Y5n

+ 5Q5nAU2Y2

= Ykn(Yn - 5QnAU2n - 5Q2n)

5Q10n
+ 5Q5nAU2Y2

5Q10n.

We g e t
Y5n

= Yl + 5Qn(Qn

- MJ2n)Jhn + 5Q5nAU*Y*

+ 5Q10n .

(2.14)

For the development of one of our tests, it will be convenient to define

Here the modulus N is assumed to be coprime to Q. From (2.8) and (2.2), we get
W

10n

n&n

"

5W

+ 5 ) 2 - 2 (mod N) .

(2.16)

Also, by (2.10), we have

WloJVlnW1*"

3W

n + 1 (mod JO-

(2- 17 )

We will also require some standard number-theoretic properties of the Lucas

functions. We list these as a collection of theorems together with appropriate
references.

We let p be an odd prime and put

e = (A/p), n = (/p),
e

where ( /p) is the Legendre symbol.

Theorem 2 . 1 ( C a r m i c h a e l

[ 1 ] , Lehmer [ 2 ] ) :

Theorem 2.2 (Lehmer [2]):

Theorem 2.3 (Carmichael

I f pfAQ, t h e n p | [ / p _ .
if a n d onl

If pj(AQ9 then p|^ ( p _ e ) / 2

[1], p. 51): The g.c.d.

of.Upn/Un

y if n = 1 D
and Un divides p.

(This result is true as well for p = 2.)

Theorem 2.4:

Let g.c.d. (/I/, 2pQ) = 1.

If p\m9

N\Um,

then the prime factors of N must be of the form kp

and g.c.d. (Um/p9

N) = 1,

1, where V is the highest

power to which p occurs as a factor of m (pv||tfz).

By combining Theorem 2.4 with Theorem 2.3, we get the following

1988]

299

A NOTE ON THE PRIMALITY OF 62" + 1 AND 102" + 1

Corollary:

If g.c.d.(N,

pnIVn

2pQ) = 1 and

^mod #>'

then the prime factors of N must be of the form kpv

If we put p = 2, we have Upk /Uk

= Vk ; hence, N - Fn

P, Q we have 7^_ r w 2 = 0 (mod Z!/) .

must have

1, where pv~1||m.
is a prime if for some

On the other hand, if N = Fn is a prime, we

V(N_1)/2 = 0 (mod i!7) if ^ | A C

(A/tf) = 1, and (/#) = - 1 . This will

certainly be the case if we put P = a + 15 6 = # (a = a, 3 =

-1.

Thus, N = Fn

= a, and

1) 5 where (a/N)

is a prime if and only if V(N_ ^ / 2 E 0 (mod N) when P = a+ 1,

(a/217) = - 1 . This, of course, is the Pepin (a = 5, 10) or the Proth

(a = 3) test for the primality of

Fn.

To extend these ideas to the Gn and the Hn numbers, we must find a result
analogous to Theorem 2.2 for /(p_ ) / 3 and /(p_ew5 when e = 1.

This can be done

by using a simple modification of an idea developed in Williams [12] and [13].

We describe this briefly

here and

refer the reader to [13] for more details.

(In [13] we deal with the case p E -q E 1 (mod v)

We let p, q9
q 1

and r be odd primes such that p E q E 1 (mod r) and let K =

Write t = ind m9

GF(p ~ )m

only.)

fixed primitive root of q.

where m E g*

(mod q)

(0 < < a - 2) and ^ is a

We consider the Gauss sum

q-l

(5, o)) - 5 indfc00. . k

1

where and OJ are, respectively, primitive r t h and a th roots of 1 in K.

If, as

in [13], we let j = ind p,

q<* = (5, o))p,

q3 = ( r 1 , oo)p,

then a + 3, a3 G F(p), and in X,

(aa)^"1^ =

(?s

^P-I

(g5

a3)-i(59

) = g"J".

Thus, if P E a + 3 (mod p) and S E a3 (mod p) , then [/

U

if

(p-i)/r

E 0 (mod p) . Also

^ (mod p ) 5

p^-D/r ^ 0, 1 (mod

q).

This result is analogous to Theorem 2.2; however, in order for it to be

useful, we must be able to compute values for a + 3 and ag. The value of a3 is
simply qr

, but a + 3 is rather more complicated.

It can be written as

(2-- 3)/2

a + P=

T,

C(i,9 P:} q ) ^

(mod

)s

(2.18)

^=0

300

[Nov.

A NOTE ON THE PRIMALITY OF 62* + 1 AND 1 02" + 1

where the coefficients C(i, r, q)

tion of a certain polynomial

are independent of p, and R can be any solu-

congruence (modulo p) .

In the case of r = 3 5 R

does not occur in (2.18); in the case of r = 5, R can be any solution of

x2

+ x - 1 E 0 (mod p ) .

For more details on R and tables of C(i,r,

[14].

q), we refer the reader to [12] and

Here, it is sufficient to note that C (0,

3, 7) = 1, C(0, 5, 11) = -57,

and C(l, 5, 11) = -25.

3.

THE PRIMALITY TESTS

It is evident from the results in Section 2 that it is a very simple matter

to develop a sufficiency test for the primality of numbers like Gn and Hn.

One

need only select some integer a such that g.c.d.(a, N) = 1, put P = a + 1, Q =

a, and determine whether
U

N-l/U(N-l)/r

= Onodff).

Here, p = 3 for N = Gn

(3-D

and r = 5 for N = # n .

If (3.1) holds, N is a prime;

however, if (3.1) does not hold, we have no information about N and must select
another value for a.

In practical tests for the primality of these numbers we

would use, instead of (3.1), the two conditions

g.c.d.(a(/v-1)/p - 1, N) = 1

(3.2a)

aN~l

(3.2b)

and

In this

= 1 (mod N).

case, if (3.2a) and (3.2b) hold, then (3.1) holds; if (3.2b) does not

hold, N is composite. Also, if N is a prime, the first value of a selected (by

trial) usually causes both (3.2a) and (3.2b) to hold.
is not effective, in that we cannot give a priori

Nevertheless, this test

a value for a such that, if

If is a prime, (3.2a) and (3.2b) must hold.

We will now give effective tests for the primality of Gn and Hn.
note that, since (A/Gn) = (5/Gn)
bers in a test

= (2/5) = - 1 , we cannot use the Fibonacci num-

for the primality of Gn.

However, we can still give a very

simple test like Test T1.2 for the primality of

Let N = Gn.

We first

Gn.

By the results at the end of the last section we know that if

P = 1 and Q = 1 then, since N2 f 0, 1 (mod 7 ) , we must have

when N is a prime.
(Q/N)

1988]

Also, under the assumption that I is a prime,

= (7/tf) = (N/7)

= (2/7) = 1

and

U(N_l)/2

= 0 (mod N)

301

A NOTE ON THE PRIMAL STY OF 62" + 1 AND 10*" + 1

by Theorem 2.2. Further, since U(N_l)/3

t 0 (mod N) , we cannot have U(N_l)/6

E0

(mod 71/) by (2.4); hence,

%-D/2/y(ff-i)/6

(mod " )

If we define Zffl E (U3m/Um)Q'm

Z

sm = Zl^m

by putting 5

(3-3)

= XmQ~m

(mod /I/), then by (2.13) we have

" 2 ) 3 - 3Z*(Zra - 2 ) 2 + 3 (mod N) .

= Zck

(mod 212), we have

k + i = Sk(Sk

~ 2 > 3 - 3Sl(Sk

- 2 ) 2 + 3 (mod N).

(3.4)

If r = 2", then

It follows that, if 5 r E 0 (mod 212) , then any prime factor of 21/ must have the
form k3zn

1. Since (2 3 2 * - l ) 2 > Zl/, we see that 21/ must be a prime.

Now 3
^0

(U3/U1)Q'1

and ^ / ^ = P 2 - Q;

(mod /!/)

h.e n c e ,
S

2
o = P Q-

- 1 E 7"1 - 1 E 3(21/ - 2)/7 (mod 21/).

(3.6)

Thus, by combining the results (3.6), (3.4), (3.5), (3,3), and the theorems of
Section 2, we get the following necessary and sufficient primality test for Gn:
Primality Test (T3-1) for N = 62" + 1 (r = 2n)
1.
Sk

+1

2.

Put SQ = 3(21/ - 2)/7 and define

= S\{Sk

- 2 ) 3 - 3S*(Sk

- 2 ) 2 + 3 (mod 21/).

21/ is a prime if and only if

S

E 0 (mod 212) .

r -1

Unfortunately, because of the difficulty in finding R,

the primality test

which we shall develop for Hn is not as simple or elegant as T3.1.

formula (2.14) for Y
Y5n

Also, the

is not as simple as (2.12); that is, we cannot express

in terms of a simple polynomial in Yn and Qn only.

However, in this case,

we can directly integrate Lucas' Test T1.4 into an effective test for the primality of Hn.
Let 212 = Hn.

Since N2 ^ 0, 1 (mod 11), by the results at the end of Section

2 we know that, if 21/ is a prime, then

U

N-l/U(N-l)/5

( mod ^

when P E -57 - 25P (mod 212) , Q = ll

302

<3'7>
3

= 1331, and
[Nov.

A NOTE ON THE PRIMALITY OF 62" + 1 AND 102* + 1

Rz

0 (mod N).

+ R

If we put Tv

(3.8)

(mod N), by (2.16) we get

W10*

5Tl + 5) :

T\ (Tl

2 (mod tf)

(3.9)

Hence, if r = 2", we also get

T

W
r - 1 - ^(N-

}-(ff- 1)/10
7 7
(A- D/5*

1)/10

(mod tf)

It follows from (2.17) that (3.7) holds if and only if

3T:p -

r - 1

0 (mod N),

+ i

(3.10)

As mentioned above, the difficulty in using this as a test for the primality of Hn resides in the fact that we do not usually know a priorii?.

We can, however, apply the noneffective Test T1.4 of Lucas.

a value for
If this suc-

ceeds, we need not use the result above; but, even if it fails, it will provide
us with a value for R and then we can use a test that we know is effective.
We note that in Lucas1 test we have P = 1, Q - - 1 . Hence,
e = (A/ff) = (5/N)

= 1,

n = (Q/N)

= 1,

and
U,
L

(N-

0 (mod N)

l)/2

(3.11)

when N is a prime.
Define
Xi

E V2i

(mod N)

Yi

E U2.

(mod ff) (i > 1).

By (2.3) and (2.4), we have

Y

i+i

Y X

i i>

= 4 - 2

+1

(3.12)

(modi?)-

Also, by (2.2),
(3.13)

X? - 51? E 4 (mod N).

If we put Hn = 2A5r

+ 1 (r = 2 n ) , then 4 = 2 1

and

r-2
UA = Y
A
r -1

by ( 2 . 4 ) .

I! ^

(3.14)

(mod N)

i =0

T h u s , i f 21/ i s a p r i m e and N\UA9

we must h a v e
(3.15)

Xm E 0 (mod tf)
for

some

see

that

1 < m < P - 2

R E 25(2 + 5

i s a s o l u t i o n of

1988]

tti

V2 - 3 ) lOr/2Ym)lOr'2

H e n c e , by u s i n g

(mod N)

( 3 . 1 5 ) and ( 3 . 1 3 ) , we

(3.16)

(3.8).
303

A NOTE ON THE PRIMAUTY OF 62" + 1 AND 102* + 1

Put
and

^o
define
Sk+1

(mod ^)

r~i

(3.17)

E 2 5 | + 25S3k + 5Sk

Using (2.9) we see that Sk

have Sr

E 0 (mod 21/).

(mod N) .

(3.18)

= UA5k (mod 2V) .

If N is a prime, by (3.11) we must

If 5'0 ^ 0 (mod /I/), then, for some t < r, we have

S. 0 (mod 21/)

and

= 0 (mod 21/) .

By (3.18) we find that

+ 2 (mod 21/)

R = 5Sl

(3.19)

is a solution of (3.8). Also, if (2 5 t + 1 - l ) 2 > 21/, then, by the Corollary of

Theorem 2.4, we know that 21/ is a prime.
We are now able to assemble this information and use (3.12), (3.16)-(3.19),
(3.9) and (3.10) to develop the following test.
Primality Test (T3.2) for Hn = 102* + 1 (r = 2 n )
1.

Put X = 3, Y1
Yk

+1

= 1 and define
= YkXk

Xk + 1 E X
2.

(mod N)>

- 2 (mod /I/).

I f J m E 0 (mod 21/) f o r some m < r - 2 ,

i? E 2 5 ( 2 + 5 1 0 W 2 Y J 1 0 P " 2
and go d i r e c t l y t o s t e p 5 ;

3.

P u t S0

E Y r _1

(mod 21/) and

(mod 21/)

otherwise,
define

5 fe + 1 E 255^ + 255* + 5Sk

4.

put

(mod ff) .

Find some t < r such that

t+i = (mod

and 5

t ^ (mod

^)-

If no such t exists, then N is composite and

our test ends.

If

(2 5t + 1 - l ) 2 > 21/,
then N is a prime and our test ends.
(2 5t+1

If

- I ) 2 < N,

put
304

[Nov.

A NOTE ON THE PRIMALITY OF 62" + 1 AND 1 02* + 1

R E 5 2 + 2 (mod
5.

N).

Put
TQ E (57 + 25R)2((5N

+ 1)/11) 3 - 2 (mod /!/)

and define
Tk
6.

+1

E T^ - lOTl

35

5 0

^ "

^ +

^l

- 2 (mod N) .

71/ is a prime if and only if

^P_

- 357^_1 + 1 E 0 (mod tf).

REFERENCES
1.

R. D. Carmichael. "On the Numerical Factors of the Arithmetic Forms a n

B n ." Annals
of Math.
(2) 15 (1913-1914):30-70.

2.

D. H. Lehmer. "An Extended Theory of Lucas' Functions."

(2) 31 (1930):419-448.

3.

E. Lucas. "Sur la division de la circonference en parties egales." Academie des Sciences de Paris, Comptes vendues
85 (1877):136-139.

4.

E. Lucas. "Considerations nouvelles sur la theorie des nombres premiers

et sur la division geometrique de la circonference en parties egales."
Assoc. Francaise pour l'Avancement des Sciences, Comptes Rendues
des
Sessions,
1877, pp. 159-167.

5.

E. Lucas. "Theorie des functions numeriques simplement periodiques." Amer.

J. Math. 1 (1878):184-240, 289-321.

6.

E. Lucas.
e di stovia

"Sur la serie recurrent de Fermat."

dette
Scienze
Mathematiohe
e Fisiche
"Question 453."

Annals

of

Bulletino
di
Bibliografia
11 (1878):783-798.

7.

E. Lucas.

8.

P. Pepin. "Sur la formule 2 2 + 1 . "

tes rendues
85 (1877):329-331

9.

F. Proth. "Memoires presentes." Academie des Sciences de Paris,

vendues
87 (1878):374, see also p. 926.

Nouv.

Corresp.

Math.

Math.

5 (1879):137.

Academie des Sciences de Paris, CompComptes

10.

F. Proth. "Extrait d f une lettre de M. Proth."

(1878):210-211.

11.

H. Riesel.
Math. Comp.

12.

H. C. Williams. "An Algorithm for Determining Certain Large Primes." Congvessus

Numevantium
III,
Pvoo. of the Second Louisiana
Conf. on
Combinatovics,
Gvaph Theovy and Computing,
Utilitas Mathematica, Winnipeg, 1971,
pp. 533-556.

13.

H. C. Williams.

Covvesp.

Math.

"Some Factors of the Numbers Gn = 62" + 1 and Hn = 102" + 1."

23 (1969):413-415; Corrigenda, Math. Comp. 24 (1970):243.

"A Class of

Primality Tests for Trinomials Which Include

the Lucas-Lehmer Test." Pacific

14.

Nouv.

H.C. Williams.
A5n - 1 and Aln

J. Math. 98 (1982):477-494.

"Effective Primality Tests for Some Integers of the Forms

- 1." Math. Comp. (To appear.)
<>#<>

1988]

30 c