`> `
**# Fermat.mws**

__Speaker__
**: Dr. John Cosgrave.**

__Address__
**: Mathematics Department, St. Patrick's College, **

** Drumcondra, Dublin 9, IRELAND.**

__e-mail__
**: [email protected] (College) or **

[email protected] (Home)

__Web__
**: <http://www.spd.dcu.ie/johnbcos>**

__Title of talk__
** (given on Tuesday 10th. August 1999 in Plymouth University, Devon, England): **

** **

** The mathematical context of the **

recent (25th. July 1999) discovery of the

__largest known composite Fermat number__

**Note**
**. The Maple file of this talk, and many other Maple worksheets**

**1st. year Maple/Calculus/Analysis**

**2nd year Number Theory**

**3rd year Number Theory and Cryptography**

**some public lectures**

**together with course notes, examination papers (written and Maple lab), may be accessed at my Web site.**

__Dedication__
**.**

** **
**I dedicate this talk to the French scientist Yves Gallot (Toulouse), **

and the German mathematician Wilfrid Keller (Hamburg)

**Dear Friends and colleagues,**

I am delighted to inform you that using Yves Gallot's Proth program I have just found the

10th. largest known prime
** (and a new Irish prime record into the bargain). The prime is:**

** 3***
**, **

and it has 115130 digits.

All the credit goes to Proth (1878, whose theorem I teach to my 3rd. years), to Gallot for his

remarkable program, and to my College for computer access during the slack Summer period.

I have put up a brief note about it on my web site (<www.spd.dcu.ie/johnbcos>).

**Then, two days later , on the evening of Sunday 25th. August I sent out the following much more **

exciting announcement:

** **
**ANNOUNCING THE LARGEST KNOWN COMPOSITE FERMAT NUMBER**
** **

**Dear Friends and colleagues,**

Using Yves Gallot's remarkable Proth program I have made the fortuitous discoveries that:

1.
*****
** is **
**prime**
** (the 10th. largest known one, and the**

3rd. largest non-Mersenne prime),

2.
**p**
** is a divisor of the **
**Fermat number**
** **

making
** be the **
__largest known composite Fermat number__
**, and the sixth **

[added later: its actually the 7th.] Fermat number for which a factor has been found

using Gallot's program.

3.
**p**
** is a divisor of the following 'generalized Fermat numbers' (GFN's):**

**, **

** **
**, **

**, **

4.
**p**
** is **
__not__
** a divisor of **
**any**
** **
** **
__nor__
** of **
**any**
** **
**,**

5.
**p**
** is a 'generalized Cullen prime.'**

Previously the largest known composite Fermat number was

**, with prime 3***
** [Jeff Young, 1998]**

I made my chance discovery while making a systematic Proth-Gallot test of all numbers

**3***
**, with '**
**n**
**' ranging between 366,000 and 390,000, spread over 40-50 machines in **

**my College's main computer laboratory, during the past two months. **

Best wishes to you all, John

REFERENCES

1. Wilfrid Keller maintains the 'Prime factors k*2^n + 1 of Fermat

numbers F[m] and complete factoring status' site at:

<http://vamri.xray.ufl.edu/proths/fermat.html>

2. Ray Ballinger valiantly maintains the Proth prime search site at:

<http://vamri.xray.ufl.edu/proths/>

3. Chris Caldwell maintains [just in case you didn't know] the

remarkable Prime number site at:

<http://www.utm.edu/research/primes>

Much more detail concerning the story and timing of the discovery may

**be seen at my College we site, including a simple analysis showing that **

**the **
**supra-astronomically large**
** number**

**has **

**approximately **
** digits**

**public lectures, given in October 1997, available at my web site.]**

**Recall that a **
__perfect__
** number is one whose sum of factors - excluding itself - is equal to itself.**

__Examples__

**6 is perfect, because the factors of 6 are 1, 2, 3 and 6, and **
**.**

**28 is perfect, because the factors of 28 are 1, 2, 4, 7, 14 and 28, and **

**496 is perfect, because the factors of 496 are 1, 2, 4, 8, 16, 31, 62, 124, 248 and 496, and **

__Euclid's great discovery (and one to which students may easily be led) was__
**: Let **
** be a natural number **

such that (
**) is a prime number, then the number **
** is a perfect number.**

__Examples__
**.**

** is prime, and thus the number **
*****
**, is perfect**

** is prime, and thus the number **
*****
** = 33,550,336, **

is perfect

`> `
**isprime(2^13 - 1);**

`> `
**2^12*(2^13-1);**

`> `

__Historical (historic, and unsolved) question__
**: For which values of **
** is (**
**) prime?**

__Some partial answers__
**.**

__If__
** **
**n**
** is composite (i.e., is not prime) **
__then__
** (**
**) is also composite,**

**and - as a consequence - **

__if__
** (**
**) is prime, **
__then__
** **
**n**
** is prime.**

__Warning__
**. It is **
__not true__
** that**

**if **
**n**
** is prime then **
**(**
**) is prime**

__Examples__
**. Note that 11, 23 and 29 are all prime, but:**

`> `
**isprime(2^11 - 1);**

`> `
**ifactor(2^11 - 1);**

`> `

`> `
**isprime(2^23 - 1);**

`> `
**ifactor(2^23 - 1);**

`> `

`> `
**isprime(2^29 - 1);**

`> `
**ifactor(2^29 - 1);**

`> `

**their origin is a question asked in the 3rd. century B.C. (and earlier), Fermat primes/numbers **

**had their origin in 1640. **

__Pierre de Fermat (1601-1665__
**, and the '**
**father of modern Number Theory**
**') - a contemporary **

**and correspondent of Mersenne's - asked himself this **
__apparently__
__ simple question__
**, sometime **

**in the Summer of 1640:**

** Which primes are a power of 2, **
__plus__
** 1? That is, for which values of **
**r**
** (**
**...) **

is (
**) a prime?**

**School children, students, anyone, may easily check by hand that:**

**When **
**, **
** = 3, **
__is__
** prime**

**When **
**, **
** = 5, **
__is__
** prime**

**When **
**, **
** = 9 = 3*3, is **
__not__
** prime**

**When **
**, **
** = 17, **
__is__
** prime**

**When **
**, **
** = 33 = 3*11, is **
__not__
** prime**

**When **
**, **
** = 65 = 5*13, is **
__not__
** prime**

**When **
**, **
** = 129 = 3*43, is **
__not__
** prime**

**When **
**, **
** = 257, **
__is__
** prime**

**At this point (and this has always been my experience, over many years, with my own students) **

**any numerically sensitive person will immediately leap to the **
__guesses__
**/**
__questions__
**:**

**Is (**
**) composite when **
**r**
** **
__is not__
** a power of 2? [Here the answer is a simple '**
**yes**
**,' and it is **

an elementary exercise to prove it.]

**Is (**
**) prime when r **
__is__
** a power of 2? That is, letting **
** (**
**, ... ) **

be the
**m**
**-th Fermat number, is it true that **
** is prime for all **
**?**

**In a letter to Frenicle of **
__August 1640__
** (and another of October 1640; both letters available - in French - **

**at Antreas P. Hatzipolakis's we site: <http://users.hol.gr/~xpolakis/fermat/fac.html>) Fermat wrote as **

**follows (English translation quoted from M.S.Mahoney's **
**The Mathematical Career of Pierre de Fermat**
**, **

**Princeton University Press, 2nd edition, 1994; see also Andre Weil's **
**Number Theory **
**(**
**An approach through **

**history**
**), Birkhauser, 1984):**

**But here is what I admire most of all: it is that I am just about convinced that all progressive numbers **

**augmented by unity, of which the exponents are numbers of the double progression, are prime numbers, **

**such as**

**3, 5, 17, 257, 65537, 4294967297**

**and the following of twenty digits**

** 18446744073709551617, etc.**

**I do not have an exact proof of it, but I have excluded such a large quantity of divisors by infallible **

**demonstrations, and my thoughts rest on such clear insights, that I can hardly be mistaken.**

**Fermat returned to this question over and over again in the remaining 25 years of his life, and when he **

**died in January 1665 he could not - perhaps - have imagined that all would change quite dramatically in **

**the following century... .**

**Briefly this theorem (which lies unproved in the work of Fermat - and has its origins in Fermat's studies **

**of which primes may be the hypothenuse of an integer sided right angled triangle...) states this:**

**Let **
**m**
** be **
__any__
** natural number, and **
**x**
** be any integer, then **
__every__
** **
__odd__
** **
__prime__
** divisor **
**p**
** of the integer **

**(**
**) leaves remainder 1 when divided by **
**.**

**In other words, **
__every__
** **
__odd__
** **
__prime__
** divisor **
**p**
** of the integer (**
**) must have the following **
__structure__
**:**

** **
*****
**,**

**for some **
**, ... **

__Examples__
**:**

`> `
**m := 4; # and so (m+1) is 5**

`> `
**2^m;**

`> `
**2^(m+1);**

`> `
**x := 5;**

`> `
**x^(2^m) + 1;**

`> `
**ifactor(x^(2^m) + 1);**

`> `
**2593 mod 2^(m+1);**

`> `
**29423041 mod 2^(m+1);**

`> `

**What Euler did (actually Andre Weil is of the view (which I am in sympathy) that Fermat himself **

**also did this - using his unproven discovery - but made an arithmetical error) was to attempt to find **

a factor of:

** **
** = **

**by using the proved result that any prime factor **
**p**
** of **
** must be of the form:**

** **
** (some **
**, ... )**

**and, when he got up to **
** he found that **
*****
** **

is a proper factor of
**:**

`> `
**F := m -> 2^(2^m) + 1; # defining the FUNCTION 'F'**

`> `
**F(5);**

`> `
**F(5)/641;**

`> `
**ifactor(F(5));**

`> `

**and in the following century, Landry (in 1880, and at the age of 82!) found a proper factor of:**

** = **

`> `
**F(6);**

`> `
**ifactor(F(6));**

`> `

__Warning__
**. I am **
__not__
** going to use Maple to **
__attempt__
** to factor**

**:**

`> `
**F(7);**

`> `

**because that number **
__was only factored as recently as 1970__
** - **

it has the following prime factorization:

** = (**
*****
**)*(**
*****
**)**

and it was only possible to do so because of a very great theoretical advance, made that year,

**due to **
__Brillhart and Morrison__
**.**

`> `
**p1 := 116503103764643*2^9 + 1;**

`> `
**isprime(p1);**

`> `
**p2 := 11141971095088142685*2^9 + 1;**

`> `
**isprime(p2);**

`> `
**N := p1*p2;**

`> `
**is(F(7) = N);**

`> `

**However, in 1970 it had **
**already been known**
** from the first decade of this century that **
** **
__is__
** composite!!**

__How__
** was it possible to know at **
**an earlier time**
** (than 1970) that **
** is composite?**

**This brings us to **
__Pepin's remarkable theorem of 1877__
**:**

** is a prime if and only if the number**

** **

**leaves remainder **
** when divided by **
**.**

**That is, **
** is a prime if and only if**

** ... (P)**

**for some integer **
**.**

__Small hand performed example__
__, by way of illustration__
**:**

**Let **
**, then **
** = **
** = 17, and so**

** **
** = **
**, **

**and dividing 6561 by 17 we get:**

*****
** ... [compare with P, above]**

**proving, by Pepin's theorem that **
** = 17, is prime.**

**That small example was for illustration purposes **
**only**
**; no one would seriously prove that 17 is prime**

**by appealing to Pepin's theorem!! However for larger values of **
**, it really is a serious issue to decide **

**the status of **
** by using Pepin's theorem (though researchers are currently stuck on the case **
**).**

**Here is the Maple command for that latter computation:**

`> `
**mods(3^((F(2) - 1)/2), F(2));**

`> `
**mods(3^((F(3) - 1)/2), F(3));**

`> `
**mods(3^((F(4) - 1)/2), F(4));**

`> `

**Incidentally, let us just have a peek at the value of the number [which I OMIT in**

**the primted form to save space. remove the **
**comment sign **
**'#' before the command if**

**you wish to execute it]:**

`> `
**# 3^((F(4) - 1)/2);**

`> `

**It is quite large! This computes how many digits it has:**

`> `
**length(3^((F(4) - 1)/2));**

`> `

**Now let's do the Euler case, where **
**:**

`> `
**F(5);**

`> `

**But see what happens when we attempt to apply the Pepin theorem:**

`> `
**mods(3^((F(5) - 1)/2), F(5));**