A note on small factors of Fermat numbers

Dr Sardonicus · 2017-07-11, 13:59

What with all the recent discussion of LL and Pepin's tests (and ignis fatuus implementations of them), I thought I'd mention a (small) class of primes which admit extremely short primality proofs, whose validity can be seen in a very elementary way. I make no claim of originality. In fact, I am quite sure that this is something that has been known for a very long time. But it may be deserving of wider notice, so here goes...

Tantalizingly, for each prime p there is a short primality certificate:

In Very Short Primality Proofs, Carl Pomerance gives the LL test for Mersenne primes and Pepin's test for Fermat primes as examples of proofs that p is prime, involving O(log₂(p)) multiplications. He shows [Theorem 1] that, for each prime p, there is a primality proof requiring (5/2 + o(1))log₂(p) multiplications mod p.

Unfortunately, the proof uses deep results on elliptic curves over finite fields. Also, there is no general way of finding such a short proof in a reasonable length of time.

Alas, Mersenne primes are quite rare, and (as Pomerance notes) it is widely thought that there are only finitely many Fermat primes.

However, there is are very short primality proofs for some factors of composite Fermat numbers. Although AFAIK there are not known to be infinitely many factors of the right type, the first factors yet to be found of most composite Fermat numbers will likely fill the bill.

I am sure this has been known for a long, long time. The first inkling that something unusual was afoot came to me when I was perusing Mathematical Recreations by Maurice Kraitchik. It had a table with known factors of Fermat numbers. The largest Fermat number in the table was F₇₃, with the factor 5*2⁷⁵ + 1. As listed in Prime factors k*2ⁿ + 1 of Fermat numbers F_m and complete factoring status, this factor was found in 1906 by J. C. Morehead. Given that year, computational means must have been quite limited.

At the time I saw this, I was fairly young, and my grasp of number theory was only elementary, including Fermat's "little theorem" and some basic consequences. But that was enough to inform me that the fact that p = 5*2⁷⁵ + 1 divides F₇₃, actually proves that p is prime! At the time, this struck me as extremely funny, given the enormous size of F₇₃. But, of course, using mod p arithmetic, the divisibility is easy to prove. We now give the very easy proof that the divisibility is also a primality proof. We use the following result of Lucas:

Let n > 1, and let p be a prime divisor of F_n. Then p == 1 (mod 2ⁿ⁺²).

The exponent n + 1 follows almost immediately from Fermat's "little theorem;" Lucas obtained the increase to n+2 by observing that for n > 1, 2 is a quadratic residue (mod p).

We then have the following result:

Let p = k*2ⁿ⁺² + 1 divide F_n. If k < 2ⁿ⁺² + 2, then p is prime.

The proof is very simple. If p is composite and divides F_n, its prime factors q are all congruent to 1 (mod 2ⁿ⁺²). Consequently,

p \ge (2ⁿ⁺² + 1)² = (2ⁿ⁺² + 2)*2ⁿ⁺² + 1, so k \ge 2ⁿ⁺² + 2, and the proof is complete.

This gives a primality proof of p involving n squarings (mod p); n < n + 2 + log₂(k) < log₂(p).

Nick · 2017-07-17, 11:55

For anyone whose library gives them access to JSTOR papers, the article "The Converse of Fermat's Theorem" by Raphael M. Robinson in the American Mathematical Monthly volume 64 no. 10 (pages703-710) from December 1957 assumes very little prior knowledge (only very basic Number Theory) and contains more about these results.

http://www.jstor.org/stable/2309747

2017-07-11, 13:59	#1
Dr Sardonicus Feb 2017 Nowhere 2×5×577 Posts	A note on small factors of Fermat numbers What with all the recent discussion of LL and Pepin's tests (and ignis fatuus implementations of them), I thought I'd mention a (small) class of primes which admit extremely short primality proofs, whose validity can be seen in a very elementary way. I make no claim of originality. In fact, I am quite sure that this is something that has been known for a very long time. But it may be deserving of wider notice, so here goes... Tantalizingly, for each prime p there is a short primality certificate: In Very Short Primality Proofs, Carl Pomerance gives the LL test for Mersenne primes and Pepin's test for Fermat primes as examples of proofs that p is prime, involving O(log₂(p)) multiplications. He shows [Theorem 1] that, for each prime p, there is a primality proof requiring (5/2 + o(1))log₂(p) multiplications mod p. Unfortunately, the proof uses deep results on elliptic curves over finite fields. Also, there is no general way of finding such a short proof in a reasonable length of time. Alas, Mersenne primes are quite rare, and (as Pomerance notes) it is widely thought that there are only finitely many Fermat primes. However, there is are very short primality proofs for some factors of composite Fermat numbers. Although AFAIK there are not known to be infinitely many factors of the right type, the first factors yet to be found of most composite Fermat numbers will likely fill the bill. I am sure this has been known for a long, long time. The first inkling that something unusual was afoot came to me when I was perusing Mathematical Recreations by Maurice Kraitchik. It had a table with known factors of Fermat numbers. The largest Fermat number in the table was F₇₃, with the factor 52⁷⁵ + 1. As listed in Prime factors k2ⁿ + 1 of Fermat numbers F_m and complete factoring status, this factor was found in 1906 by J. C. Morehead. Given that year, computational means must have been quite limited. At the time I saw this, I was fairly young, and my grasp of number theory was only elementary, including Fermat's "little theorem" and some basic consequences. But that was enough to inform me that the fact that p = 52⁷⁵ + 1 divides F₇₃, actually proves that p is prime! At the time, this struck me as extremely funny, given the enormous size of F₇₃. But, of course, using mod p arithmetic, the divisibility is easy to prove. We now give the very easy proof that the divisibility is also a primality proof. We use the following result of Lucas: Let n > 1, and let p be a prime divisor of F_n. Then p == 1 (mod 2ⁿ⁺²).* The exponent n + 1 follows almost immediately from Fermat's "little theorem;" Lucas obtained the increase to n+2 by observing that for n > 1, 2 is a quadratic residue (mod p). We then have the following result: *Let p = k2ⁿ⁺² + 1 divide F_n. If k < 2ⁿ⁺² + 2, then p is prime.** The proof is very simple. If p is composite and divides F_n, its prime factors q are all congruent to 1 (mod 2ⁿ⁺²). Consequently, p \ge (2ⁿ⁺² + 1)² = (2ⁿ⁺² + 2)2ⁿ⁺² + 1, so k \ge 2ⁿ⁺² + 2, and the proof is complete. This gives a primality proof of p involving n squarings (mod p); n < n + 2 + log₂(k) < log₂(p). Last fiddled with by Dr Sardonicus on 2017-07-11 at 14:07*

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
ECM on small Generalised Fermat numbers	geoff	Factoring	23	2010-09-13 23:50
Awfully small factors....	petrw1	Lone Mersenne Hunters	17	2009-11-20 03:40
newbie question - finding small factors of very large numbers	NeoGen	Math	7	2007-03-13 00:04
Small factors	Kees	PrimeNet	6	2006-11-16 00:12
LLT numbers, linkd with Mersenne and Fermat numbers	T.Rex	Math	4	2005-05-07 08:25

2017-07-17, 11:55	#2
Nick Dec 2012 The Netherlands 1,759 Posts	For anyone whose library gives them access to JSTOR papers, the article "The Converse of Fermat's Theorem" by Raphael M. Robinson in the American Mathematical Monthly volume 64 no. 10 (pages703-710) from December 1957 assumes very little prior knowledge (only very basic Number Theory) and contains more about these results. http://www.jstor.org/stable/2309747