`> `
**# UCC_2000.mws**

**A Prime For The Millennium -**

primality testing with particular emphasis

on Henry Cabourn Pocklington (1875 - 1952)

A talk given to the student mathematical society of

University College Cork on Thursday 23rd. March 2000

**John Cosgrave, St. Patrick's College,**

Drumcondra, Dublin 9, IRELAND.

**[email protected] **

http://www.spd.dcu.ie/johnbcos

**For **
**T**
**im **
**and**
** **
**M**
**airead Robinson of **
**F**
**olding **
**L**
**andscapes**

**(http://www.iol.ie/~tandmfl)**

**whose idea it was to publish **
**A Prime For The Millennium**

(an explanatory email to my niece Jo and nephew Ben)

**I have adopted, as the title of my talk tonight, the title of my recently published booklet **
**A Prime For The Millennium**
** (my royalties for the Irish Cancer Society). This booklet began its life as an email written to my young niece and nephew, Jo and Ben Hartley. Just how that private email came to pass into the public domain as a booklet may be read about in the Millennium**
**prime booklet section of my web site. How a painting by **
__Tom Marine__
** (a Leeds-based artist) of the booklet cover (designed by **
__Simon Cutts and Tim Robinson__
**) came to be sold to **
__Turlough Sheehan__
** of Consolidated Distribution Systems for the benefit of the Irish Cancer Society and the NSPCC (UK), may also be read about at my web site. **

**The cover of the booklet - a gif file copied and pasted into**

this Maple worksheet - is best viewed in the html version:

**I wish to thank **
__Turlough Crowe of Allied Irish Banks,__
** **
__Elaine Bragg of Adept Scientific__
** (http://www.adeptscience.co.uk), **
__Charlie Hipwell of Pfizer__
**, and **
__Gerry McGovern of Nua__
** (http://www.nua.ie) who generously sponsored copies of the booklet for distribution this evening. **

Anyone reading this abroad (or here in Ireland) may obtain a copy (or copies!) by contacting Folding Landscapes at their web site (http://www.iol.ie/~tandmfl). There was a print run of 2000, so hurry hurry while stocks last! Of public reaction to the booklet I was especially pleased with an email forwarded to me by Tim Robinson last December 23rd:

**Dear Tim Robinson,**

>

>As a mother of two small kids you would think (quite rightly)

>that I would be mad busy on the eve of Christmas Eve; well

>since we found the time from nowhere to greet the dawn at

>Newgrange on Tuesday I thought I would steal some time

>to read your beautiful publication 'A Prime For The Millennium'

>which I bought for my brother-in-law who is a number whiz..

>

>What a delight; I thought that I was numerically illiterate

>but I saw the poetry in John Cosgrave's work. If I was a

>number I would definitely want to be a Prime. Please convey

>my thanks to him for his enthusiasm; I now have something

>numerical to feed my babies with when they are older.

The MapleV5 file of this talk may be accessed in the Public and other lectures section of my web site. The
**html**
** text version of that file - for anyone who doesn't have Maple - may also be accessed (note that because Maple saves outputs and in-line mathematical expressions as gif files, then there are hundreds of gif files in the html version).**

`> `
**2^57171 mod 797979; # computes the remainder 2 to the power of 57171 leaves on division by 797979**

`> `

**I would like to point out how remarkable - relatively speaking - a computation that was!! **

To perform it, Maple
**actually evaluated**
** **
**, and **
**then**
** divided by 797979 to produce the remainder 70715. **

And here is the
**actual value**
** of **
** (a 17211 digit number):**

`> `
**2^57171;**

`> `

**However I will soon wish to carry out modular exponentiation computations involving **
**much larger numbers**
**, computations like these:**

** mod **
**n**
**, (**
**, ... ) and **
**quite large**
** values of **
**n**
**. **

For example:

`> `
**a := 2;**

`> `
**n := 98765432123456789876543211111111111111111111111111;**

`> `
**a^(n-1) mod n;**

`Error, integer too large in context`

`> `

**However there is a very elementary, but incredibly powerful method (known as the **
**square-and-multiply**
** method) which enables such calculations to be done extremely quickly, and here is the Maple command for the above computation to be done:**

`> `
**a&^(n-1) mod n;**

`> `

**You will see shortly **
**why**
** such computations are so vital (and, incidentally, see - instantly, and remarkably - that as a result of the just performed computation we may conclude that **
** is **
**not**
** prime).**

[Remark. Maple's apparent speed of modular exponentiation is completely outclassed by much more powerful (and free!) programs as
__Yves Gallot's Proth.exe__
**, or **
__Chris Nash's related PrimeForm__
**.]**

`> `
**p1 := 71; # a small prime**

`> `
**103^(p1 - 1);**

`> `
**103&^(p1 - 1) mod p1;**

`> `
**2&^(p1 - 1) mod p1;**

`> `
**10&^(p1 - 1) mod p1;**

`> `
**142&^(p1 - 1) mod p1;**

`> `

**(I hope you see why that '0' appeared.) Now I would like you to see how Fermat's 'little' theorem may be used to **
**quickly establish**
** that a number is composite (i.e., is not prime). I will deliberately make up a number which is **
**not**
** prime, by multiplying two large primes together (the resulting number could **
**not**
** be quickly shown to be **
**not**
** prime by using the method of Eratosthenes):**

`> `
**p2 := nextprime(9876543009887765498720);**

`> `
**q2 := nextprime(10000*p2 + 999999999999999);**

`> `
**n2 := p2*q2;**

`> `

**and then the instantaneous computation: **

`> `
**2&^(n2 - 1) mod n2;**

**shows that n2 is not prime. You see why?**

In fact a
**non unity output**
** will **
**almost certainly**
** result from (almost!) any large **
**random**
** choice (the probability of a large random number being prime is quite small; that's an interpretation of the Prime Number Theorem). In the saved text I can only have one 'choice' shown, but during my live lecture I will re-execute the the 'rand' commands to see a few different 'choice' values (this cannot be reproduced by someone having only the html version):**

`> `
**?random**

`> `
**rand();**

`> `
**rand();**

**In the following - where there are five **
**different**
** random numbers being used - the coefficients c1 and c2 are simply to **
**ensure**
** (and you see how?) that 'choice' is **
**not**
** divisible by any prime from 2 to 97 (the 25th prime):**

`> `
**c1 := product(ithprime(k), k=1..25);**

`> `
**c2 := c1^2;**

`> `
**choice := c1*rand()*rand()*rand() + c2*rand()*rand() + 1;**

`> `
**2&^(choice - 1) mod choice;**

`> `

**and so - as you will see, **
**almost certainly**
** - 'choice' is **
**not prime**
** (I hope I don't have bad luck on the night!). **

[Of course, if we successively re-executed the previous two commands
**often enough**
** we would **
**eventually**
** - **
**almost certainly**
** - get a second output of '1.' And so? Well, you have to see what's coming up next...]**

**Now I give another (**
**not random**
**!) computational example [see Appendix for further details]:**

`> `
**c := 1195068768795265792518361315725116351898245581;**

**Let us observe how it fairs with respect to Fermat's little theorem:**

`> `
**2&^(c - 1) mod c;**

`> `
**3&^(c - 1) mod c;**

`> `
**5&^(c - 1) mod c;**

`> `
**7&^(c - 1) mod c;**

`> `
**11&^(c - 1) mod c;**

`> `
**13&^(c - 1) mod c;**

**Those 1's **
**continue**
** being produced **
**until**
** one reaches:**

`> `
**37&^(c - 1) mod c;**

`> `

**then **
**n**
** is prime. An illustrative example:**

`> `
**example1 := 29:**

`> `
**a1 := 2:**

`> `
**a1^(example1 - 1) mod example1;**

`> `
**seq(a1^r mod example1, r = 1..(example1 - 2));**

`> `

**Those computations show that:**

1.
** (mod 29), and**

2.
__none__
** of **
**, ... , **
** leaves remainder 1 on division by 29**

**and thus 29 is a prime. However it is obvious that the amount of computation is **
**worse**
** that would be required with Eratosthenes!! Lucas observed (in 1878) the following improvement: Let **
**n**
** be a natural number, and suppose there is an integer **
**a**
** such that**

1.
** (mod **
**n**
**), and**

2.
** (mod **
**n**
**) for all **
__divisors__
** r**
** of (**
**) with **
** < **
** **

**then **
**n**
** is prime. An illustrative example:**

`> `
**example2 := 83:**

`> `
**a2 := 2:**

`> `
**with(numtheory): # needed for 'divisors'**

`> `
**S := divisors(example2 - 1);**

`> `
**Test := S minus {example2 - 1};**

`> `
**a2^(example2 - 1) mod example2;**

`> `
**seq(a2^r mod example2, r = Test);**

`> `

**Those computations show that:**

1.
** (mod 83), and**

2.
__none__
** of **
** leaves remainder 1 on division by 83**

and thus 83 is prime. It is obvious, of course, that the improvement is significant only when
** has a small number of divisors. It would be futile to use it to establish the primality of - for example - the 8-digit prime (11! + 1):**

`> `
**11! + 1;**

**since 11! has 540 divisors:**

`> `
**divisors(11!);**

`> `

**A really great improvement later came with D.H. Lehmer (though Kraitchik seems to know the result, but with no stated proof...). It is a mystery to me that Lucas missed it.**

`> `
**f := n -> product(ithprime(k), k=1..n)*ithprime(n+1)^n + 1;**

`> `
**f(1);**

`> `
**f(2);**

`> `
**f(3);**

`> `
**f(100);**

`> `

**It is explained in simple language in my booklet what I did, but here I just remark that what I needed to do, to identify primes in the above sequence, was to **
**first**
** identify **
**some candidates**
** for primality (meaning ones that at least passed the **
**first hurdle**
** of the Fermat-Lucas test to the base 2):**

`> `
**candidates := proc(m, n) local k;**

for k from m to n do

if 2&^(f(k)-1) mod f(k) = 1

then print(k, f(k))

fi od end:

`> `
**candidates(1, 30);**

`> `

**And thus, out of the first 30 of the above numbers, the 1st, 2nd, 10th, and 10th are possible primes.**

In fact, those four are all prime (the first two - 7 and 151 - can be done by hand!), but, how do we
**know**
** that; how can we **
**prove**
** that? Using Pocklington, that is. Let's have a look at the 3rd of them, the 25 digit **

`> `
**f(10);**

**and just to let you **
**see**
**:**

`> `
**ifactor(f(10) - 1);**

`> `

**We already have that **
** (mod **
**), and so, using Pocklington, the primality of **
** would be established if we **
__also__
** had that **
**. Now, the computation of the gcd of two numbers - even really large ones - is a **
**fast computation**
** (this is part of the greatness of the **
**Euclidean algorithm**
**): **

`> `
**igcd(10^200 + 84, 10^150 + 14);**

`> `
**igcd(100! + 8765432, 10^150 + 13);**

`> `

**So, let's calculate: **

`> `
**igcd(2^((f(10) - 1)/ithprime(11)) - 1, f(10));**

`Error, integer too large in context`

`> `

**Which integer is "too large"? It's the **
**. That number (easy exercise) has **
**more**
** than ten thousand, million, million, million digits!! And Maple can only handle integers up to **
**about**
** 500,000 digits. (And that's just for f(10); the millennium prime is f(325)). So, what can one do? To our rescue comes the Euclidean algorithm, the **
**key step**
** of which is the utterly elementary - but oh! so incredibly powerful result! - that if **
**A**
** and **
**B**
** are any two whole numbers, then **
**, where **
**R**
** is the integer obtained from **
**A**
** by dividing it by **
**B**
**, as in: **
**, where **
**Q**
** is the 'quotient', and **
**R**
** is the 'remainder'.**

In particular it means that the value of
** may be obtained by computing the remainder that **
** leaves on division by f(10): **

(and the Maple command for
**that**
** is the modular exponential one: 2&^((f(10) - 1)/ithprime(11)) - 1 mod F(10) )**

thus obtaining:

`> `
**igcd(f(10), 2&^((f(10) - 1)/ithprime(11)) - 1 mod f(10));**

`> `

**Instantly, and **
**proving**
** that f(10) is prime.**

`> `
**igcd(f(20), 2&^((f(20) - 1)/ithprime(21)) - 1 mod f(20));**

**which **
**proves**
** that f(20) is prime. Returning to my search of last January 1999 I continued looking for candidates, and checking bit by bit up to f(180) these were the outputs (to re-execute them you must first delete the comment sign ' # ' before 'candidates'): **

`> `
**# candidates(31, 60); # no output**

`> `
**# candidates(61, 120); # no output**

`> `
**# candidates(121, 180); # here just one output, '173'**

`> `
**length(f(173));**

`> `

**and applying Pocklington to f(173) it turned out to be prime, and I might have stopped at that point but decided to plough on as my ambition then was to find - if there was one! (it was quite possible that there might not have been another one) - a Euclid-Pocklington prime with at least 1000 digits (any prime with at least 1000 digits is known as a **
**titanic**
** prime, and its finder is entitled to be called a **
**Titan**
**; it's just a bit of fun.)**

Well, you have probably guessed the outcome: the first candidate after f(180) turned out to be f(325) (the '325' was the output from 'candidates(301, 330)'). Then the Pocklington condition was satisfied, proving that f(325) was prime, and then, checking to see how many digits it had, it happened to be exactly 2000.

John Selfridge's theorem of 1967. Let
**... **
**, where the **
**, ... are distinct primes, and suppose for **
**each**
** **
**i**
** there is an integer **
** (which may or may not vary as i varies, though in practice it does - it is this freedom that makes it superior to Lehmer's theorem) such that:**

1.
** (mod **
**n**
**) (i.e. **
** leaves remainder 1 on division by **
**n**
**; **

in other words, suppose "
**n**
** passes the Fermat-Lucas test to the base **
**a**
**"]**

2.
** (mod **
**n**
**) (i.e., **
** does **
**not**
** leave remainder 1 on division by **
**n**
**)**
**,**

then
**n**
** is prime. And here, for example, is the primality of 11! + 1 established using Selfridge:**

`> `
**N := 11! + 1;**

**First fix **
**a**
** at 2 to see:**

`> `
**2&^(N-1) mod N;**

`> `
**2&^((N-1)/2) mod N; # need to try another 'a'**

`> `
**2&^((N-1)/3) mod N;**

`> `
**2&^((N-1)/5) mod N; # need to try another 'a'**

`> `
**2&^((N-1)/7) mod N;**

`> `
**2&^((N-1)/11) mod N;**

`> `

`> `
**3&^(N-1) mod N;**

`> `
**3&^((N-1)/2) mod N; # need to try another 'a'**

`> `
**3&^((N-1)/5) mod N;**

`> `

`> `
**13&^(N-1) mod N;**

`> `
**13&^((N-1)/2) mod N; **

`> `

**That last, non-unity output, finally establishes the primality of **
**. Other examples of Selfridge's theorem may be viewed in the 3rd year section of the Maple section of my web site.**

Other examples of Euclid-Pocklington (or simply Pocklington) type primes.

A very beautiful (because of its structure, and its resistance to a classical primality proof) prime, one with 1031 digits, is the prime
**. This number was first identified as a **
**probable prime**
** several years ago (in an unpublished paper) by Wilfrid Keller, and was rediscovered by me on March 10th 1999 (see my earlier, afternoon talk), again as a probable prime. For my purposes it was critical that it **
**be**
** a prime, and following circulation of a note about it to about 35 mathematicians I received a note from Francois Morain on March 25th 1999 that a two day computation by him - using the elliptic curve method - had resulted in its primality being established. This prime has been dubbed the 'Keller-Cosgrave-Morain' prime**

`> `
**KCM := (2^(59^2) - 1)/(2^59 - 1):**

`> `
**length(KCM);**

`> `

**Some weeks ago, with this talk in mind, I thought it might be interesting to find a Pocklington-type prime of the form (**
**), with **
**, and **
**. Using Chris Nash's PrimeForm program I found a 2613-digit one one with **
**. This prime is especially interesting since the number **
**U**
** is currently unfactored.**

`> `
**p := (KCM - 1)*3^3316 + 1:**

`> `
**length(p);**

`> `

**On December 30th 1999, again using Chris Nash's PrimeForm I found the 15756-digit Pocklington type prime **
***...***
**.**

The general form of Pocklington's theorem. Let
**... **
**, where the **
**, ... are distinct primes, none of which divide **
**U**
**, and **
** ... **
**. **
**Then**
** n**
** is prime if:**

Condition 1 (the Fermat-Lucas condition)
** **
** there is **
**some**
** integer **
**a**
** such that **
** (mod **
**n**
**), and**

Condition 2
** **
**(the general Pocklington's condition)**
** **
** for all **
**i**
**.**

An example:
***...***
** is a 3318-digit prime.**