NOTE TO USERS This reproduction is the best copy available. UMI A SURVEY OF RESULTS ON GIUGA'S CONJECTURE AND RELATED CONJECTURES by Joseph R. H obart BSc., University of N orthern British Columbia, 2004 THESIS SU BM ITTED IN PARTIAL FU LFILLM EN T OF TH E R EQ U IREM EN TS FO R TH E D EG R E E OF MASTER OF SCIENCE in MATHEMATICAL, COMPUTER AND PHYSICAL SCIENCES (MATHEMATICS) THE UNIVERSITY OF NORTHERN BRITISH COLUMBIA July 2005 © Jo sep h R. H obart, 2005 1 ^ 1 Library and Archives Canada Bibliothèque et Archives Canada Published Heritage Branch Direction du Patrimoine de l'édition 395 Wellington Street Ottawa ON K1A0N4 Canada 395, rue Wellington Ottawa ON K1A0N4 Canada Your file Votre référence ISBN: 978-0-494-28392-9 Our file Notre référence ISBN: 978-0-494-28392-9 NOTICE: The author has granted a non­ exclusive license allowing Library and Archives Canada to reproduce, publish, archive, preserve, conserve, communicate to the public by telecommunication or on the Internet, loan, distribute and sell theses worldwide, for commercial or non­ commercial purposes, in microform, paper, electronic and/or any other formats. AVIS: L'auteur a accordé une licence non exclusive permettant à la Bibliothèque et Archives Canada de reproduire, publier, archiver, sauvegarder, conserver, transmettre au public par télécommunication ou par l'Internet, prêter, distribuer et vendre des thèses partout dans le monde, à des fins commerciales ou autres, sur support microforme, papier, électronique et/ou autres formats. The author retains copyright ownership and moral rights in this thesis. Neither the thesis nor substantial extracts from it may be printed or otherwise reproduced without the author's permission. L'auteur conserve la propriété du droit d'auteur et des droits moraux qui protège cette thèse. Ni la thèse ni des extraits substantiels de celle-ci ne doivent être imprimés ou autrement reproduits sans son autorisation. In compliance with the Canadian Privacy Act some supporting forms may have been removed from this thesis. Conformément à la loi canadienne sur la protection de la vie privée, quelques formulaires secondaires ont été enlevés de cette thèse. While these forms may be included in the document page count, their removal does not represent any loss of content from the thesis. Bien que ces formulaires aient inclus dans la pagination, il n'y aura aucun contenu manquant. Canada APPROVAL Name; Joseph hobait Degree: Master of Science Thesis Title: CONJECTURAL PRIME TESTS USING BERNOULLI NUMBERS AND THE RIEMANN ZETA FUNCTION Examining Committee: Chair^%Dr. Kenneth Prkachin, Professor Psychology Program University of Northern British Columbia Co-Supervisor: Dr. Lee Keener, Professor Mathematical, Computer, and Physical Sciences Program University of Northern British Columbia C o-S^d^isor: Dr. PaüT^^ôntgomery, Associate Professor Mamematical, Computer, and Physical Sciences Program University of Northern British Columbia Committee Member: Dr. Charles Brown, Associate Professor Mathematical, Computer, and Physical Sciences Program University of Northern British Columbia External Examiner: Dr. Karl Dilcher, Professor Department of Mathematics and Statistics Dalhousie University Date Approved: Rl Q .005 A b stra c t In 1950, G. Giuga developed a method of determining if a natural number n is prime [20]; n is prime n—1 ^ k~l = —1 (mod n). Giuga proved his conjecture up to 1000 digits. However, he was unable to extend his proof to all natural numbers. Thirty-five years later, in 1985, E. Bedocchi extended Giuga’s result to 1700 digits [6]. More recently, Borwein et al extended Giuga’s result to 13,800 digits [8]; however, they were unable to prove the conjecture. Since all previous attempts to prove the conjecture failed, researchers at­ tempted to reformulate Giuga’s conjecture. The first published attem pt was by Agoh in 1991. Agoh’s reformulation n is prime 4=^ nBn~i = —1 (mod n), became known as Agoh’s conjecture [2]. Concurrently, a 1994 thesis by Wong showed 8 variations on Giuga’s conjecture using different combinations of (p{n) in place of n —1 [57]. This thesis attempts to detail every known result on Giuga’s conjecture. By consolidating all published results along with some unpublished results we hope to aid those who wish to study Giuga’s conjecture in the future. 11 C o n ten ts A b s tra c t ii C o n te n ts iii L ist o f F ig u r e s v L ist o f T a b le s v A c k n o w le d g e m e n ts vi 1 I n tr o d u c ti o n 1 2 B a c k g ro u n d M a te r ia l 3 3 2.1 Num ber T h e o r y .................................................................................................. 3 2.2 A bstract A l g e b r a .............................................................................................. 6 2.3 Q uadratic R e s id u e s ........................................................................................... 9 2.4 A lg o rith m s................................................................................................. 12 2.5 Bernoulli N u m b e r s ........................................................................................... 15 2.6 Bernoulli Numbers Modulo p ......................................................................... 18 2.7 Euler Numbers .................................................................................................. 20 2.8 The Riemann Zeta F u n c tio n .......................................................................... 22 2.9 Prime T e s t s ........................................................................................................ 24 2.10 Factoring A lg o rith m s ........................................................................................ 28 2.11 Com puting Bn and ( ( n ) ................................................................................. 32 G iu g a ’s C o n je c tu r e 37 3.1 41 Giuga Numbers and Giuga S e q u e n ce s........................................................... 111 3.2 "The Eightfold W a y " ....................................................................................... 48 3.3 Normal Families, Co-Giuga, and Pseudo-Carmichael N umbers . 55 3.3.1 Normal Families of P r i m e s ................................................................ 56 3.3.2 Pseudo-Carm ichael N u m b e rs............................................................. 57 3.3.3 Co-Ciuga N u m b e r s .............................................................................. 59 C om putational R e s u l t s ................................................................................... 61 3.4.1 C o u n te re x a m p le s ................................................................................. 61 3.4.2 C iuga Sequences ................................................................................. 65 A goh’s Conjecture and Related R e s u lt s ..................................................... 69 3.5.1 ................................................................................. 72 Open P r o b le m s ................................................................................................ 76 3.4 3.5 3.6 4 C iuga Q uotients C o n c lu s io n . . 79 A p p e n d ix 1: G iu g a ’s C o n je c tu r e R e s u lts 81 A p p e n d ix 2: M o d e r n P r im a l ity T e s ts 86 A p p e n d ix 3: N u m b e r T h e o r e tic C o n g ru e n c e s 95 A p p e n d ix 4: A lg o rith m s 97 N o ta tio n a l C o n v e n tio n s 99 R e fe re n c e s 100 IV List o f F igu res 1 Contour for R iem ann’s Zeta function [53]..................................................... 24 List o f T ables 1 The First 15 Bernoulli N u m b e rs .................................................................... 16 2 Inequalities Related to Bernoulli Numbers [46] . ................................... 17 3 Congruences Involving Bernoulli N u m b e r s ................................................ 19 4 The First 13 Euler N u m b e r s ........................................................................... 21 5 Values of the Riem ann Zeta f u n c t i o n .......................................................... 23 6 Relations Between the Riem ann Zeta Function and Bernoulli Numbers [1)............................................................................................................................. 25 7 Number of Giuga S e q u e n c e s ........................................................................... 43 8 Proper Giuga S e q u e n c e s ................................................................................. 44 9 The “Eightfold W ay” ........................................................................................ 55 10 Conditions for Yhk&i ^ ( m o d n) [57].................................................... 62 11 G iuga’s Conjecture R e s u lts .............................................................................. 81 12 M odern Prim e Tests 86 13 Modern Pseudo-prime T e s t s ........................................................................... 89 14 Prime Num ber C o n jectu res.............................................................................. 89 15 Modern Sieving M e th o d s ................................................................................. 90 16 M odern Factoring T e c h n iq u e s ....................................................................... 92 17 Number Theoretic C o n g ru e n c e s .................................................................... 95 18 N otational C onven tio n s..................................................................................... 99 . ............................................... A ck n o w led g em en ts First, I would like to thank Dr. Lee Keener for taking the tim e to teach so many extra courses on top of his paid workload. If not for the course MATH 499 - Special Topics in Number Theory, I would never have had an opportunity to first learn about G iuga’s Conjecture. I would also like to th an k him for his infinite patience while I changed my m ind (several times) not only on my thesis topic b u t my m athem atical direction in general. Next, but certainly by no means less valuable, were the comments and corrections given by my supervisory com m ittee of Dr. Patrick M ontgomery and Dr. Keener. The tim e th a t they spent teaching me to refine my ideas and m ethodology (and my writing) was by far the most im portant lesson I learned from UNBC. I would also like to acknowledge and thank my com m ittee members. Dr. Charles G rant Brown and Dr. Karl Dilcher for their assistance com pleting my thesis defense. I would also like to than k my friends, family, instructors (especially Edw ard Dobrowolski) and fellow graduate students. W ithout their constant support and coerc­ ing, I might still be w riting this paper. VI 1 In tro d u ctio n Number theory is one of the fastest growing areas of m athem atics. Useful applications of num ber theory in other areas of m athem atics are becoming increasingly numerous. For instance, results in cryptography and th e theory of elliptic curves are often first seen in num ber theory. For years, however, m athem aticians viewed num ber theory, not as a tool for solving problems on a larger stage, bu t as an example of m athem atical beauty. W hen asked w hat practical applications num ber theory could provide to everyday people, num ber theorists were often heard to answer, “None.” There are still areas of num ber theory which seem to be fruitless from a practical point of view. Bernoulli numbers, Euler polynomials, quadratic residues and m any other aspects of classical num ber theory might fit this mold. This is not the case. It will be shown th a t Bernoulli num bers (and therefore Euler polynomials) can be used as prime testing mechanisms, while it is already known th a t quadratic residues can be used to factor and are often the underlying theory in different cryptographic applications. This thesis extends w hat is known w ith respect to G iuga’s conjecture. n n is prim e = —f (mod n). k=l The thesis is a complete compilation of published results on G iuga’s conjecture while also discussing many of the topics underlining the conjecture and possible counterex­ amples. The thesis begins w ith a brief review of basic num ber theory, classical num ber theory, algebra, numerical analysis, prim e testing and factoring. This chapter (Ghapter 2) serves simply as a reference for w hat is to follow in the rem aining chapters. M aterial found in this chapter can also be found in [1], [19], [22], [25], [35], [36], [37], 1 [39] and [41]. For m aterial on prim e testing and factoring, th e reader is urged to read [4], [5], [10], [12], [17], [24], [25], [27], [30], [34], [44] and [56]. The third chapter looks at the known results on G iuga’s conjecture. Most of the m aterial can be found in [2], [6], [8], [20], [23], [36], [37] and [57]. Some new results will also appear. Num ber theory is a beautiful branch of m athem atics and indeed of science as a whole. Its beauty is often overshadowed by its ever increasing applicability to real life problems. This thesis, despite my best efforts, continues this overshadowing. It is my hope th a t eventually G iuga’s conjecture is proved and will become the basis for a new prim e test. 2 B ack grou n d M ateria l “M athem atics is the language with which God wrote the universe. ” - Galileo Galilei - This chapter serves only as a reference for w hat is to follow in this thesis. We begin w ith some basic notation. Define the sets N, Z, Q, R and C in th e usual way. To avoid confusion, please note th a t N = U {0}. Also, Define P to be th e set of all prime numbers. 2.1 N um b er T heory All results in this section are standard and can be found in any num ber theory text, for example [38] and [22]. One of th e m ost basic concepts in num ber theory is th a t of divisibility and divisors. D e fin itio n 2.1 For a G Z"*" and n G'L, we say that a divides n, w ritten a\n, i f there exists b G Z such that ab = n. I f no such b exists, we say that a fn . T h e o re m 2.1 ( E u c lid ’s L e m m a ) I fp is a prime, andp\ab, th en p \a orp\b or both. D e fin itio n 2.2 We say that o’" exactly divides n if a'^\n but, fn . We denote o’" eæoc% dmWes n 6?/ o’"]]?!. D e fin itio n 2.3 A n integer n is said to be b-smooth if n has no prim e factors larger than b. D e fin itio n 2.4 We say that a is congruent to b modulo n, denoted by a= b (mod n). i f n \ { a ~ b ) . I f a = b (mod n) , th e n a a n d b are said to be in the sa m e residue class modulo n. The following is a consequence of considering residue classes m odulo n [8]. T h e o re m 2.2 ^ 1-1 ( m o d p) i f {p ~ l ) \ { n ~ I) ( 1) k=l 0 (mod p) otherwise. D e fin itio n 2.5 For a,b E N, we define the greatest common divisor o f a and b, denoted (a, b) as the largest positive integer n such that n |a and n\b. D e fin itio n 2.6 The least common multiple o f two positive integers, a and b, is the smallest n E 'EF such that a\n and b\n. We denote the least common multiple by 6 ). The following theorem relates the greatest common divisor to the least common multiple [38]. L e m m a 2.1 L e t a , b E N . Then, (a, b) ■lcm{a, b) = ab. One of the key observations about the greatest common divisor of a and b isth a t any linear combination of a and b can be expressed as a m ultiple of (a, b). T h e o re m 2.3 Suppose that a E i F , b E Z , and (a, b) — n, then there exists integers X and y such that ax + by = n. That is, there is a linear combination o f a and b equal to (a,b). Generally, in analytic num ber theory, we are concerned about integers. Thus, for equations, we generally only pay atten tio n to integral solutions (solutions in integers). This makes the following observation very im portant [38]. C o ro lla ry 2.1 Given a, b, c G Z , the Diophantine equation ax + by = c has integral solutions iff {a, b)\c. We can go further and state the following theorem [38]. T h e o re m 2.4 Take a, b, c 6 Z. Set h = {a,b). Since a — u h and b — vh, then the equation ax -\-by = c has no integral solutions unless h\c. Moreover, the general integral solution o f the equation is x = Xq — vk, y = yo + uk, k G Z where (xq, yo) is a particular solution. A nother well-known and fundam ental theorem of num ber theory is due to Ferm at. The proof of F erm at’s Little Theorem can be found in any introductory num ber theory textbook, for example Koblitz [25]. T h e o re m 2.5 ( F e r m a t’s L ittle T h e o re m ) Let a e Z~^ and p G F. I f p fa , then qP-1 = I (mod p). The following theorem can be found in Wong [57]. It relates powers m odulo prim e powers. L e m m a 2.2 Let a g Z'^ and p g F. For every z G N, if a = 1 (mod p) then aP' = 1 (mod We conclude w ith the definition of Euler’s totient function (also called th e phi function). D e fin itio n 2 .7 Let n e Z'^. Then (p{n) is the number o f integers k, with 1 < k < n such that (n, k) — 1. Basic properties of the to tien t function can be found in any introductory num ber theory book, for example Bressoud and Wagon [11]. Though this is only a brief introduction, the bulk of w hat is used later has been covered already. Any additional results used later will be stated as required. 2.2 A b s tr a c t A lg eb ra There are many good abstract algebra textbooks. Among them , G allian’s book [19] is the main reference for the following results. D e fin itio n 2.8 A group G is defined to be a set (finite or infinite) along binary operation ^ with a on G which assigns to each pair {a. b) o f elements in G an element denoted by a ^ b , with following properties: • closure: I f a,b G G then a ^ b G G, • a sso cia tivity: I f a , b , c G G th e n (a 0 è) 0 c = a 0 ( 6 0 c), • id en tity: There is a unique element I G G such that a 0 / = a = / 0 a , • in verse: For every a G G there is a urnque a~^ such th a t a 0 a “ ^ = / = a ' a. If for all a, 6 e G, a 0 6 = 6 0 a, the group is said to be com m utative or abelian. E x a m p le 1 It is not difficult to show that the following sets under the indicated operation form groups: 6 • z under + • Q — {0} under x • G L (n,K ) under m atrix multiplication (for invertible matrices only) • the set o f points on + a x + b over Q under point addition • integer multiplication modulo p where p is prime. • Zm under the operation + modulo m {Zm = ( 0 , 1 , . . . m — 1}) • under the operation x modulo m (Z ^ = {a: e Zm\{‘X ,m ) = 1}). D e fin itio n 2.9 Z{G) is the subset o f elements o f G that commute with every element o /G . To be able to talk about th e cardinality of a set in a group, we define th e order of a group, G. D e fin itio n 2.10 The order o f a finite group G, denoted |G| is the number o f elements in G. In the setting of a group, we often wish to do standard arithm etic. The structure often plays a role in this. To work w ith inverses, for instance, we take advantage of the following definition. D e fin itio n 2.11 Suppose G is a group and a E G. where a 0 6 = / G G. We can now do m odular arithm etic w ith fractions: We define ^ = b E G E x a m p le 2 Evaluate 5/4 (mod 7). Multiplication modulo 7 is a group. Further 5 and 1/4 = 4~^ are both elements o f G. Now, since 4~^ = 2 (mod 7), we simply compute: (5 )(l/4 ) = (5)(2) = 10 = 3 (mod 7). Among the most im portant types of groups is the set of cyclic groups. Cyclic groups play a special role in different aspects of num ber theory and cryptography. For examples see Koblitz [25] or Gallian [19]. D e fin itio n 2.12 A finite group G which can he form ed by computing powers o f an element, g E G is called cyclic. In this case, G = {e, g, g"^, g ^ , . . . ,g^~^}. The element g is called the generator o f the group. This group is often denoted by (g). A nother im portant and richer algebraic stru ctu re th a t we will make use of is called a field. D e fin itio n 2.13 Let ¥ be a set (with at least 2 elements) with operations + and x defined on F satisfying the following three properties: 1. ¥ is an abelian group with respect to + . 2. ¥ — {0} (0 denotes the additive identity) is an abelian group with respect to x . 3. For a,b, c E F, a{b + c) = ab + ac and {a + b)c = ac + be. Then, (F, + , x) is said to be a field. E x a m p le 3 • Q, M and C are all fields. • Tjp is a field under modular addition and multiplication if p is prime. e F 2" (the set o f polynomials with coefficients in {0, l}y) with modular addition and multiplication on polynomials is a field. For example, Fgs = ^a j X^ + + a^x^ + • • • + a \ X + ool^i G Z g } • Note also that addition in F 2" is bitwise X O R and inverses can he computed using the extended Euclidean algorithm (see section 2. 4 ). 2.3 Q u a d ra tic R e sid u e s Q uadratic residues are often the basis for the m athem atics underlying cryptographic concepts, for instance the Rabin W illiams cryptosystem , the Legendre cryptosystem , and the Legendre factorization m ethod [25]. We include this section to provide a basis when discussing the theory of factoring and prim e testing. Only results which are truly im portant for w hat follows are included here. Q uadratic residue results such as definitions and basic results can be found in [22] or [38]. D e fin itio n 2.14 Let m be any integer. We say that a is a quadratic residue modulo m if (a, m) = 1 and there exists some x such that x'^ = a (mod m ). We denote the set of quadratic residues modulo m as QRmD e fin itio n 2.15 Let m be any integer, and suppose that ( a, m) = 1and that x"^ ^ a (mod m ), fo r any x. Then, we say that a is a quadratic non-residue modulo m . We denote the set of quadratic non-residues modulo m as Q N ^ - Notice, = U E x a m p le 4 Select m = 7. Then Q R j = {1,2,4} and Q N j = {3,5,6}. Z} = QRq U QNy = {1, 2, 4} U {3, 5, 6} = {1, 2, 3, 4, 5, 6}. 9 Clearly, We shall see in subsequent chapters how quadratic residues can be used in prime tests and pseudo-prime tests. For instance, Euler’s criterion provides an example of how one m ight implement quadratic residues to determ ine prim ality [41]. T h e o re m 2.6 ( E u le r ’s C r ite r io n ) a G QRp if and only if D e fin itio n 2.16 Let p be prime. The Legendre symbol 0 ifp\a 1 i f a e QRp ■ —1 i f a E QNp = 1 (mod p). is defined by a = P, It follows from E uler’s criterion (Theorem 2.6) th at, = ( - ) (mod p). T h e o re m 2.7 The following properties hold fo r the Legendre symbol: (p ) = (p ) 6. (-i)W ^ I j (Law o f Quadratic Reciprocity). 10 E x a m p le 5 Evaluate ( ^ ) We could calculate 319 2 (mod 1031); however, this is computationally more difficult. Quadratic reciprocity yields a m uch simpler method. /319\ / I I 29 V1031j ~ \ 1031 fJL] ( ^ ) Property 2 V 1031/ V1 0 3 1 ; (“ ) ( Ï ) 8 \ /1 6 ' Property 6 Property 3 1 1 / 1 29 2 Property 5 and 2 n I. Property 4 Due to the restrictive n atu re of the Legendre symbol (i.e. the requirem ent of p to be prime), we introduce a more general version of the Legendre symbol called the Jacobi symbol D e fin itio n 2 .1 7 Let Q = Y\_qT Jacobi symbol an odd integer. For any positive integer P , the is defined by where ( —) is the Legendre symbol. T h e o re m 2.8 The following properties hold fo r the Jacobi symbol: 2 11 ( i j = (-!)■ 5. (2) = ( - l ) ^ ^ ( £ ) , We now tu rn our attentio n to some of the fundam ental algorithm s in com puta­ tional num ber theory. 2.4 A lg o r ith m s Recall from Section 2.1 (Theorem 2.3 and its corollary) th a t the linear D iophantine equation ax + by = I has no solution unless (a,b) — 1. The following algorithm s allow us to solve for x and y and determ ine if (a, 6) = 1. They can be found in more detail in Bressoud and Wagon [11]. A lg o rith m 2.1 (E u c lid e a n A lg o rith m ) Let [xj (the floor function) be the largest integer < x. Given a,b E X and b > 0, a= bqo + ro % = [a/b\ 0 < ro < b b= roQi + r i q i= [6/roJ 0 < rj < ro ro = riçg + rg % = |_ro/rij 0 < r2 < ri rn_29n-i + r» -! r^ - i = (a, 6) rn_3 = r » —2 ~ n —iQn T r „ r^ = 0 Note that the Euclidean Algorithm determines whether on not (a,b) = 1. Further, n < 5 1 o g io (m in { a , 6 }) = O (lo g io (m in { o , 6 } )). 12 A lg o rith m 2.2 (E x te n d e d E u c lid e a n A lg o rith m ) Let = 0, = 1, J5_2 — 1, S _ i = 0 and define Afe = Q k^k-l + Ak-2 Bk = QkBk-i + Bk-2 fo r A: = 0 , 1 , . . . and % as above. Then, a solution to the equation a x -{-by = 1 with n as in the Euclidean Algorithm, is given by X= and y = { - I f i A n - i - A nother algorithm which is useful iu com putational num ber theory is known as H orner’s Algorithm. H orner’s algorithm (sometimes called the power algorithm ) eval­ uates a" (mod m) given a , n , m . A lg o rith m 2.3 ( H o r n e r ’s M e th o d ) Given a , n , m , let n = 6q2^ -f bi2^^^ + bk-\2 -f bk be the binary expansion o f n (bo = 1, 6, G { 0 ,1}). Note that k = (logg n j . Notice that we can evaluate n in the following way: 2 (- ■• (2(26o + bi) + 62) • • • + fcfc-i) + bk- Now, H orner’s method works as follows: put ■So = bo Sj+i = 2si -j- bi i = 0,1,... k — 1 to pmdüce St = Now, define r, = a*’ (mod m ) fo r al i i = 0 , 1 , k (where r% is the least positive residue o f modulo m ). Then Tk = = a” 13 (mod m ). Further, we can compute each iteratively as follows: n+i = (mod m) [ r? (mod m ) i f bj+i = 0 r fa (mod m ) i f bi+i = 1 This algorithm perm its computation o f oF in 0 (log(2n)) operations and uses no operands larger than (due to the modular arithmetic at every step). Given a system of congruences N = ai (mod pi) N = Ü2 (mod P2) = (m o d p t), one might wish to find a solution to this system in integers. One way to do this is w ith a theorem known as th e Chinese Rem ainder Theorem [39]. A lg o rith m 2.4 (C h in e s e R e m a in d e r T h e o re m ) Let { p i , P 2 , ■■- Pk} be distinct primes. Then, the following system o f equations: N = ai (mod Pi ) N = Ü2 (mod P 2 ) N = Ok (mod Pk) has a unique solution fo r N modulo fŸi=\Pi- 14 TAe T/ieorem ^ a f z f Z Ao/ck ^ (Ae Pi k ore not p n m e p m - mded t/io t/o r oZf z ond,;, (p:,p,) = 1. Met/iodg o/reconennp soZnkon to t/ie gpatem e z k t /i9^. 2.5 B e rn o u lli N u m b e r s Bernoulli num bers were first studied by Jakob Bernoulli (1654-1705) in the late 1600’s and early 1700’s while studying sums of powers of consecutive integers. Results regarding Bernoulli numbers were first published in 1713 in th e posthum ous work “Ars C onjectandi” . Currently, Bernoulli num bers are being studied in m any different areas of m ath ­ ematics such as number theory (including, b u t not lim ited to, distribution of primes and F erm at’s last theorem ), calculus of finite differences, combinatorics, Euler and Stirling sequences, Pascal’s triangle, and differential topology. The most modern definition of Bernoulli num bers is obtained through the gener­ ating function 4-pXt — f'^ = ^ B „ (x )— |f| < 27t. (2) n=0 This definition defines the X = 0 yields the Bernoulli polynomial. Evaluating this polynomial at Bernoulli number. This function and other results can be found in Abramowitz and Stegun’s book The H andbook of M athem atical Functions [1]. Perhaps a more convenient definition of Bernoulli num bers is obtained by the following recursive definition [1]: D e fin itio n 2.18 Take B q = 1. Then the Bernoulli number is: 1=0 ' 15 ^ (3) It is not hard to show th a t Definition 2.18 follows from th e generating function in equation (2). We will take equation (3) as the definition of a Bernoulli num ber instead of the more general definition given by equation (2). Bq ~ 1 B i = -1 2 B2 = 1 6 Bs = 0 Be = 0 B 7 = 0 Bg = 0 B 4 = B e = Bg = -1 30 1 42 -1 30 5 B io = 66 B ii = 0 B i2 = -6 9 1 2730 B i3 = 0 7 B is = 0 B i4 = 6 Table 1; The F irst 15 Bernoulli Numbers Each Bernoulli num ber w ith an odd index greater th an 1 is zero. This is an easy consequence of Definition 2.18 and the sym m etry given by the Binomial Theorem [1]. Further, one can show the following generalization of Definition 2.18 [1]. L e m m a 2.3 + h) = ^ k=o The following theorem is due to R aabe [46]. It plays a significant role in the study of Bernoulli polynomials. T h e o re m 2.9 (R a a b e ) Let m > 0 and n > 0 be integers. Then m —1 r~0 X -\-r = m 16 "Bn(a;). The next lemma [46], outlines th e relationship between Bernoulli numbers and sums of powers of consecutive integers. L e m m a 2.4 E * ”= fc=i n + 1 y m ,n e Table 2 provides some well known bounds on the m agnitude of Bernoulli numbers. |B2n| > \B2n{^)\ 1-2-2" > ( 26:"^ 1 ^ / (27t)2" 1-21-2» -^ \ > 0 1tn+lR ^ ^ (27t)2» n = 1,2,.. 0 < z < 1 n — 1,2,.. 0 < X< 1 n = 1, 2 , . . Table 2: Inequalities Related to Bernoulli Num bers [46] The structure of Bernoulli numbers rem ains largely unknown. There are m ethods of calculating Bernoulli num bers w ithout using th e generating function or the recur­ sive definition. These m ethods often require approxim ating the Zeta function and calculating the num erator of the Bernoulli num ber based on a known denom inator. Results involving approxim ating the Zeta function will be discussed in Section 2.11. One result regarding the structure of Bernoulli num ber denom inators (where each is assumed to be in lowest term s), denoted denom {Bn), is a result of von S tau d t and Clausen [35]. T h e o re m 2.10 (v o n S ta u d t - C la u s e n T h e o re m ) Let B^n be the Bernoulli number. Then, p — 1 | 2n, if and only if p | deuom {B 2n )■ C o ro lla ry 2.2 Bg» = Vlg» - E p - i | 2n p' E Z. Even though von S taudt and Clausen’s theorem gives no inform ation about the num erator of Bernoulli numbers, the denom inators are determ ined simply through finding integers p such th a t (p — l)|2 n . 17 2.6 B e r n o u lli N u m b e r s M o d u lo p Among the most im portant properties of Bernoulli numbers is th e so-called K um m er congruence. K um m er’s 1850 result is one of fundam ental im portance to this thesis and to num ber theory as a whole. K um m er’s congruence relates Bernoulli num bers whose indices are in the same residue class modulo p — 1, m odulo a prime, p [35]. T h e o re m 2.11 ( K u m m e r ’s C o n g ru e n c e ) Let A: G N, p G P and 6 ^ 0 (mod p — 1). Then the following equivalence holds B k ( p —l ) + b Bfj k{p — 1) + 6 — b (mod p). Much work has been done to generalize K um m er’s result from a modulo p result to a modulo p^ result. We list some known results in Table 3. For A; G Bk{p-i)+b and N, K um m er’s congruence implies a first order relationship between of the form Bk{p-i)+b = Bb + m k (mod p) whenever (h(p—1)4-6)"^ exists m odulo p. To see this, m ultiply b o th sides of K um m er’s congruence by A:(p — 1) -t- 6 and observe the following congruences: Bk{p-i)+b = {k(p — 1) + b)— (mod p) (4) Bb (mod p). (5) = Bb + m k (mod p), (6) = Bb+ — ^ Now, suppose th at for some constant m E Z, and 6 ^ 0 (mod p — 1). After subtracting Bb from both sides, equation 6 implies th a t ^ B b — ^Bb = m k 18 (mod p). (7) R e fe r e n c e C o n g ru en ce - t (* ^k(p-l)+b — k ( p - l) + b — Kummer [35] (mod P) V fc e N Sun [42] p " - ' ) f (mod p^) 1)(1 Sun [42] 2)friV t + ( b ' ) ( l p'’- ' ) ? (m odp*) Sun [42] S .-3 = ÿ ( E ï i 1) ^ Sun [42] (mod P^) (p - 1)! ^ For b > n and 6 ^ 0 (mod p — I) ^ Ireland and Rosen [22] E L o G ) ( - l ) ‘ ê b m = 0 (mod P") d \ d »l _ X(i)Bk^i (mod p) /I -^fc(p-i)+fc — / 1\ n - l - r /fc'i ^ 2 1)+ 6 Z_vr=0 \ / \n—l —rJ\r) V Sun [42] f c ( p — (1 For k e { 1 , 2 , . . . ( , p (m odp'') Sun [42] 4 } , — k { k - i) p ^ j - k p 2 ("j^od p ^ ) [ ^ (2p-2-k E C E 5 ! = = = For k E Sun [42] C h < - ' i k is odd if ^ IG odd Sun [42] Sun [42] - 3Bp+i)p (mod p^) - ( 2 - pBp_i)p §p^ (mod p^) P ^ 2p-2 3pBp_i 3(p 1) (mod p^) ( i - - + Sun [42] Sun [42] - then, ( ^‘ jpSy_i_(. (mod p^) p i l if P < p 1 E [ — p B p _ i For p > 3, then For p > 3, then (p — + 2 ( p — (mod 1 ) p ^ ) if k = p — = ^ pBk- i (mod p^) 1)! = pBp^i p (mod p^) — Table 3: Congruences Involving Bernoulli Numbers 19 1 Sun [43] Beeger [7] Dividing k from both sides, and assuming \B b is invertible modulo p (i.e. the denom­ inator has a m ultiplicative inverse in Zp), then —~ ~ = m (mod p). (8) Therefore, the linear relationship between Bk(p-i)+b and Bb is Bk(p-i)+b ^ Bb — — (mod p) w ith —^ constant. Higher order relationships may be derived modulo p"; however, relationships of this form become increasingly complex as a increases. 2.7 E u ler N u m b e r s Closely related to Bernoulli num bers are th e Euler numbers. All results in this section can be found in The Handbook of M athem atical Functions [1]. Euler polynomials are generated by the following function, similar to the generating function for Bernoulli polynomials: e* -f 1 ^E n {x)— nl n =0 \t\<7T. (9) En{x) is known as the Euler polynomial. The num erator of the value of polynom ial after being evaluated at a; = | , yields the value of the Euler num ber, En- In fact, the denom inator of the evaluated polynom ial is 2" so, - 2"E»(l/2). As with Bernoulli numbers, there is a recursive formula which may be used to describe Euler polynomials. L e m m a 2.5 The Euler polynomial satisfies E ^ (z + h) = ^ fc=0 ^ ' n e N, h E 20 i E R. (10) Clearly, x + h ~ ^ is a- simple point at which to evaluate asa: = - l / 2 , will yield a simple solution. It is also im portant to note th a t £ ’« (0) = —£»(!)'. Hence, Euler num bers can be given as a function of the constant term of Euler polynomials with smaller indices. The definition given in equation (9) is equivalent to th a t in Lemma 2.5. It can also be shown th a t any Euler num ber w ith odd index is zero. Further, one can show th a t the signs of the even indexed Euler num bers alternate as depicted in Table 4. Eq= 1 ^1 = 0 £2 = -1 £3 = 0 £4 = 5 £5 = 0 E& = -6 1 £7 = 0 £g = 1385 £9 = 0 = -50521 £11 = 0 E i2 = 2702765 ^13 = 0 £10 Table 4: The First 13 Euler Numbers The next lemma is a useful characterization of Euler polynomials. L e m m a 2.6 n —k En{x) — y ] ( 11) k=0 Much like Bernoulli polynomials, Euler polynomials can be characterized in term s of sums of powers of integers. L e m m a 2.7 Eji{rn + 1) + (—1)”^£„(0) k=l 21 m, 71 e N ( 12 ) We conclude this section w ith some im portant relationships between Bernoulli numbers and Euler polynomials. L e m m a 2.8 (14) B„(0) = 2.8 = - 2 (n + l) - '( 2 ”+‘ - (15) T h e R ie m a n n Z eta F u n ctio n The Riemann zeta function is among the most im portant special functions in m ath ­ ematics and physics. The Zeta function can be found in the study of prime num ber theory, lattice theory, probability, distribution of primes, complex contour integra­ tion, and in areas of physics such as entropy, and statistical mechanics. There are many hypothesized properties of th e Zeta function th a t rem ain unproved. The most notable of these results is the so called Riem ann Hypothesis [53]. We will be inter­ ested in the characterization of the Zeta function as it relates to sums of reciprocal powers. The Zeta function is defined in the following way [1]: D e fin itio n 2.19 When 7i[n] > 1 (where TZ[n] is the real part of n), R iem ann’s Zeta function is defined as follows: oo k=i 22 This definition is equivalent to saying th a t —n \ —l cw = peP where again TZ[n] > 1. The Zeta function can also be defined by the following sum [53]: 1 s= 0 where 7„ = (ln(A;))" I * ^ k lim <{ V m— . k=l (ln(m )) n + l n + 1 w ith % (n) > 0. is called the Stieltjes constant. As defined above, Ç{n) is a complex num ber w ith TZ[n] > 1. The Zeta function, however, has a unique analytic continuation to all of the complex plane w ith the exception of a simple pole at n = 1. C(o) = ((!) = 1 2 undefined C(2) = 1.202 ((4 ) = C ( - i) = ... r .. 2 ((-2 ) - 0 C (-3) = 1 120 C (-4) - 0 1 C (-5) = 1.036 ((6) = 1.008 252 C (-6) = 0 ((-7 ) = 240 C (-8) = 0 1 Table 5: Values of the Riem ann Zeta function For n even and negative, Ç{n) = 0. These roots are referred to, in the literature, as trivial zeros. All non-trivial zeros occur for n = cr + R when 0 < a < 1. The 23 Riemann hypothesis asserts th a t all non trivial zeros have the form n = | + it [53]. For n even and positive, ((n ) = for some integers k and I as seen in Table 5. The following result shows a connection between the Zeta function and contour integrals. T h e o re m 2.12 2 ?ri 7 1 where 7 is the contour in figure 1, and F is the gamma function defined by: poc F f o l = I t^~ ^p~ ^d.t init.h V .( 7 > f). J k Figure 1: Contour for R iem ann’s Zeta function [53]. Table 6 highlights some relations between the Zeta function and Bernoulli num ­ bers. 2.9 P r im e T ests Prim ality proving is a rapidly changing area of num ber theory. W ith this in mind, I have made little effort to provide a complete historical overview, nor has much effort been made to provide more th a n a couple of m odern prime tests (and not in much detail). This section should provide no more th an a starting point for a more detailed study. 24 C o n d itio n R e la tio n n %1 ((2n + 1) = • 5 6% + 7Z(n) > —2s - G%) i r C(n) = j t r + 1 + E L . i f fo cot(7ri)dx C (l-2 n ) = - f f n 6 Z+ ((2n) — n 6 %+ |2 ?2nl Table 6: Relations Between the Riem ann Zeta Function and Bernoulli N umbers [1], D e fin itio n 2.20 A prime number is a positive integerp > 1, with exactly two positive divisors, 1 and itself. A positive integer, larger than 1, which is not prime is said to be composite. A prime test is any test which certifies a number to be prime or composite. There are two main types of prime tests: determ inistic and probabilistic. De­ term inistic tests determ ine prim ality w ith 100% certainty while probabilistic tests potentially identify composite numbers as prim e (albeit w ith small probability). Historically, the most prim itive determ inistic prime test is the m ethod of trial division. This m ethod involves dividing n by each integer less th an ^/n. W ilson’s theorem yields another determ inistic prim ality test: n is prim e <=> (n — 1)! = —1 (mod n). Both W ilson’s theorem and trial division are far too slow to be of practical value. 25 The most commonly used probabilistic prime test is given by F erm at’s L ittle Theorem (Theorem 2.5) n is prim e = » (mod n) V 1 < a < n. = 1 The converse of this theorem , given a random ly chosen a w ith (a, n) = 1, a-n-i = I (mod n), implies th a t n is prime w ith probability 1 — where k is the num ber of trials. Of course Carmichael num bers (which will be discussed in detail later) always satisfy this equation (and Carmichael num bers are always composite). Because of Carmichael numbers, F erm at’s Little Theorem is only a probabilistic test. In August 2002, three Indian m athem aticians Agrawal, Kayal, and Saxena subm it­ ted the first determ inistic polynom ial-tim e algorithm to determ ine prim ality. Their algorithm relies on the following lemma [4]. L e m m a 2.9 Suppose that (a,p) = 1. Then p is prime i f and only if (x — o)^ = (x^ — 1) (mod p). The AKS test (as it is known) is both unconditional and non-random ized. T h a t is, it does not rely on conjectural results (i.e. the Riemann Hypothesis) or on choosing numbers carefully or randomly. The algorithm runs as follows: A lg o rith m 2.5 (A K S A lg o rith m ) Input n > 1. 1. if (n is of the form b > 1) output COMPOSITE; r = .g; .9. w/tz/e (r < 4- if ( (n, r) { I ) output COMPOSITE; 26 ,5. ^ ^ r is pnm e 6. let q be the largest prime factor of r — 1; 7, if ( q > 4 y /r lo g n ) and (n « (r —1) 9. ^ 1 (m od r)) r f - r + 1; JO. } 11. 12. fo r a = \ to 2-^7 log tt, 13. i f ( (yX — a )” ^ (x” — a) (mod x'^ — l , n ) ) output COMPOSITE; 14 . output PRIME; The runtim e of the algorithm in the original paper was 0 { { ln n)^^). C urrent im plem entations run in 0 {{ ln n)®) for general integers [32]. The elliptic curve prim e proving m ethod was m otivated by new results in the theory of elliptic curves. Since entire courses are devoted to the study of elliptic curves, a simple framework will be provided here for the reader to begin individual study. T h e o re m 2.13 Let N be an integer co-prime to 6, E an elliptic curveover Zjv, together with a point P on E and m and s two integers with s\m. For each prime dzvM or g : % o /g , : -2:9), c /o g g 0 / (æ,2/,z). y lg g ^ m e f/n z f m P = O e is the point at infinity and gcd(zg, A^) = 1 for every q. Then, i f p is a prime divisor of N , one has # E (Z p ) = 0 (mod s), where # T (Z y ) represents the number of integral points on the elliptic curve, E. This result provides a basis for the Goldwasser-Kilian algorithm. 27 A lg o rith m 2.6 (G o ld w a s s e r-K ilia n ) Input n > 1. 1. Choose an elliptic curve E over Z„ fo r which the number o f points m. satisfies m = 2q where q is a probable prime; 2. I f {E,m.) satisfies the conditions o f Theorem 2.13 with s = m , then n is prime, otherwise it is composite; 3. The primality of q is proved in the same way; 4- Output results. The Goldwasser-Kilian algorithm proves th e prim ality of n in expected tim e of 0((logn)^°+ ‘^), where c is a constant independent of n. Improvements have been made to this algorithm; however, w ithout sufficient background in elliptic curves a statem ent of the algorithm seems rath er fruitless The improved algorithm (known as E C PP) has a run tim e of roughly 0((logn)®+^) for some £ > 0. 2.10 F a cto rin g A lg o r ith m s Tests which certify th a t a num ber, n, is composite often give no indication of the divisors of n. A factoring algorithm yields a factor (prime or not) or a series of factors of n. A good reference for further study on factoring algorithm s and a book in which most recent results are stated is Koblitz [25]. Historically, the m ethod of direct search factorization (essentially trial division) was the first and arguably the least sophisticated m ethod of factoring. Requiring at most ^/n trial divisions, direct search factoring is essentially only a prelim inary tool used before more sophisticated algorithms. Modern factoring algorithm s take advantage of many different branches of num ber theory. For example, the elliptic curve factoring algorithm takes advantage of the theory of elliptic curves, the quadratic sieve takes advantage of Dixon’s algorithm 28 and factoring differences of squares, and the num ber field sieve uses similar ideas to the quadratic sieve while taking advantage of polynomials which are not quadratic. The elliptic curve factoring m ethod starts w ith selecting an elliptic curve E in “short W eierstrass form” (th at is, a curve of th e form ax h (16) with 4a^ + 276^ ^ 0) over the field Z*. Notice th a t if p is a prim e divisor of n, and a = h (mod n), then necessarily a = b (mod p). This property always holds for points on elliptic curves w ith the exception of division (i.e. if o or 6 is a fraction which is invertible modulo p, it need not be invertible modulo n). To com pute a/b (mod n), b must be invertible modulo n. If b is invertible m odulo p, it need not be invertible modulo n. In general, com puting points on an elliptic curve is a straightforw ard calculation. Algebraically, for P = {xp, yp), and Q = {x q , pg), P + Q = R = (xp, yp) where - z g , and 2/p - % . s = -----------Xp Xq Here, s represents the slope of the line through P and Q. Notice th a t point addition in the context of elliptic curves is not componentwise. To com pute 2P algebraically, find 337p + a which gives values xp = - 2xp, and Clearly, 3 P = 2 P + P, etc. 29 yp = - y p . To factor n, select a point P satisfying equation (16) and com pute Q = R P where i? is a large positive integer divisible by all prime powers less th an some bound B. Clearly, Q = R P can easily be com puted unless there is a division by zero; however, in this case, a factor of n is found (the greatest common divisor of n and the denom inator). If th a t factor is n itself or if Q is successfully com puted, repeat the process as we have failed to find a factor of n. The elliptic curve m ethod for factoring factors in expected tim e [12] exp((0.5 + o(l))(logn)^-^^^(log logn)°'^). Similarly, the quadratic sieve factors a num ber n in expected tim e [12] exp((0.5 + o (l))(lo g n )^ °^(loglogu)°'^). The quadratic sieve, unlike th e elliptic curve m ethod, requires a factor base F — { p i,.. Pm}- Essentially, the quadratic sieve is a factorization m ethod which relies on finding two integers x and y for which (mod n) bu t x ^ y (mod n), using the factor base F. If such a situation arises, it is known th a t either {x — y, n) or {x -\- y ,n ) is a non-trivial factor of n w ith high probability. W hat is required to find X and y is to construct a sequence of positive integers /(c j) = F — n (mod n). Let U be the set of these r*. W hen more th an m of these n for which term s are found, we have - " P m " = ( p ^ p r ' - -P Z )^- 30 To form x and y, set and ^ = - Tieu Therefore, ^ = n Ti&U - n ri£U - ^ ) = n / h ) = ri€U ^)- Finally, the Euclidean algorithm determ ines b o th (x —y, n) and {x + y ,n ). As mentioned, the tim e complexity of b o th the elliptic curve m ethod of factoring and the quadratic sieve are very similar. The m ulti-polynom ial quadratic sieve (an improvement over the quadratic sieve) yields a heuristic expected tim e [12] of ex p ((l 4- o(l))(logn)°® (loglogn)°-^). As the name suggests, the m ulti-polynomial quadratic sieve takes advantage of several polynomials of the form f { x ) = a x ^“ -\-hx-\-c where a is a square, 0 < b < a such th a t = n (mod a) and 6^ —4oc — n. W ith some arithm etic, it can be shown th a t {ax + b)‘^ = a f{ x ) (mod n), and since a is a square, so too is f{ x ) . So, if f { x ) factors easily, we obtain a similar factoring situation to the quadratic sieve. Finally, the num ber field sieve provides an even b etter expected tim e of approxi­ mately, exp((1.526 -f- o(l))(logn)^^^(loglogn)^^^). Unlike previously mentioned algorithm s, the nnm ber field sieve attem p ts to factor integers n of the form n = r® ± s, where 31 r, s G Unfortunately, due to the extensive am ount of algebraic num ber theory required to fully appreciate the algorithm , a complete overview is not given here. However, the idea behind the sieve is th a t b o th the algebraic integer a + ba and th e integer a + bm are sm ooth over a factor base. If $ is a ring homomorphism between Z[a] and Z„, then ^ { a + ba) = (a + bm (mod n)). W ith sufficiently many of these congruences, one can find a solution to th e equation (mod n), which in tu rn may yield a non-trivial factor of n. 2.11 C o m p u tin g Bn an d ( (n) Much research has been done in com puting b o th the Bernoulli num ber, i?„, and the value of the zeta function, C(n). Many of the techniques which are currently in use are described in the recent paper “Com putational Strategies for th e Riem ann Zeta Function” [9]. Most com putational work does not deal with the general problem of determ ining the value of ({n) or for a general integer value of n. Indeed, the m ajority of the research seems to lie in two different areas: com puting ({n) for a few select values of n (say n = 3 or 5) in an interesting way, and com puting complex zeros of the zeta function. Neither of these themes seems overly useful in the context of this thesis as we are prim arily interested in exact fractional values of function of the form and values of the zeta jb. Nevertheless, a brief description of these m ethods is still in order. Recall th a t for n 6 Z"*", ((1 — 2n) = and for n G Z"*", ((2 n ) = 32 \B 2n\- Therefore, any com putational technique used to com pute values of the zeta function can also be used to com pute Bernoulli numbers. W ith this in m ind, we concentrate on algorithm s to com pute values of th e zeta function. S tandard recurrence relations can be used to find the value of C(^)- For instance, w ith k > 2 , k -l 1 ^ C ( 2 ;) C ( 2 A ; - 2 j) = (A: + -)((2& ). A lthough this yields exact values for C{2k), it is rarely used as A; — 1 previous values of the zeta function m ust be a priori known. To approxim ate values of the zeta function in the complex plane, one can use the formula j=o where poo 1 fS-l and r is the gam m a function. This m ethod is referred to as a “Lerch-series approach.” The Lerch-series approach can be used whenever s G C and 7?.[s] > 0. Approxim ations to values of the zeta function for integers have become increas­ ingly easy to obtain due to the current ease of approxim ating tt. Of m ajor interest, is the value of ((3). Many different formulations have been derived for C(3) w ith the hope of being able to simply extend the formulations to C,{n) for arb itrary n. One example stem s from the following equality [16]: (1 - 2-^""-^)2((2m -h 1) m —l (1 - 4-'=)((2A: -h 1) ' “8 2 - ^ + E 33 which, for m = 1, yields Of course, once one has C(3), com puting ((5) is straightforw ard and once C(3) and C(5) are known, com puting ({7) is straightforw ard etc. Notice also th a t th e term ^ jlo g 2 - ^ + 4" ^ % ) } converges quickly because of the (2m)! and 4" term s in the denom inator. Therefore, values of the zeta function for odd integers are easy to approxim ate. A similar formula holds for even integral inputs, however it is not as simple to compute. This approach is known as “recycling” as previous values of the zeta function are recycled while trying to com pute a current value. A nother recycling approach is given by th e following algorithm due to C randall [ 16J. A lg o rith m 2 .7 (R e c y c lin g S c h é m a fo r ( ( 2 ) , . . . ((T + 1)) 1. S e t P r e c is io n Select N such that 2~ ^ is less than the required precision and N > L. 2. Q u o tien t A r r a y Create g{k) = P {k )/Q { k ), fo r k E [0, 4A — 1], where P{k) = (—A)^’, and Q{k) = k\(k + 1 — z). 34 3. R eso lve g F u n c t i o n P = 1; while p < 2 N do fo r q = 0 to 4 N — 1 — p do g{q) = g{q)-\-g{q-\-p) with g[q) in the form num erator/ denominator and reduced modulo end; P = 2p; 4- M o n ic R e v e r s io n Now, g{0) = P {0)/Q (0) with each o f P ,Q being o f degree at most L, so divide each of P, Q through by its constant coefficient; 5. I n v e rs io n Create polynomials P^^ and using Newton inversions. stance, to find P~^, set p = g = \ wAz/e (p < )) do p = max(2p, d ep (f )); h = P (mod z^); g = (9 + g ' (1 - ' p)) (mod zP) end/ 35 For in­ 6. C o e f fic i e n t C o m p u t a t i o n Compute the coefficients Rk m the polynomial L -R(z) = ^ Rkz'" = {{dP /dz)P ^^ - {dQ/dz)Q~^) k=0 7. (mod O u t p u t C V a lu e s ((/û) A t- i The operation complexity of this algorithm is 0 { L ~ ^ N log^ L) for each of the L evaluations of (. So, if L ~ N , (th a t is D values with each to D digits) th e average cost is about 0(log^ D) per value. A third approach, due to Plouffe and Fee [16] uses the von Staudt-C lausen theo­ rem to com pute the denom inator of Bn and asym ptotic techniques to determ ine the num erator. The result is an exact value for Bn which can easily be converted to a value of (. The tricky p art of this algorithm is determ ining the value of the denom­ inator which is essentially a problem of factoring n — 1. This approach was used to determ ine the value Bgooooo m its rational form. 36 3 G iu g a ’s C on jectu re In 1950, G. Giuga proposed the following [20]: n —1 n is prime <=> s{n) := = —1 (mod n). If n is prime, then by F erm at’s Little Theorem, (Theorem 2.5) n —1 n —1 k=l k=l —l = n — 1 = —1 Thus, the converse is all th a t rem ains as conjecture. (mod n). We shall denote the set of positive integers n > 2 th a t satisfy s(n) = —1 (mod n) by E. In this way, we see th a t P C S and G iuga’s conjecture asserts th a t P = E. In his original paper [20], Giuga proved th a t any composite integer n € E m ust satisfy {p — l)\{{n/p) — 1) and p\{{n/p) — 1), for every prime divisor p of n. We include the proof here for completeness [8]. T h e o re m 3.1 n e T, if and only i f fo r each prime divisor p o f n we have (p - 1) I ((n /p ) - 1) aW p I ((n /p ) - 1). P ro o f: Before directly proving the equivalence, a general property is established. Suppose th a t (p — l) |( n — - 1 (mod n) by F erm at’s Little —1). Then X)fc=i Theorem (Theorem 2.5). If ( p - 1) / ( n —1), then it m ust be true th a t = 0 (mod n) (Theorem 2.2). So, we have: —1 (mod p) if (p - l) |( n — 1) = j I . 0 (mod p) 37 otherwise (17) Therefore, for every prime divisor p of n, with n = PQ-, it must be the case, by considering residue classes, th a t : ^ (-« j (mod p) 0 (mod p) I if ( P “ l)i(n - 1) , (18) otherwise as we are considering the class of p — 1 g-times. This result is now employed in the direct proof. (=>) Let n G 2 . It is clear th a t for each prim e divisor p oî n (where n — pq), it is true that: —q (mod p) if (p — l) |( n — 1) (19) 0 (mod p) otherwise Since it is not possible th a t —1 = 0 (mod p), it must be the case th a t (p — 1) | (n — 1). However, since n — l = p g — 1 = q{p — 1) + (g — 1), it m ust also be true th a t (p — 1) I (g — 1) but g — 1 = (n /p — 1). It also follows from Equation (19) th a t —1 = —g (mod p), which implies th a t p | (g — 1). {<=) Now, suppose it is the case th a t (p — 1) | ((n /p ) — 1) and p \ ((n /p ) — 1). Notice th a t n m ust not contain any squared term s as if it did, there would be a prime p where p jn /p , which contradicts p |((n /p ) — 1). It is clear from Equation (18) th a t X)fc=i = ~Q (mod p) using the first divisi­ bility condition. The second divisibility condition, however, implies th a t n /p = g = 1 (mod p) which means th a t But, since p | = —1 (mod p) for each prime divisor p of n. 4- l) for each prim e divisor p of n and each of these divisors is distinct (i.e., no squared term s), it m ust be the case th a t n —1 n-l n I /c” ^ + 1 k=l n —1 A:” ^ 4 - 1 = 0 (mod n) <=> k—1 ^ = —1 k=l 38 (mod n). or alternatively th a t n G E, as required. C o ro lla ry 3.1 n P ro o f: ■ n is square-free [8]. Suppose not. T hen it m ust be the case th a t for some p, p‘^\n, and p\{{n/p) — 1). However, since p ‘^\n, and p\{n/p), then p f{{n/p) —1), which contradicts Theorem 3.1. ■ C o ro lla ry 3.2 n e 'E if and only if p^{p — 1) | (n —p) fo r any prime divisor p o f n [2 j. P ro o f: Theorem 3.1 states n G S if and only if p |((n /p ) — 1), and (p — l) |( n — 1). Therefore, it stands to show th a t p |((n /p ) — 1), and (p — l) |( n — 1) if and only if p^(p - 1) I (n - p ) . Since p |((n /p ) — 1), kp = (n /p ) — 1 kp^ = n — p, which shows th a t p^|(n —p). However, note th a t (p,p — 1) = 1, and (p — l) |( n — 1) = (n —p) + (p — 1). Therefore, p ^ (p - l)l(n -p ). ■ C o ro lla ry 3.3 I f n G S , then {4>{n),n) = 1 [2]. P ro o f; The assertion is obviously true if n is prime. Hence, take n G E w ith n composite (and square free by Corollary 3.1). Let p and q be distinct primes th a t divide n. Assume th a t p = 1 (mod q) for some p ,q\n (th at is, a prime factor q oî n divides part of 0(n)). Then, since n G E, 0 = (n - 1) + (1 - n/q ) = n - n /q = (n - q) + {q - n /q ) = - n / q which is absurd since n is square-free (Corollary 3.1). (mod q), ■ It is im portant to notice the link between Giuga’s conjecture and other aspects of num ber theory. Of particular im portance is the condition th a t if n G E, then 39 n is a square free integer such th a t for any prim e p th a t divides n, it is tru e th a t (p - 1) I {n/ p - 1). This condition is referred to as the Carmichael condition [8]. D e fin itio n 3.1 A positive square-free composite integern is said to satisfy the Carmichael condition i f { p —l) | {{n/p) — !) fo r every prime p where p | n. Equivalently, n satisfies the Carmichael condition if {p — l) |( n — 1) fo r all prime divisors p of n. D e fin itio n 3.2 A positive square-free composite integer n is said to he Carmichael if it satisfies Ferm at’s Little Theorem: aU-i = 2 (mod n), (20) whenever {a,n) = 1 and a < n. We refer to the set of Carmichael numbers greater than 2 as V. In 1910, Carmichael conjectured th a t there are infinitely m any com posite integers which satisfy Equation (20) [5]. In 1994, Alford et ah [5] proved w hat was known as C arm ichael’s conjecture: there are infinitely many Carmichael numbers. Their technique involved showing th a t for sufficiently large n, the num ber of Carmichael numbers less th an n is greater th an [5]. Hence, as 7% —^ oo, so too does the num ber of Carmichael numbers. Pinch [28] showed th a t for a given n, the num ber of Carmichael numbers less th an n is bounded above by n exp | ~ Among the most common Carmichael num bers are those of the form {6k + l ) {12k+ l){18k + 1) where k G and each of (6A: + 1), {12k + 1) and (18& + 1) are prime. This representation gives rise to one of the largest Carmichael num ber ever found, having k = 1805 [18]. W ith reference to the second condition in Theorem 3.1, the following definition is used. 40 D e fin itio n 3.3 A composite integer n with the property that p \ {{n/p) — 1) fo r all prime dirigors p 0 / n w to 6e a Gmpo Member. TAe get 0 / of/ Gmpo Mwmberg is denoted Q. Theorem 3.1 can now be restated as follows [20]: T h e o re m 3.2 n G E and is composite i f and only if n e T Ci G ■ G iuga’s conjecture asserts th a t T DG = f . 3.1 G iu g a N u m b e r s an d G iu g a S eq u e n c es Let p be a prime divisor of n. Then, Definition 3.3 is equivalent to the statem ent: E ^ -fl^ p\n (21) p\n This equivalence is due to Giuga [20]. For the sake of convenience, we often refer to this expression as the sum minus product (and the associated integer as th e sum minus product value). G iuga’s result, th a t a Giuga num ber is the same as an integer th a t satisfies Equa­ tion (21), leads to the following generalization. D e fin itio n 3.4 A finite increasing sequence of positive integers { a i , . . . a ^ } is said to be Giuga if X]™ 1 ^ ^ E Uj is prime fo r each i, the sequence is N. said to be a proper Giuga sequence. A Proper Giuga sequence gives rise to a Giuga number n G S, equal to the product o f the elements in the set. The following generalization of G iuga’s result is due to Borwein et al. [8]. G iuga’s original result follows as a corollary. 41 T h e o re m 3.3 A finite increasing sequence of positive integers { « i,. . . a, I fli • • • satisfies • Oj-i-i • ■• «77! - 1 for every i < m i f and only if it is a Giuga sequence. P ro o f: Let A = define bi = A jo i. Notice th a t th e sequence {oq,. . . , Om} is Giuga if and only if yl|(6i 4 h 6m - !)• The converse is an im m ediate consequence of this alternative representation of a Giuga sequence. To show the converse, assume th a t a, | (6— 1) or equivalently, th a t of | {A —afi for every i. Integer m ultiplication yields A^ | {A — a i ) - - - { A — am). Ignoring all multiples of A'^ reveals th a t A “ ^ j {A{bi H 1- 6m) —(ui • • • Om)) = {A{bi H implies th a t ( oq, . . . Um} is a Giuga sequence. ■ C o ro lla ry 3.4 n is a Giuga number if and only if y i - n l 6 N. C o ro lla ry 3.5 [2] n e 12 if when p is a prime factor o f n n P ro o f: 1 - = 1 I P p\n (mod n). Clearly, n satisfies It follows th a t "'Eyn^i G K p\n p\n This gives y iV --! 42 h 6m — 1)), which E N. Now, the denom inator of the sum term will be n (as the product of th e primes is n] This will cancel out the n in front of th e sum. Hence, by Theorem 3.3, n - = 1 (mod n). It is conceivable th a t an integer n could give rise to two different non-trivial factorizations, both of which are Giuga sequences. There is no known example of this. If it happened to be the case th a t no Giuga num ber could also be a Carmichael number, then Giuga’s conjecture would be proved. Since all Carmichael num bers are odd, if every Giuga sequence contains an even factor, then it follows th a t G iuga’s conjecture would be proved. The search for Giuga sequences has been completed up to and including length 8 and the results are contained in the following table [8]: N um ber of S equences None One Two Three 17 27 Hundreds N u m b e r o f F a c to rs 2 3 4 5 6 7 8 Table 7: Num ber of Giuga Sequences Of the Giuga sequences referred to in Table 7 only 12 are proper and those are listed in Table 8. Even if the num ber of Giuga sequences of a given length seems to increase d ra­ m atically w ith the num ber of factors, the next result (which was obtained through 43 3 fa c to rs : 30 = 2 3 5 4 fa c to rs : 858 = 2 3 -11 13 1722 = 2 - 3 - 7 - 4 1 5 fa c to rs : 66198 = 2 - 3 - 1 1 - 1 7 - 5 9 6 fa c to rs : 2214408306 = 2 - 3 - 1 1 - 2 3 - 3 1 - 47057 2442 3 1 2 8 5 6 2 = 2 - 3 - 7 - 4 3 - 3041 - 4447 7 fa c to rs : 4 3 2 7 4 9 2 0 5 1 7 3 8 3 8 = 2 - 3 - 7 - 5 9 - 1 6 3 - 1381 - 775807 14 7 3 7 1 3 3 4 7 0 0 1 0 5 7 4 = 2 - 3 - 7 - 7 1 - 1 0 3 - 67213 - 713863 550843391309130318 = 2 - 3 - 7 - 7 1 - 1 0 3 - 61559 - 29133437 8 fa c to rs : 2 4 4 1 9 7 0 0 0 9 8 2 4 9 9 7 1 5 0 8 7 8 6 6 3 4 6 = 2 - 3 - 1 1 - 2 3 - 3 1 - 47137 - 28282147 3892535183 5 5 4 7 9 9 1 4 6 1 7 0 7 0 8 0 1 2 8 8 5 7 8 5 5 9 1 7 8 = 2 - 3 - 1 1 - 2 3 - 3 1 - 47059 - 2259696349 110725121051 1 9 1 0 6 6 7 1 8 1 4 2 0 5 0 7 9 8 4 5 5 5 7 5 9 9 1 6 3 3 8 5 0 6 = 2 - 3 - 7 - 43 - 1831 - 138683 2861051 -1456230512169437 Table 8: Proper Giuga Sequences communication with Julian Buck and Jed Brown) guarantees th a t there are only finitely many sequences of any length. P r o p o s itio n 3.1 Let m be a fixed natural number. P ro o f: Then there exist only finitely Fix m. and let { a i , . . . , am} be a Giuga sequence. From Definition 3.4, / ^n 44 Furtherm ore, there is an element a,-•/I such th a t -F > -L m since if this were not the case then ^ = 1, a contradiction. This implies th a t < m. Therefore, there are at most m. choices for Since ^ y 1 T 1 -, 1 - 2_ > 1 _ ± it must be the case th a t there is an such th a t 1 Ojg d-j, — 1 (m - ' since otherwise we would have V - - — < (m -l)f another contradictory statem ent. So, we have and because m. is fixed and there are only finitely m any choices for o^j, it follows th a t there are only finitely many choices for aj^. All other cases follow in an analogous m anner. For example, it is not difficult to show th a t 1 ^ Qjiflja - Qji - Qja (Zja (m, and so (m - 2)(Zj,aj2 implying, again th a t there are only finitely many cases for aj^. In general, it must be the case th a t E quation 22 can be shown in the following way. Suppose for 1 < r < m — 1, and Ujj, 0 ^2 , •. . , %. have all been removed from the sum. Then it is necessarily the case 45 th a t ,_ 1 “ h i=l lT i=i^ji Again, this implies th a t there is an aj‘jr+1 such th a t 1 > m . i %. - ( e L i - r) ni=i Qjr+i which implies the desired result th a t ------------------------------ > 0>+i • Using the same argum ent as before, because of a fixed m, there are only finitely many choices for each of aj ^, . . . , aj ^. values for Hence, there are only finitely many integer It follows th a t each a, € { a i , . . . ,am} may take on only a finite number of integer values. Therefore, the num ber of Giuga sequences of length m is finite. ■ A lthough the proof is rath er long winded, it leads to an algorithm for finding all Giuga sequences of a given length. This algorithm can be found in A ppendix 4. C o ro lla ry 3.6 Define Grn = {« G N |a is an element of a Giuga sequence o f length m ). For any fixed m. E N, Gm has a maximal element. It is not known if all n G N could be an element of Gm for some m. Further, although the number of Giuga sequences of a fixed length is lim ited to a finite num ber and there is a maximal size of element for any given sequence length, we can say more. If { o i , . . . , üm} is an increasing Giuga sequence of length m then there are bounds on each term of the sequence (another result due to H obart and Buck). 46 P r o p o s itio n 3.2 I f {ai, 0 2 , • • • ? is a Giuga sequence with sum m inus product x, t/lGM m > GiT. P ro o f: Fix oi and notice th a t for z = 1, . . . ^a +i > T is J 2 ^ \ ^ > z. This shows Therefore, a sufficient condition for 771 «1 > -F - as a, + 1 < a i + i üi-)-1 ^ u .|i-l m , m V—\ 1 \ \ 1 ) — > > — > T. 6 «i M ultiply both sides by Ui to obtain the desired result. The hnal theorem in this section shows a bound on Oj for m any different j , based solely on the choice of Ui. T h e o re m 3.4 Let m be a fixed natural number and suppose that { « i , . . . Giuga sequence. Then fo r any j such that ai + 1 — j > 0, Oj < • P ro o f: a^ - • ■ttm + «1% • • • Urn + . . . + Ul • • • Om-1 ( i — 1 )« 2 • • • «Ï7Ï + ui {j — ^ J + l)o i • • • U j - i aJ + {m — j + l)a i > 1 UlUj 47 ■ > 1 Oj_|_i • • • « m ^ ^ is a (m —J + l) a i > aiüj — [j — 1)( (m —J + l) a i > aj{a\ — {j — 1)) (m - j + l ) a i = > ---------- —r “i— > o-j ai-j + 1 whenever oi + 1 —j > 0. From a theoretical standpoint, all of these results are fairly interesting, however, from a com putational point of view, they are perhaps less spectacular th an one would hope. Among other problems, the results so far, by their very construction, make no attem pt to discourage an exponential time increase when increasing the length of a Giuga sequence. 3.2 “T h e E ig h tfo ld W a y ” Recall th a t G iuga’s conjecture states th a t n is prime iff; n —1 = —1 (mod n). k~l “The Eightfold Way” is a set of variants of this equation, due to Wong [57], involving Euler’s phi function. These 8 similar versions of G iuga’s conjecture, give insight into the requirem ents for counterexamples to the conjecture. Before showing th e eight variations, we need to establish two im portant results. Theorem s and proofs from this section are established in [57]. 48 T h e o re m 3.5 Let q = bé a prime power. Then I0 A:"* = < ^ fceZ* P ro o f: If g = 2, then, (mod g) I 4>{q) otherwise (mod q) = 1 = 0(2) (mod 2). Now, suppose th a t p > 3 . We claim th a t A™ = 0 (g) (mod g) ( p - l ) | m . te Z ; Let •5 = where E *:“ = E ( d ) ” = E te z ; k=0 t=0 Ogisa prim itive root m odulo g, and 0 = a™. Saying (p — 1) / m isequivalent to 0 — 1 being non-zero modulo p and hence invertible m odulo g. So,if (p — then S' is a geometric series and S = 1) J(m, = 0 (mod p). Now, suppose th a t (p — l)|m . T hen w ithout loss of generality, m = (p —l)p^"^, where 1 < s < r, and therefore, 0 = 1 (mod p^) by lemma 2.2. Since the order of 0 is 0(g)/m = p^~^, S consists of m repetitions of p '- '- i r= y] 0\ A’= 0 Since a-p is primitive, the sum m ands of T are distinct modulo g and are all congru­ ent to 1 modulo p*. Thus, they m ust form a perm utation of the arithm etic progression 1 + mp^, 3 < m < p r — s. The sum of the term s in this progression is pr-« _ g_ g+ which gives T = p’’^®, hence S = m T = (p — l)p '’'"^ = 0(g). 49 Now,when p = 2 and hence g = 2% then k"^ = 0 (2 ^) (mod 2’') <=> m is even. For m odd, the term s of th e sum ^ ^ g . /o'” cancelout in pairs, thus A;"' = 0 (mod 2"). Suppose m even. W ithout loss of generality, we can take 1 < s < r — 2 . Then (2V4)-1 s = ( l + (-!)"■) Y , /J‘. k~l where j3 — S'". Since m is even, the first factor is 2. The second factor consists of m repetitions of T= Y fc=0 The sum m ands of T are distinct m odulo T" and congruent to 1 modulo 4m. There­ fore, they form a perm utation of the arithm etic progression 1 -|-4mn, 0 < n < T j Am, which sums to 2'"/4m + 4m (2'-/4m )(2Y 4m - l) / 2 = 2Y 4m + 0 (2 ''/2 ). M ultiplication by 2m yields S = 2m.T = 2'"/2 = ■ T h e o re m 3.6 I f ni > 1, then A:'" ks Z* (mod q). ke Z , WAeM p ig odd, (Ae congruence Aolds /o r m > 1 . P ro o f; W hen m > r this is a trivial result obtained by applying F erm at’s Little Theorem and noticing th a t th e orders of the groups are the same m odulo q. Thus, 50 use r = 1 as the base case and proceed by induction. For r > 1 , Z Z fce Z , Z te Zg fceZp^_i Since the last term is divisible by ^ /o’" = ^ A:"* (mod q). fee Z , fee Z* k- 1 k ^ ' ^ p k = - q p ' ‘ + 1, W hen 777. = 1, fee Zg fee Z* ^=1 which is divisible by g if p is odd. ■ We are now in a position to develop the eight general equations related to G iuga’s conjecture. The first result is a generalization of Theorem 3.1. The next two results follow trivially. T h e o re m 3.7 YlkeJj (mod n) if and only i f n is square free and fo r each p n m e divisor o fn , we have {p — l)|r ? 7 and p\{{n/p) — 1) P ro o f: We begin by showing th a t n is square free. Suppose th a t g|r7. where p|r 7 and q is a prime power of p. In particular, this means th a t p^\n. T hen p\f{q), and hence, fc™ = 0 7 ^ - 1 (mod q). fe€ Z ti In a similar way, we require g k'^ to be non-zero modulo p. Hence, the condition th a t (p —l)|r 77 for odd p follows from Theorem 3.5. If p = 2, the congruence is trivial. The third condition is m et when we consider /c"* = {n/p)(f){p) = - 1 fee Z,i 51 (mod p). Dividing the equation by (p{p) = p — I = — 1 (mod p), weget n / p = 1 (mod p). or p\{{njp) — 1), as required. ■ C o ro lla ry 3 .7 = —1 (mod n) if and only if n is square free and fo r Z„ each prime p dividing n, p\{{n/p) — 1). ^ —1 (mod n) if and only if n is square free C o ro lla ry 3.8 (G iu g a ) and fo r each prime p dividing n, p\{{n/p) — 1) and {p — l)\{{n/p) — 1). A fter examining the two cases where the exponent on A: is n — 1 and 0 (n), we consider the cases arising from changing th e modulus. T h e o re m 3.8 = (p{n) (mod n) if and only if fo r every 1 < i < I, one of g the following conditions holds: • Z, * Z t e Zg P ro o f: = 0 (mod q) and p\q — 1 fo r p, q\n; or ^ ^( 9 ) g) ond n|g = (mod g). For the first case, consider (j){q)(j){n/q) = 0 (mod g). This is equivalent to p\(p{n/q), which is in tu rn equivalent to p|(g — 1 ) for all p and g|n. In the second case, we ■4>{q) is divisible by must have {n/q)4>{q) = p, this is a contradiction. ■ It is clear th a t Z* is a group under m ultiplication. We need some further infor­ m ation about the structure of this group. Indeed, Z* is isomorphic to the C artesian product Z p p X ZpT2 X • • • X Z rt [57]. Define Z%' to be the set of elem ents of Z* which are congruent to 1 modulo n/qi. This set has cardinality of <^(%), and contains a unique representative modulo % for each element in Z* By applying the Chinese Rem ainder Theorem, we obtain the following fact [57], which we will require later: T h e o re m 3.9 Every x G Z* can he written uniquely as a product x = X\X 2 ■■■xi (mod n) with each z, G Z*'. P ro o f: (mod q), z, m ust be the unique element of Z%' which is Since f l L i congruent to x modulo q. m Using this representation, we can factor S = Ylke Z* m to S'iS'2 • • • Si where te z ;' Since Si = 4>iqj) (mod qj) whenever j congruent to Z* 7^ i, we are only interested in the Si modulo %. Theorem 3.5 gives j0 if (p - (mod I (j){qi) (mod qi) 1 ) J(fn otherwise Therefore, ' jo (mod qt) if (p = (mod%) This representation gives rise to the next theorem. 53 1 ) /m otherwise T heorem 3.10 S' = g . /c'" = - 1 (mod ») Âf o»/?/ ^ n ^ pnme artd (n - l)\m . Proof: Since (n — l ,n ) = 1, it m ust not be the case th a t S* = 0(mod i. Therefore, S, = (p^Qi) for all i, so th a t S = 4>{n). However,4){n) %), for any < n ~ Iwhenever n is not prime. The result then follows from Theorem 3.5. ■ Corollary 3.11 S = YlkeX* = —1 (mod n) if and only i f n is prime. Corollary 3.12 S = Ylke Z* = —1 (mod n) if and only i f n is prime. T heorem 3.11 S = — ^(n) (mod n) if and only if fo r each i, either E k e z ;. Proof: or Pj|(pj - 1) ybr som e pj|M. If S = YhkeX* = 0 (mod %), then we need (f){n) = 0 (mod %) which implies the second condition. If = E t e Z; we have the argum ent before the theorem. ?) ■ The final two corollaries for this section complete th e set of variants of G iuga’s conjecture. They follow naturally from the previous theorem. C orollary 3.13 S = Ylke Z* = <^(n.) (mod n) fo r all n E N. Corollary 3.14 S = — (/)(«) (mod n) if and only i f n = 2 or n is odd Z* and (p — 1)1 (n — 1) fo r each prime divisor of n. Proof: n m ust satisfy (p — l) |( n — 1) by the same argum ent as Corollary 3.10. As in th a t same Corollary, the condition does not hold when n is a power of two, so n cannot be even. By Theorem 3.11, th e condition is sufficient. 54 ■ Table 9 summarizes the eight different variants of —r ( 23 ) (mod n). kei m Zn Zn r n —1 n —1 <^(n) n —1 Z» (^(n) (^(n) Zn <^(n) n —1 z: z; z: z: n —1 n —1 (^(n) <^(n) (^(n) n —1 <^(n) n —1 I C onditions on n p\{{n/p) — 1) for all prime divisors p of n. n is square-free, p\{{n/p) — 1) and (p — 1)1 ((n /p ) — 1) for all prime divisors p of n. n /q = 4>{n/q) (mod p) for all p |n where q\\n. n is odd, n jq = 4>{n/q) (mod p), (p — 1)1 (n — 1) for all p |n where q\\n. C orollary 3.7 3.8 Prime Prime Every n G N n is odd and (p — l) |( n — 1) for all prime divisors p of n. 3.11 3T2 3T3 3.14 3.9 3.10 Table 9: The “Eightfold Way” The next section looks at the conditions for these equivalences to hold. We will develop the theory of norm al families of primes, co-Giuga num bers and pseudoCarmichael num bers and how they relate to equation 23. 3.3 N o rm a l F a m ilies, C o -G iu g a , an d P se u d o -C a r m ic h a e l N u m ­ b ers Normal families of primes are im portant in the study of G iuga’s conjecture for a number of reasons. First, any counterexample to G iuga’s conjecture m ust be norm al (because of the Carmichael condition). Second, the norm al family condition on the counterexample allows significant com putational work to be done on G iuga’s con­ jecture. This section outlines some results on normal families of primes as well as the theory of co-Giuga numbers and pseudo-Carmichael numbers. This will conclude 55 the development of W ong’s Eightfold way and provide a lead in to some im portant com putational results. Results in this section stem primarily from the work’ of Wong [ 5 7 ] . 3.3.1 N orm al Fam ilies o f P rim es Any counterexample, n, to G iuga’s conjecture m ust satisfy pi /f {pj — 1) for any two prime divisors of n . Indeed, if — 1), then there is a A such th a t P i \ { p j k p i + 1 = p j and so P j —I = { { k p i + 1) — 1)1 (n — 1) and p j \ n . This contradicts Theorem 3.1. The prim e factors of such an integer give rise to a set which is called normal. D e fin itio n 3.5 A finite fam ily P of distinct primes is called normal if P i / i P j 1)7 - fo r every p, and Pj. Exam ple 6 The set {3, 5,17} is normal while the set {3, 7,13} is not because 3|13 —1 and 3|7 — 1. Using the power of Sylow’s theorem s, we have the following results about normal families. The result is due to Holt, and can be found in Wong [57]. Theorem 3.12 Suppose P = {pi,P 2 i • • • , P m } is a normal fam ily o f primes and let n = P 1P2 ■■- Pm- Then there is a unique group of order n up to isomorphism. Proof: Let G be a group of order n . If P = {pi,P 2 ■• - P m } is a Sylow p-subgroup of G, then |A u t(P )| = p — 1 does not divide |G|. Applying the Burnside Transfer 56 Theorem shows th a t G has a normal subgroup N of order n /p i such th a t G = N P . Choosing P to be a norm al Sylow p-subgroup of G, we see th a t G = N x P . Induction on m completes the argum ent. ■ T heorem 3.13 I f n is divisible by primes pi,Pj fo r which pi\{pj — l), then there exists a non-cyclic group o f order n. Proof: It is sufficient to find non-cyclic groups of orders and pq. Zp x Zp suffices for a group of order p^. For a group of order pq, let 6 be a prim itive p — th root of unity modulo q. Then the group w ith presentation = y^x) is non-Abelian and of order pq. m As stated previously, any counterexam ple to G iuga’s conjecture m ust be normal. O ther well-known unsolved problems in num ber theory revolve around the normal condition as well (for example Lehm er’s conjecture). For a more detailed reference, please see G uy’s book, Unsolved Problem s in Number Theory [21]. 3.3.2 Pseudo-C arm ichael N um bers We noted earlier (Corollary 3.14) th a t an integer n satisfies = 4>{n) (mod n) if and only if n = 2 or n is odd and (p — l) |( n — 1) for each prim e divisor of n. The condition th a t (p — l)|(n — 1) is known as the pseudo-Garmichael condition [57]. D efinition 3.6 A n integer n is said to be pseudo-Carmichael if fo r every prime di­ visor p o fn , (p — l) |( n — 1). The pseudo-Garmichael num ber condition is identical to the Carmichael condition; the difference between a Carmichael num ber and a pseudo-Garmichael num ber is th a t 57 n is not required to be square-free. Hence, every Carmichael num ber is also pseudoCarmichael. Since there are infinitely many Carmichael numbers, it follows th a t there are infinitely many pseudo-Carmichael numbers. The following theorem provides a link between norm al families of primes and pseudo-Carmichael numbers. T h e o re m 3 .1 4 Let P = { p i,P 2 , - - - ,Pz} ^6 a normal fam ily of primes, and define ri = lcmi^j{(f{pj)). Then any number o f the fo rm pseudo-Carmichael. with p e i P is Conversely, i f n is pseudo-Carmichael, then its prime factors form a normal family. P ro o f: Since 0(pj)ITi whenever j ^ z, it m ust be the case th a t = 1 (m o d p j —1), by Euler’s generalization of F erm at’s Little Theorem. In the case th a t i = j, pkiu _ 2 (mod P i - 1) holds trivially. Therefore, whenever I n — =^ (mod Pj - 1), i=l {pj — l) |( n — 1), for all j. Conversely, suppose th a t n is pseudo-Carm ichael b u t the prim e divisors do not form a norm al family. As n is pseudo-Carmichael, it m ust be the case th a t (g —l) |( n — 1), which implies th at {q — 1)1 = n — 1, / G Z. Further, the condition th a t the factors of n are non norm al implies p|(g — 1) or th a t pm, = g — 1, m, G Z. These conditions together imply p |(n — 1) which is absurd as p|n. 58 ■ 3.3 .3 C o -G iu g a N u m b e r s As was the case w ith pseudo-Carmichael num bers, we can define a class of integers whose characterization is similar to th a t of a Giuga number [57]. D e fin itio n 3 .7 A n integer n is said to be co-Giuga if fo r all primes p dividing n and all q = p^\\n it is the case that n /q = f i n / q ) (m od p). Clearly from the definition, co-Giuga num bers need not be square-free while the same cannot be said for Giuga numbers. It is also true th a t th e prim e factors of a co-Giuga num ber m ust form a norm al family. If this were not th e case, then for some prime divisor p, f i n / q ) = 0 ^ n /q (mod p). Recall th a t a Giuga number, n, satisfies the equation A similar characterization applies to co-Giuga numbers. Since the co-Giuga condition is independent of the exponent on p, we can consider only square-free num bers w ithout any loss of generality. T h e o re m 3.15 n is co-Giuga if and only if P ro o f: Suppose th at n = P1P2P3 (a similar argum ent works for more prim e divisors). Then, (P2 - 1)(P3 - 1) = P2P3 (mod Pi) (pi - 1)(P3 - 1) = P 1P 3 (mod P2) (P2 - l)(Pi - 1) = P2P1 (mod ps). 59 W hich means that: (pi - 1 )(P2 - 1)(P3- 1) = PzP3(Pi - (Pi - 1)(P2 - 1)(P3 - 1) (mod pi) = PiP3(P2 - 1)(mod Pa) 1) (Pl - 1)(P2 - 1)(P3- 1) = PlP2(P3 - 1) (mod Ps). Using the Chinese Rem ainder Theorem (Theorem 2.4), it is clear th a t there is a unique solution to this system given by (pi - l)(p 2 - l)(p3 - 1) = - P 2P 3 - PiPa - P1P2 (mod n). This formulation, however, is equivalent to \ P i/ V P2/ \ P 3/ Pi P2 P3 or alternatively, A similar argum ent can be used to prove the theorem on an arb itrary num ber of divisors. ■ In his paper, Wong [57] showed th a t there is no non-trivial co-Giuga num ber w ith fewer th an 7695 prime factors. We conclude this section w ith W ong’s original proof as well as W ong’s original representation of the “Eightfold way” , illustrated in Table 10. D efinition 3.8 Given two families of primes A — {pi,P 2,P 3, - - - ,Pt) and B = {gi, 9 2 , 9 3 , - ' ,%}, with Pi < Pj and g, < qj whenever i < j , we say that A domi­ nates B if k > I and p, < Qi fo r every 1 < i < 1. T h e o re m 3.16 There are no non-trivial co-Giuga numbers with fewer than 7695 pnme /actora. 60 P ro o f: Let P = {pi < P 2 < P 3 < • • •} be a norm al sequence of primes. Consider the expression d (P P ) = n A - + y 1 - 2, / GZ + . It is clear from Theorem 3.15 th a t n — f l L i Pi is a co-Giuga num ber if d{P, I) G Z. If I = 1, then d{P, /) = —1. Notice also th a t d is monotonically increasing (in the strict sense). The function is also m onotonically increasing in This implies th a t if Q is a normal family th a t dom inates P , and m < I, then d{Q, I) > d (P ,m ). Now, P is dom inated by one of th e following two sequences [57]: A = {5, 7 ,1 1 ,1 3 ,1 7 ,1 9 ,2 3 ,2 9 ,3 1 ,...} , or P = { 3 ,5 ,1 1 ,1 7 ,2 3 ,2 9 ,4 1 ,...} . However, d(A, 7694) = —0.000094 while d (P , 7694) = —0.4071613..., implying th a t — 1 < d {P ,m ) < 0 for m < 7695. Thus, d cannot be an integer. 3 .4 C o m p u ta tio n a l R e s u lts 3.4.1 C ounterexam ples Using the property th a t any counterexample to G iuga’s conjecture m ust be a Carmichael number, it is clear th a t the smallest counterexam ple is greater th a n 560 as 561 = 3 11 -1 7 is the smallest n G F. W hen he wrote his original paper [20], however, Giuga used the the Carmichael condition along w ith the Giuga condition to show th a t th e small­ est counterexam ple would require at least 1,000 digits. 61 As com putational power I r Zn n —1 Zn n —1 n —1 Zn (^(n) (^(n) Zn <^(n) n —1 z; z: n —1 n —1 (^(n) <^(n) <^(n) n —1 <^(n) n —1 m Conditions on n Trivial cases Non-Trivial examples Corollary Giuga Primes 30, 858, 1722, etc. > 13,800 digits > 7694 Prim e Factors > 7694 Prim e Factors 3.7 Giuga and None Carmichael Co-Giuga Prime powers Odd, Co- Odd Giuga and Prim e PseudoPowers Garmichael Prime Prim es Prime Primes All n e N All n e N Odd and Odd PseudoPrim e Carmichael Powers None None None Carmichael Numbers, 45, 225, 325, . . . 3.8 3.9 3.10 3.11 3T2 3T3 3.14 = r (mod n) [57]. Table 10: Conditions for increased, the estim ated lower bound increased to 1,700 digits (Bedocchi [6 ]) and most recently to 13,800 digits [8 ]. This section will outline th e com putational work th a t has been done on G iuga’s conjecture as well as some ideas for future research in the area. Two conditions are obvious for a sequence of primes P = {pi,P 2 ■■■,Pk} to form a counterexample to G iuga’s conjecture. • P is a norm al family. Define Sm to be the set of all norm al sets w ith maximum element smaller th an the prime, Pm- For any S G Sm, w ith S = {pi,P 2 ■■■,Pk}, define Tm{S) = {pi,P 2 - ■■,Pk,Pk+i, ■• ■,Pr} to be the smallest set of odd prim es which contains S, and for every pj > pm (the prime) and S U {pj} is norm al for j > k, and for 62 which ^ > 1. Define rm{S) as the num ber of elements of Tm{S)- Finally, define a sequence {imlm G N, = min{7’„ (5 )|S ' G -S'™}} . Giuga used the fact th a t this sequence is non-decreasing to calculate th a t a counterexam ple to his conjecture would have to have more th a n 1000 digits. Now, the num ber of prim e factors in a counterexam ple m ust exceed V m G N. It is clear th a t the prim e factors form a norm al family. Further, each subset S of factors less th a n pm is a mem ber of Sm- Since any norm al set of primes which contains S and satisfies the second condition above m ust have at least rm{S) elements, we have th a t n has at least rm(S) > im prim e factors (for any m G N). So, any counterexam ple is larger th an YVjliPj &iid therefore has at least the same num ber of digits as this product. After Giuga showed th a t a counterexam ple had over 1000 digits [20], Bedocchi [6] com puted ig = 544 which implies th a t a counterexample m ust have over 1700 digits. Borwein et al. com puted As = 835 w ith a similar algorithm , before looking for something b etter due to the significant slowdown resulting from exponential growth [8], W ith the following observation, Borwein et al were able to com pute A 35 = 3459 which implies th a t a counterexam ple m ust have at least 13,887 digits [8]. P r o p o sitio n 3.3 Consider S E Sm o,nd the value of rm{S). S has at most two “successors” S and S* in the set Sm+i- They are S and S* = S U {pm}- It is then tru e t W rm + i(S ') > rni(S') a W r m + i(5 '* ) > rm (S '). Proof: There are two cases to consider: S U {pm} is normal, and S U {pm} is not normal. CASE 1: 5 U [pm] is normal. T hen S has th e two successors S and S* in Further, we have Pm G Tm{S). However, Pm 0 Tm+i{S), b u t every other element is 63 contained in Tm+i{S). So, Tm+i{S) m ust contain at least one higher prim e for the sum EpGTm+i(g) p to exceed 1 . Therefore, g*, th e set contain primes which are congruent to 1 (m od Pm)- These are missing in may 4.1 ( 6 '*), since pm 6 S*. For each of these, we need at least one higher prim e for th e sum EpeTm+i(g') p to exceed 1. Again, r ^ + i( 6 *) > r ^ ( 6 ). CASE 2: 6 U{pm} is not normal. T hen the only successor of S in 6 ^ + 1 is S itself. Also, Tjn{S) = Tm+i{S) as the prim e Pm is not contained in either set. Therefore, rm{S) = rm+i{S). m This shows, among other things, th a t the sequence im is non-decreasing. It also shows th a t the values rjt+2 , - - - for all of the successors in 6 ^+1 , 6 ^4-2 , - -. of a given set 6 G 6 ^ do not fall below rk{S). If we want to com pute im and already know a bound I > im, then we do not have to look at any successor in the sets 6 ^4-1 , • • ■Sm of a set 6 € Sk w ith rk{S) > I. The n atu ral way to do this is iteratively. A lg o rith m 3.1 Take A i = 6 1 and let Ak+i consist of all successors in Sk+i o f all S e Ak with Tk{S) < I. Then im = m in{rm ( 6 ) | 6 E Am}If I is close to im, then this significantly reduces the num ber of sets to consider. The bound / can be chosen as the value of Vm{S) for some S G Sm- T he iterative m ethod saves the most tim e if one correctly guesses which sets have low values. By looking at prelim inary com putational results, the following seems to hold [8 ]. C o n je c tu r e 3.1 Let L 5 = {5,7}, and define Tk U { p k } ^ Tk U { p k } Lk otherwise Lk+l — ^ TAen, /o r m > 5, r,^(Tm) = z,?:. This conjecture holds true for m < 135. 64 norm ol 3.4 .2 G iu g a S e q u e n c e s Finding all sequences of a given length is not difficult, in theory, as all one is required to do is com pute the sets of all ^ > 1. To reach a th a t satisfy the inequality Giuga num ber whose sum minus product value is two requires a great deal more effort th an a num ber w ith sum minus product value of one. In fact, a proper Giuga sequence w ith sum minus product value of two requires at least 59 prime factors. Therefore, since no such Giuga num ber has been found (and it is not clear if one exists at this point), we will lim it our discussion to sequences w ith sum minus product value of one. Gomputing all sequences of a given length is difficult in practice. There are hun­ dreds of sequences of length 7, and because of the exponential growth of th e size of the sets, further com putations are im practical. Given an initial sequence of length m — 2 however, it is possible to find a Giuga sequence of length m. T h e o re m 3 .1 7 [8] Let A = {ai, 0 2 , . . . , <1 ^ - 2 } be any sequence o f length m — 2. Let 1 1 P = 0x02 ■■■Uj71-2; S = -----1-------[-.•• + Oj Ü 2 1 O - m - 2 Fix an integer v > S. Take any integers x, y with x ■y = P { P + S — v) and y > x. Let Then, 1 1 1 S H-----------1---------- —------------— V. ^m—1 ^ Hence, A U {üm -i, Um} = {«i, Ug,. . . , a ^ - 2 , dm-i,o-m} is a Giuga sequence i f and only if 1 G N. 65 Proof: We begin by showing th a t 1 S H 1 1 p 1 V. Clearly, ^ P (z, - g ) I 1 1 ( P "b as P(% --3) _ S) jP-bz ' P + % ^ f%P + %)CP-H&0 ^ if and only if P , P P (v-S ) + —------- vt :--------- m z -----r = 1 P +x P +y (P + x ) ( P + y) if and only if f) P + P +X P +y jp2-Z% (P + x ) ( P + y) which is of course true. This means th a t the extended sequence is Giuga if and only if b o th a ^ - i and a^n are integers. Now, a ^ - i is an integer if and only if is an integer. Because of symmetry, it is enough to show the im plication in one direction. If P ( u - ^ ) |( P + z), then P(n - ,9)|(P + z )(P + 2/) = 2P^ + (z + 2/)P - (u - ^)P, so P (n -^ )|(2 P ^ + (z + ?/)P) = P ( P + z + P + ^), so P ( u - g ) |P ( P + 2/) since P (v — S ) jP + x. 66 To show th a t {P{v - 5 ) ,P ) = 1 (which would prove the assertion), assume th a t this is not the case. T h at is, there exists a prim e p such th a t p \P {v - S) and p\P. So, p\üi for some i only because (o,, aj) = 1 when i ^ j . Since p divides P{v — S) = v P — (ng • • • am -2 + • • • + • • • Um-s), we can drop all term s on th e right hand side w ith a factor of a, to get p | ( a i • • • a j _ i • O j + i • • ■ a m - 2 ) which is a contradiction. ■ T h e o r e m 3 .1 8 [8] / / {ai, 0 2 , . . . , 0 ^ - 1 , Um} is a Giuga sequence with sum minus product V, and if we define X = ajn-iP{v - S) - P, y = amP{v - S) - P, (with P and S as in the previous theorem), then x and y are integers and X - y = P { P + S — v). P ro o f: Clearly, x and y are integers. It rem ains to show th a t x - y — P { P + S — v). We have X ■y — —P ‘^{v — S){am -i + am) + P^(am -iam )(u — S)"^ + P^ = P"^{S — v)am -iam {--------- 1 1 = P“ ^ {S — v)am -iam ----------- p + - P (P + P - u ) . 67 S — v) p'^ A counterexam ple to Giuga’s conjecture would have to be an odd number. Hence, no mem ber of a Giuga sequence (which is a counterexam ple) would be even. No such sequence has been found (counterexam ple or otherwise). We have th e following result, however, on the relationship between n and v [8]. P r o p o s itio n 3 .4 Let n = pip^ • • - Pm be an odd Giuga number. Then, m —V = 1 P ro o f: (mod 4). Consider the Giuga sequence equation: 1 1 1 H-------- + • ■ ■H-------------- ------ = V n P2 Pm Pi n n n — + — + • . . _l------------- - 1 = nv P2 Pm Pi 1 — The result follows from considering th e equation modulo 4. Indeed, assume th a t the first k factors are congruent to —1 modulo 4 and the other m —k factors are congruent to 1 modulo 4. Then, we have - 1 = v { - l Ÿ - k { - l Ÿ ^ ^ - (m - k ) { - l ) ’^ = ( - l) ^ ( u - m + 2k) It easily follows th a t m — v = —1 (mod 4). (mod 4). ■ In addition to being able to create Giuga sequences of length m from any sequence of length m —2, we also have an explicit m ethod of creating Giuga sequences of length m + 1 from a Giuga sequence of length m w ith a certain property [8]. T h e o re m 3 .1 9 Suppose a Giuga sequence {oq,. . . , am} satisfies Om — 0-1 ■■■Qm—1 1 and let O m — a i • • • O m — l T T Q 'm + 1 68 — ‘ ‘ ' l® m 1- TAeM, { &! , . . . , Om, Om+i} o Gmgo ggg^emce mYA (Ae gome at/m mm^ig pmdtfc( value. P ro o f: Let P = ai • • • o ^ - i and let S = l / o i + . . . l/o m -i- Then, a™ = P - 1, ôm = P + 1 and âm+i = P^ + P — 1. B oth sequences have the same sum minus product value if and only if S + P -1 __, = S + - J — + ^ P (P -l) P + 1 P2 + P - 1 ^ P ( P + 1)(P2 + P - 1 )’ which is true for all S and P . ■ Notice th a t the sequences derived from this theorem are not the only ones th a t exist. To find all of the sequences of a given length, we can use Theorem 3.17 or Theorem 3.1. For an explicit algorithm (due to Brown, Buck and H obart), see Appendix 5. 3.5 A g o h ’s C o n je c tu r e a n d R e la te d R e su lts This section will build on the results obtained in the study of the Eightfold way. The variations discussed here are due largely to Agoh. In fact. Theorem 3.20, of this section was originally found by Agoh in his paper “On G iuga’s C onjecture” [2]. Recall the two types of sums discussed in Section 3.2 ^ and ^ A:"". These two sums along with some Bernoulli num ber properties play a large role in w hat is to follow. Specifically, note: (I) Z.; = E k e Z..+1 i (k-i) where Pt(M) = r[p|n(I " + l)''B m +i-k, ^)^k (0 < * < m). 69 The next theorem takes advantage of these equalities. C onjecture 3.2 (A g o h ’s C onjecture) n € P i f and only i f n B n - \ = - 1 (mod n). T heorem 3 .2 0 A goh’s conjecture is equivalent to Giuga’s conjecture. Proof: (Agoh) Suppose th a t n is prime. Then by the von Staudt-C lausen Theorem, n B n - i — n {A n -i - ^ -) = -1 T) (mod n). Therefore, assume n is composite. Then E E fcGZ„_i fee Zn Notice th a t if p — l |n — 1, u B n - i is invertible modulo p. Further, if p — 1 /fn — 1, u B n - i is invertible m odulo p. Hence uB n-k, k > 3, is invertible modulo p for any prime factor p of n. Also, u B n -2 — 0 as n is odd. It is therefore clear th a t ^ - l) ^ (mod n). kÇz Z,t ■ In his paper, Agoh proved some im portant congruences involving Bernoulli num­ bers modulo prime powers [2]. P r o p o sitio n 3.5 Take n E E. Then fo r any prime factor p o f n : pBn_p = p - 1 (mod p^), pB(n/p)_i = p - 1 (mod p^), Cm; pB((^/p)_i)/p = p - 1 (mod p). P ro o f: Recall kS /cE Zn 70 k \k —1 Now, it is im m ediate from Corollary 3.2 on page 39 th a t for n G S and any a w ith p /o th a t = 1 (mod p^). Hence, we have E (m odp^ fee Z„ Clearly, however, = 0 and when k > 3, 1 /n - 1 ^ n '^ B n -k ^ O k \k —1 (mod p^). by the von Staudt-C lausen theorem. Thus, it m ust be the term pBn-p th a t is con­ gruent to p — 1 (mod p^). P a rts (ii) and (iii) can be found w ith a similar process. ■ We can now add to our knowledge of Giuga sequences. Define A to be any subset of the set of prime factors p of a fixed n G S. The next result (due to Agoh) follows w ithout a large am ount of work. T h e o re m 3.21 Let M = M (A ) = Y[p^\P o,nd t — ((A) be the number o f elements in A. I f n G S , then In particular, 1 _ p ,n - 2 n - = (-1 )* “ ^ (mod n), p\n wAere g za (Ae number o /p n m e /octora o /n . P ro o f: Since n G E, it m ust be the case th a t (p — l) |( n — 1) for all p G A. Prom the von Staudt-C lausen Theorem (Theorem 2.10), we have E —l (mod M f 71 Recall also th a t Since this sum is congruent to 0 (M ) (mod M ), and (m od a/ ) , for /c > 2, it follows th a t = = - ( VpeA m ^ / V ) (mod M), peA ^/ which shows the first congruence (from Corollary 3.3 page 39). W hen A4 = n, the second result follows from the first w ith the use of Corollary 3.5. 3.5.1 ■ G iuga Q uotients If Giuga’s conjecture is true, then like W ilson’s theorem, it would be a useful num ber theoretic tool. Therefore, we shall continue studying G iuga’s conjecture in the same way as W ilson’s theorem. One particular aspect of W ilson’s theorem th a t has been studied is w hat are known as W ilson quotients. This section will discuss Giuga quotients and other related quotient values. These results are due to Agoh and can be found in his paper “On G iuga’s C onjecture” [2]. D efinition 3.9 Define the following fou r quotients: (I) Qpia) = {p fa), the Fermat Quotient of p. (II) q{a,n) = — ((u, n) = 1), the Euler Quotient o fn . (III) C {a,n ) = (n G F, (a, n) = 1), the Carmichael Quotient o f n . (IV) Gp{a,n) = {n G S, p\n, p fa), the Giuga Quotient o f n . 72 P r o p o s itio n 3.6 With a ,p and n and b as allowable values from Definition 3.9, %(o6) = + %(6) (mod p) q{ab, n) = q{a, n) + q[b, n) (mod n) C{ab, n) = C{a, n) + C{b, n) (mod n) Gp{ab, n) = Gp{a, n) + Gp{b, n) (m od p^). It can further be shown [2] th a t G iuga’s conjecture is equivalent to saying Gp(a, n) = 0 for all bases a w ith p fa. Before we proceed to derive properties pertaining to Giuga quotients, we require some background. The first result is due to Lerch [26]. P r o p o s itio n 3 .7 I f n > 2 and a are integers with {a,n) = 1, then q { a ,n ) = ^ k 2. Define J {m ) = 73 Further, define Otherwise 1 Then denote: (V) Wp = ---~ p (p is prime), ■ (VI) W {m ) = , the Wilson Quotient o f p, the Generalized Wilson Quotient o f m. As is the case with the previous four quotients, (V) and (VI) are b o th integers and can be shown to have th e following congruences hold. T he proofs of these can be found in [3]. P rop osition 3.8 £rn4>{T^)Fd{m) = g(o, TTi) ^ (mod 77%). a < m —l (a,m )= l and if p is an odd prime. p-1 % ^ ^ % (a) (mod p). a= l P rop osition 3.9 (V oronoi’s C ongruence) Let t > 1, m > 2 and a be integers w ith { a ,m ) = l. Then, m k< m ~ 1 m Now, by using the above tools, we can make the following two assertions about Carmichael and Giuga quotients. P rop osition 3.10 I f n ^ T and (a,n) — 1, then ^(n)C(o, n) = (n — l)g(o, n) 74 (mod n). Also, i f n e T > , p\n and p )[a, then (p - l)Gp(o, M) S Proof: (mod p). Take m = n and t = n — 1 in Proposition 3.9. Then C(a, n) T ^ f" = («-!) ak n T k < m —l ( k , m) =\ (mod n). Since n e r , and (oA;)” 1 (mod n). = — The result now follows from Proposition 3.7. In a similar way, take m = p^ and f — n —p in Proposition 3.9, then n-p+l , I (n-p G p(n,n) ^ ak (a^)" ^ ^ p3 = (^ - P) ^ (fc,p)=i Since, n € E, we have n-p+l (-p-ri - y X Hence, n-p-l = — AK (mod p^). Now, by Proposition 3.7, this implies th a t (p - l)Gp(a,M ) = ^ ^ -^ g (n ,p ^ ) 75 (m od p). (mod p^). If q{a,p^) = qp{a) (mod p), we are done. To verify this, note th a t since p is odd, (^i = 0 (mod p) for every i > 2 . It follows th a t _1 g(a,.p ) p3 = %(d) (mod p), hence showing all of the required elements. Corollary 3.15 I f n E T , then C {a,n) = —enW {n) (mod n). a n is square-free. Corollary 3.1 Borwein n G E if and only if p^(p — 1) | (n —p) for any prime divisor p of n. Corollary 3.2 Agoh If n G E, then (0(n), n) = 1. Corollary 3.3 Agoh n G E and is composite if and only if n G F and n £ Q. Theorem 3.2 Borwein A finite increasing sequence of integers { o i , . . . a ^ } sat­ isfies Oj \ a\ • • • a,_i • Qj+i ■• • üm — 1 Theorem 3.3 Borwein Corollary 3.4 Borwein Corollary 3.5 Agoh for every i < m if and only if it is a Giuga sequence. n is a Giuga number if and only if ^ - Hp|„ ^ E N. n G E if for any prime factor p of n n (mod n). ^ = 1 Table 11: G iuga’s Conjecture Results 81 R esult D ocu m en t R eference D ue To Let m be a fixed natural number. Then there exist only finitely many Giuga sequences of length m. Proposition 3.1 Buck, H obart Define Corollary 3.6 Buck, H obart If {oi, U 2 , . . . , t t m } is a Giuga sequence w ith sum minus product X, then m > o p r . Corollary 3.2 Buck, H obart Let m be a fixed n atural num ber and suppose th a t {ui, ...Urn} is a Giuga sequence. Then for any j such th a t Ui + 1 j > 0 , a j < - - i j + i ■ Theorem 3.4 Buck, Hobart Suppose P = { p i , P 2 . . . P m } is a norm al family of primes and let n = p i P 2 ■ ■ ■P m - Then there is a unique group of order n up to isomorphism. Theorem 3.12 Wong If n is divisible by primes p t ^ P j for which P i \ p j — 1, then there exists a non-cyclic group of order n. Note: p, and P j need not be distinct, thus n is necessarily square-free. Theorem 3.13 Wong Let P = { p i , P 2 , . . . , P z } be a norm al family of primes, and define r, = l c m , ^ j ( p j ) . Then any num ber of the form p ^ ’^*P2^^^ • • -p/^' with k e is pseudoCarmichael. Conversely, if n is pseudo-Carmichael, then its prime factors form a norm al family. Theorem 3.14 Wong {a € = N |a is an element of a Giuga sequence of length m} Then, for any fixed m G m has a m axim al element. 82 D ocu m en t R eference D u e To n is co-Giuga if and only if Theorem 3.15 Wong There are no non-trivial co-Giuga num bers w ith fewer than 7695 prime factors. Theorem 3.16 Wong R esult I r Zn n —1 Zn n —1 n —1 Zn (^(n) <^(n) Zn <^(n) n —1 z: z; n —1 n —1 <^(n) <^(n) <^(n) n —1 <^(n) n —1 z; m Conditions on n Trivial cases Non-Trivial examples Gor. Giuga Primes 3.7 Giuga and Carmichael Go-Giuga None 30, 858, 1722, etc. > 13,800 digits > 7694 Prim e Factors > 7694 Prim e Factors Odd, CoGiuga and PseudoCarmichael Prime Prime All n e N Odd and PseudoGar michael Prim e powers Odd Powers Prime Primes Primes All n e N Odd Prime Powers 83 3.8 3.9 3.10 None None None Carmichael Numbers, 45, 225, 325, . . . 3.11 3.12 3.13 3.14 Table 10 Wong D ocu m en t R eferen ce D ue To Theorem Borwein Let n — P 1P2 • ■- Pm be an odd Giuga number. Then, ra —u = 1 (mod 4). Proposition 3.4 Borwein Take a Giuga sequence of length m , which satisfies oi • • • am-i — 1. Then, let Theorem 3.19 Borwein (Agoh’s Conjecture) n e E if and only if nR „_i (mod n). Theorem 3.2 Agoh Take n G E, then for any prime factor p of n\ (i) pBn-p = p - 1 (mod p^), (ii) pB(n/p)-i = p - 1 (mod p^), (iii) pB((n/p)-i)/p = p - 1 (mod p). Proposition 3.5 Agoh R esult Take an initial sequence of length m — 2. {oi, 0 2 , . . . , am - 2} be such a sequence. Let Let A = h • ■• H . P = 0^02 ■• • am—2) S = -----1 Oi O2 am-2 Fix an integer v > S. Take any integers x, y w ith x - y = P { P + S — v) and y > x. Let P +X Q-rre— 1 — P{v - S) ' P +y dm — Then, 1 1 am—I am V. l^m Hence, A U {am—it am} — {^ 1 , *^2 , • • •, am—2 , am—it am} 1® a Giuga sequence if and only if 0 ^ - 1 G N. — O] ■ ■ ■O m —1 T 1, a m - \- l a i • • • O m —l ^ m = 1- Then, { o i , . . . , 0 ^ ,- 1 , Om,Om+i} is a Giuga sequence with the same sum minus product value. R esult D ocu m en t R eferen ce D u e To Let M = Af(A) = 1 p and t = t{A) be the num ber of elements in A. If n G S , then Theorem 3.21 Agoh ............. — In particular, n i_ = ( ' (mod n), where s is the num ber of prim e factors of n. 85 " A p p e n d ix 2: M o d ern P rim a lity T ests T heory Ref. p prim e <=> M (z — a)P = {xP — a) (mod p) P epin’s [37] Theorem 1. N am e AKS Test 2. Pépin Test 3. Pocklington Pocklington’s Theorem Test [11] 4. P ro th Test P ro th ’s Theorem [36] 5. SelfridgeHurwitz Residue Test W ard’s Prim ality Test P epin’s Theorem [54] Let Rn = composite, n > doesn’t vanish. Lucas Sequences [37], W ilson’s The­ orem [36] Take N odd and assume there is a Lucas sequence {Un} w ith associated Sylvester cyclotomie num bers {Qn} such th a t there is an n > ^ /N , (A, n) — 1, for which A |Q „. Then, A is prime unless it has one of the following forms N — {n — 1)^, w ith n — 1 prim e and n > 4, or A = n^ — 1, w ith n — 1 and n + 1 prime. A is prime iff (A —1)! = —1 (mod A ). 6. 7. W ilson’s Test A lgorithm {x — a ) ^ = ( x ^ — a) (mod x^ — I, N ) implies N prime. Take n > 2 and k > = —1 (mod Fn), then 4* = - 1 and is prime. Let p be an odd prim e and select k so th a t 1 < A: < 2{p + 1) and p J\k. Set N = 2kp + 1. Then, N is prim e iff gcd(a^ -L 1, A ) = 1. N — k ■2^ + 1, w ith /c < 2” odd, is prime if there is an integer a such th a t q(-'V-1)/2 = jY) Table 12: M odern Prim e Tests 86 (mod F„). is 5, if R» (mod 2^®) 8. T heory N am e D iophantine Prime D iophantin^ Equations Equations Ref. [52] A lgorithm k + 2 is prime iff there is a solution in to th e following system: wz + h + j —q = 0 (^gk + 2g + /c + l ) ( h + j ) + /r — z = 0 16(& + + 2)(n + 1)^ + 1 - f = 0 2n + p + l + z — e = 0 e^(e + 2)(a + 1) + 1 — (a^ - l ) y ‘^ + 1 - = 0 = 0 16r^?/‘^(a^ — 1) 4-1 — —0 n + l + v —y = 0 (a^ - l)/2 + 1 ai k m 0 \ — I —i — 0 {[a + u^{u^ - 1)]^ - l} (n + M y Y + 1 —(x + c u Y = 0 b(2ct,Ti 4" 2(3 —Ti — 2ti — 2) —tti 4- p4* l{a — n — 1)= 0 s{2(xp 4 ” 2 c l — p — 2p — 2 ) — x 4~ g~\~ ?/(a - p - 1) = 0 z + pl{a — p) t{2ap — — 1) — pm = 0 LucasLehmer Test Lucas Sequences [1 1 ] Let A 4-1 = rij= i Q/ w ith % are prime factors and (3j their respective pow­ ers. If there exists a Lucas sequence 17^ such th a t gcd{U{N=i)/qj,N) = 1 V j = 1 . . . n and = 0 (mod A ), then A is prime. 87 N am e T h e o ry R ef. A lg o rith m 10. Probenius Test Ring Theory (371 11. AGKM Certificate Elliptic Curves; Goldwasser and Kilian Theorem [45] 12. P ra tt Cer­ tificate F erm at’s Little Theorem Converse [11] Select = —1 and ( ^ ) = 1. If (mod (n, — bx — c)) E Z /N Z , (mod {N ,x ^ —bx —c)) = —c, if — 1 = 2^s where s odd, and x'* = 1 (mod n, x"^ — bx — c) and x^^^ = —1 (mod n , x ‘^ —bx —c )y j < r —1, then A is a probable prime. The certificate consists of a list of 1. A point on an elliptic curve C: = x^ + g 2^ + 93 (mod A ) for some num ­ bers 92 and 93 . 2. A prim e q w ith q > (A^/^ + 1)^ such th a t for some other num ber k and m = kq w ith A; f 1, m C { x , y , 92 , 9 s , N ) is the iden­ tity of th e curve, bu t k C (x, y, 92 , 93 , A ) is not. Then A is prime. Take A E Z+ and {Pj} the set of prime factors of A — 1. Suppose there exists X E Z+ such th a t x ^"^ = 1 (mod A ), b u t X® ^ 1 (mod n) whenever e is one of (n — l)/p j. Then A is prime. 88 N am e Euler Test T heory Ref. E uler’s C riterion [25] 2. Ferm at Test F erm at’s Lit­ tle Theorem [13] 3. M iller’s Test F erm at’s Lit­ tle Theorem [51] 4. BailliePSW Prim ality Test Strong psp; Lucas psp [31] 5. RabinMiller Test Strong PSP [13] 1. A lgorithm If N is prime, then = (^ ) (mod N ) where (a|p) is th e Legendre symbol (the converse need not hold). Select a € Z+ then if N is prime = 1 (mod N ) (the converse need not hold). Assume the extended Riem ann hypoth­ esis is true, then if N is an a-SPSP for all integers a w ith 1 < a < 2(logn)2, then N is prime 1. Perform a base 2 psp test on N . 2. Given the sequence 5, —7, 9, —1 1 ,1 3 ,..., find the first num­ ber D for which ( ^ ) = —1. Then per­ form a Lucas PSP test w ith discrimi­ nant D on N . If N passes b o th tests, A is a probable prime. Given N — 2^s + 1 w ith s odd, chose a < N — 1. Ifa* = l (mod n) or = —1 (mod n) for some j < r — 1. Then, N is probably prime. Table 13: M odem Pseudo-prim e Tests 1. 2. 3. 4. N am e T heory Ref. G iuga’s Conjecture Agoh Conjecture AgohGiuga Conjecture F erm at’s Lit­ tle Theorem Bernoulli Numbers Equivalence of Giuga and Agoh Conjectures FeitThom pson Theorem [8] (mod N ) N is prime [8] = —1 (mod A ) A is prime FeitThom pson Conjecture A lgorithm [23] Epiw , ü,-i)|(w-i) T = 1 (mod A ) 4::^ A is prime. [44] For no primes p ,q > 400,000 do (p® — l ) / ( p — 1) and {qP — l) /( g — 1) have a common factor. Table 14: Prime Num ber Conjectures 89 N am e Ref. Eratosthenes [11 ] Number Field Sieve [29] A lgorithm Begin w ith a list of num bers up to N . Begin by crossing off all m ultiples of 2 th a t are larger th an 2. Next move to the next num ber th a t is not crossed off. Cross off all m ultiples of th a t num ber b u t greater th a n it, th a t are not crossed off. R epeat this until you reach [\/N J . The rem aining num bers are prime. Chose r , e , s G Z. Let n = — s, where s is small. Now, select an extension degree d G Z+. Given d, we proceed by selecting A: E Z+ (the smallest integer) such th a t kd > e, so th a t (mod n). Now, let f{X ) = — c e Z[X], Now, for a reasonable choice of d, any factor of / is also a nontrivial factor of n. So, assume th a t / is irreducible. So, we can now define a num ber field Q (a ) where a satisfies / ( a ) = 0. We let $ denote the ring homomorphism from Z[a] to Z / n Z th a t sends o- to m (mod n). The idea is to look a t pairs of small co-prime integers a, b such th a t b o th a + ah and a + mb are sm ooth. Because M 6 ^ 0 (mod p 1) (modp) k(v-l)+b-l)^k(p-i)+b ^ \r^n-l/ J k(p~l)+b — Z^r=0\ Ireland and Rosen [22] Sun [42] .s n _ i_ p /k -l-r \/k ) [n-l^rJirJ Sun [42] (modp”) Table 17: Number Theoretic Congruences 95 R e fe re n c e C o n g ru e n c e For A: G {1, 2 , . . . — 4}, r Sun [42] (mod p^) l (m od / ) if k is odd if A; is odd Sun [42] ZCi = ( 2 - 3Bp+i)p - (mod p^) ZC i = - ( 2 - pBp_i)p - §p^ (mod p^) Sun [42] Y llZ \ = p B 2p-2 - 3pBp_i + 3(p - 1) (mod p^) Sun [42] Let k < p then, ( j^ p g p _ i _ t (mod p^) ^ Sun [2000] if A: < p - 1 { [ -p 5 p _ i + 2(p — 1) (mod p^) if A; — p — 1 96 A p p en d ix 4: A lg o rith m s G iu g a S eq u e n c es Since we know th a t there are only finitely m any Giuga sequences of a fixed length and we can bound each term , we have the following algorithm to com pute Giuga sequences of a fixed length by brute force (Thanks to Jed Brown and Julian Buck (personal communications) for their help w ith the algorithm ). # include #include const unsigned N = 6; const double omega = 1.0el2; const double epsilon = le-13; int g_count ; inline void printStackC unsigned * s , unsigned level, double sum, double overshoot ); void n e x t ( unsigned [], double sum, unsigned prod, unsigned level ); int m a i n O { g_count=0; unsigned stack[10]; stack[1] = 2; stack[2] = 3; double sum = 1.0/2.0 + 1.0/3.0; next( stack, sum, 6 , 2 ) ; printf( "count = % i \n", g_count ); return 0; inline void n e x t ( unsigned * s, double sum, unsigned prod, unsigned level ) { double overShoot = sum-1-(1.0/prod); if ( overShoot > epsilon ) return; if ( sum > 1 ) { if ( overShoot > -epsilon ) printStackCs,level,sum, overShoot); return; } if ( level == N ) return; double upperBound = ( (N - level)*prod ) / ( prod*(1.0-sum) ); if ( upperBound > omega ) return; //printf( "Current Stack is: " ); //printStackC s, level, sum, overShoot ); //printf( "upper bound is; % f \n", upperBound ); for ( unsigned i=s[level]+1 ; i < (unsigned)ceil( upperBound ) ; ++i ) { s[level+l] = i ; next( s, sum+(1.0/i), prod*i, level+1 ); } 97 } inline void printStackC unsigned s[], unsigned level, double sum, double overShoot ) { g_count++; for ( unsigned i=l ; i<=level ; i++) printf( "%i ", s[i] ); printf( " sum= %f overShoot= %e \ n " , sum, overShoot ); } N o ta tio n a l C on ven tion s Symbol N P Bn En -G nW E »(0) (W s r G g(a,n) C(o, n) Gp((z,n) Definition C hapter 1 N atural Numbers: { 0 , 1 , 2, . . . } Positive Integers: { 1 , 2 , 3 , . . . } Set of Primes: {2,3, 5, 7 , 1 1 , . . . } C hapter 2 The Bernoulli Num ber The Bernoulli Polynomial The denom inator of x The Euler Number The Euler Polynomial The C onstant Term of Euler Polynomial The Riem ann Zeta Function C hapter 3 = - 1 (niod 7i)} The Set of Carmichael Numbers {n\p\{n/p - 1 ) V j 9 | n } Eermat Q uotient of p Euler Q uotient of n Carmichael Q uotient of n Giuga Q uotient of n Table 18: N otational Conventions 99 R eferen ces [1] M. Abramowitz, I. Stegun, Handbook o f Mathematical Functions, Ddver, New York, 9th edition, 1972. [2] T. Agoh, “On G iuga’s Conjecture” , Manuscripta Mathematica, 87 (1995), 501 - 510. [3] T. Agoh, K. Dilcher and L. Skula, “W ilson Q uotients for Com posite M oduli” , Math. Comput. 67 (1981), 843-861. [4] M. Agrawal, N. Kayal and N. Saxena, “Prim es in P ” , Preprint, 2002. http: / / w w w .cse.iitk.ac.in/prim ality.pdf. [5] W. Alford, A. Granville and C. Pomerance, “There are Infinitely Many Carmichael N um bers.” Ann. Math. 140 (1994), 703-722. [6] E. Bedocchi, “N ota ad una congettura sui numeri prim i” , Riv. Mat. Univ. fo r m a (1985), 11, 229-236. [7] N. Beeger, “On some new congruences in the theory of Bernoulli num bers” , Bull. Amer. Math. Soc., 44 (1938), 684-688. [8] D. Borwein, J. Borwein, P. Borwein and R. Cirgensohn, “C iuga’s Conjecture on Prim ality” , Amer. Math. Monthly (1996), 103, 40-50. [9] J. Borwein, D. Bradley,and R. C randall “C om putational strategies for the Riemann zeta function” , J. Comput. Appl. Math. (2000), 121, 247-296. [10] R. Brent. “An Improved Monte Carlo Factorization A lgorithm ” , Nordisk Tidsknft fo r Informationsbehandlung (B IT ) (1980), 20, 176-184. [11] D. Bressoud, S. Wagon, Computational Number Theory, Key College Publish­ ing, 1999. 100 [12] J. B rillhart, D. H. Lehmer, J. Selfridge, S. S. Wagstaff, and B. Tuckerman “Factorizations of , fe” ± 1, b = 2, 3,5,6, 7 ,1 0 ,1 1 ,1 2 Up to High Powers” , rev. ed. Amer. Math. Soc. Providence, Rhode Island (1988), 2nd edition. [13] J. Buchm ann, Introduction to Cryptography, Springer-Verlag, NY, 2000. [14] R. Carmichael, “A Note on a New N um ber Theory Function.” Bull. Amer. ^oc. (1910), 16, 232-238. [15] Carrier, Wagstaff, “Im plem enting th e Hypercube Q uadratic Sieve w ith Two Large Prim es” Center fo r Education and Research in Information Assurance and Security, 2003. [16] R. Crandall, Topics in Adanced Scientific Computation, Springer-Verlag, New York. 1996. [17] J. Dixon, “Asym ptotically Fast Factorization of Integers” , Math. Comput. (1981), 36, 255-260. [18] H. Dubner, “Carmichael numbers of the form (6/c 4- 1)(12A; 4- l)(18/c 4- 1)” Journal o f Integer Sequences (2002), 5. [19] J. Gallian, Contemporary Abstract Algebra, Houghton Mifflin, Boston MA, 2002. [20] G. Giuga, “Su una presumibile propriété caratteristica dei numeri prim i” 1st. Lombardo Sci. Lett. Rend. A (1950), 83:511-528. [21] R. Guy, Unsolved Problems in Number Theory, New York, Springer-Verlag, 1996. [22] K. Ireland, M. Rosen. A Classical Introduction to Modern Number Theory, Springer-Verlag, New York, 1990. [23] B. Kellner. “Über irregulare Paare hoherer O rdnungen” , Diplomarbeit. Math. Institut der Ceorg August Universitdt zu Gottingen (2002). http://w w w .bernoulli.org/ bk/ irrpairord.pdf. 101 [24] A. Klappenecker, “The AKS Prim ality Test; Results from Analytic N um ber Theory", (2002), NP. N. Koblitz, A Course in Number Theory and Cryptography, Springer-Verlag, New York, 1994. [26] M. Lerch, “Zur Theorie des Ferm atschen Q uotienten Annalen (1905), 60, 471-490. ^ ^ = g(a)” , Math. [27] M. Morrison, J. B rillhart, “A M ethod of Factoring and the Factorization of Fy", MoÉ/i. (1976), 29, 183-205. [28] R. Pinch, “T he Carm ichael Numbers up to 10^®” , Math. Comput., 61 (1993), 381-391. [29] J. M. Pollard, “A Monte Carlo M ethod for Factorization” , BIT, 15 (1974), 331-334. [30] J. M. Pollard, “Theorems on Factorization and Prim ality Testing” , Proa. Cambridge Phil. Soc., 76 (1974), 521-528. [31] C. Pomerance, “Are there Counterexam ples to the Baillie - PSW Prim ality Test?", NP, 1994. [32] C. Pomerance, “The Cyclotomie Ring Test of Agrawal, Kayal and Saxena” , Preprint, 2002. [33] C. Pomerance, J. L. Selfridge and S. Wagstaff, “The Pseudoprim es to 25 -10^” , Math. Comput. 35 (1980), 1003-1026. [34] M. Rabin, “Probabilistic Algorithms for Testing Prim ality” , Journal of Number r/ieon/, 12 (1980). [35] H. Rademacher, Topics in Analytic Number Theory, Springer-Verlag, New York, 1973. 102 [36] P. Ribenboim, The Little Book of Big Primes, New York, Springer-Verlag, 1991. [37] P. Ribenboim, The New Book of Prime Number Records, New York, SpringerVerlag, 1996. H. E. Rose, A Course in Number Theory, Oxford Press, Oxford, 1994. [39] M. Rosen, Elementary Number Theory and its Applications, Addison Wesley Longman, O ntario. 2000. [40] W. Rudin, Principles o f Mathematical Analysis, McGraw-Hill, 1996. [41] H. Stark, A n Introduction to Number Theory, Cambridge, M IT Press, eleventh printing, 2001. [42] Z. H. Sun, “Congruences for Bernoulli num bers and Bernoulli polynomials” . Discrete Math., 163 (1997), 153-163. [43] Z. W. Sun, “General Congruences for Bernoulli Polynom ials” , Discrete Math., 262 (2003), 252-276. [44] N. M. Stephens, “On the Feit-Thom pson Conjecture.” Math. Comput., 25 (1971), 625. [45] É. W. Weisstein, “Atkin-Goldwasser-Kilian-M orain C ertificate” , M athW orld-A Wolfram Web Resource. http: / / mathworld.wolfram.com/Atkin-Goldwasser-KilianM orainCertificate.htm l From [46] F. W. Weisstein, “Bernoulli N um ber” , From M athW orld-A W olfram Web Resource. http: / / m athw orld.w olfram .com /BernoulliN um ber.htm l [47] E. W. Weisstein, “Bernoulli Polynom ial” , From M athW orld-A Wolfram Web Resource. http: / / m athw orld.wolfram .com /BernoulliPolynom ial.htm l 103 [48] E. W. Weisstein, “Euler’s Factorization M ethod” , From M athW orld-A Wol­ fram Web Resource. http: / /m athw orld.w olfram .com /E ulersFactorizationM ethod.htm l [49] E. W. Weisstein, “Excludent Factorization M ethod” , From M ath W orld-A Wolfram Web Resource. http: / / m athw orld.w olfram .com /ExcludentFactorizationM ethod.htm l [50] E. W. Weisstein, “Legendre’s Factorization M ethod” , From M athW orld-A Wolfram Web Resource. http://m athw orld.w olfram .com /L egendresFactorizationM ethod.htm l [51] E. W. Weisstein. “M iller’s Prim ality Test” , From M athW orld-A W olfram Web Resource. http: / / m athw orld.w olfram .com /M illersPrim alityTest.htm l [52] E. W. Weisstein. “Prim e D iophantine Equations” , From M athW orld-A Wol­ fram Web Resource. h ttp ://m a th w o rld .w olfram .com /Prim eD iophantineEquations.htm l [53] E. W. W eisstein, ” Riem ann Zeta Function” , From M athW orld-A Wolfram Web Resource. http://m athw orld.w olfram .com /R iem annZ etaFunction.htm l [54] E. W. Weisstein, “Selfridge-Hurwitz Residue” , From M athW orld-A Wolfram Web Resource. http: / / mathworld.wolfram .com /Selfridge-HurwitzResidue.htm l [55] E. W. Weisstein, ”Vandermonde M atrix” , From M athW orld-A W olfram Web Resource. http: / / m atliworld.wolfram .com /Vanderm ondeM atrix.htm l H. C. Williams, “A p -h 1 M ethod of Factoring.” Math. Comput. 39 (1982), 225-234. [57] E. Wong, “C om putations on Normal Families of Prim es,” Unpublished. (SFU M asters Thesis), 1994. 104 [58] S. Zhang, J. Jin, Computation o f Special Functions, Jo h n Wiley and Sons, Inc, New York, New York. 1996. 105