# Are Euclid numbers squarefree?

Are Euclid numbers squarefree ? An Euclid number is by definition a Primorial number + 1. See http://mathworld.wolfram.com/Primorial.html.

In notation the $n$ th Euclid number is written as $E_n = P_n+1.$

Thus I wonder about $a^2b = E_n$ for positive integer $a,b,n$ and $a>1$.

I was thinking about Korselt's criterion : http://mathworld.wolfram.com/KorseltsCriterion.html and Fermats little.

Im unaware of other techniques for proving the squarefree property apart from more elementary tools as gcd and basic modular aritmetic.

I cannot imagine infinite descent to work here ? Maybe a binomium will help ?

I guess I missed something trivial and have a bad day.

Maybe $a^2b = E_n-2$ is easier ?

• How far do you have numerical evidence? My quick checks started to slow down already at $197\cdot193\cdot\ldots\cdot 2+1$. – Hagen von Eitzen Oct 24 '12 at 15:55
• Euclid said if you take any finite set of prime numbers and take their product (actually Euclid said their LCM), and add $1$, the prime factors of the resulting number are not in the finite set you started with. If the finite set you started with is $\{3\}$, then the number you get is $4$, and that's not squarefree. If you start with $\{3,5\}$, you get $16$, which is not squarefree. And with $\{5,7\}$ you get $36$. (But it seems to be conventional today to define "Euclid numbers" by taking the initial set of primes to contain all primes less than some number.) – Michael Hardy Oct 24 '12 at 16:03
• I haven't thought about it much, but I'd be surprised if there is an algebraic reason for this conjecture to be true. But a pseudo-statistical argument suggests there is a non-zero probability that it could be "randomly" true. – user14972 Oct 24 '12 at 16:05
• @mick: Michael wrote an article on Euclid's proof of the infinitude of primes, which is often misrepresented in the literature. I think he was mostly trying to point out that the name "Euclid numbers" given to these numbers today shouldn't be taken to indicate that they figure in Euclid's proof. Also, one might expect any systematic arithmetic property of the Euclid numbers to be shared by the numbers Michael mentioned, so it wasn't a counterexample, but a reason to doubt that there's a systematic reason for your conjecture, even if it, as Hurkyl said it might, turns out to be "randomly" true. – joriki Oct 24 '12 at 17:09
• On page 525 of Graham, Knuth, Patashnik, Concrete Mathematics, it says no square less than $25\times10^{14}$ divides a Euclid number. – Gerry Myerson Oct 25 '12 at 2:38

Just to try to explain something about mathematics programming. You don't find $1 +P_n$ and hope to factor it. What you do, also exhaustive, is fix a prime $p$ as large as you can stand. Then you keep track of the values of $P_n \pmod {p^2}$ and see if you get $p^2 - 1.$ There is no reason to take $p_n \geq p,$ as that would imply $P_n \equiv 0 \pmod p,$ so for each $p$ this is a finite calculation. The result of this search, instantaneous on the machine, is that no $1 + P_n$ is divisible by the square of any prime smaller than $1625.$

I did this for $p^3 < 2^{32}$ with no luck. But I also took the easier values $\pmod p,$ just to see how often that gave anything. Note that there are repeats for $p = 277, \; 1051, \; 1381.$

EDDDIITTT, Thursday morning: I got this working in GMP, got the prime $p$ up above 1,000,000. So, no $1 + P_n$ is divisible by the square of any prime smaller than $1000000.$ I will make an attempt to paste the C++ program below, see how that goes.

=========================

p           p_n
3           2
7           3
19          17
31           5
59          13
61          41
73          53
97          17
131          89
139          53
149         107
167          43
173          53
181          37
211           7
223          61
271         263
277          17
277          59
307         283
313         239
317          23
331          29
347          19
463         443
467         199
509          13
571          29
601         179
673         659
809         677
827         499
877         677
881         137
953          47
983         463
997         769
1031         937
1033         587
1039          89
1051         211
1051         739
1063          71
1069         523
1109         839
1259         907
1279         811
1283         509
1291         439
1297         769
1361         163
1381         157
1381        1097
1471        1459
1543         127
1579         347
1619        1481


=========================

=========================

#include <iostream>
#include <stdlib.h>
#include <fstream>
#include <strstream>
#include <list>
#include <set>
#include <math.h>
#include <iomanip>
#include <string>
#include <algorithm>
#include <iterator>

#include <gmp.h>
#include <gmpxx.h>

using namespace std;

int PrimeQ(int i)
{
if ( i < 0 ) i *= -1;
if ( i <= 3) return 1;
else
{
int boo = 1;
int j = 2;

while (boo && j * j   <= i )
{
if ( i %  j  == 0) boo = 0;
++j;
}
return boo;
}
}  // PrimeQ deterministic and guaranteed, used on a range just once

// File named aa_GMP_trial.cc

//   compile with

//   g++  -o aa_GMP_trial aa_GMP_trial.cc  -lgmp -lgmpxx

//  run with

//         ./aa_GMP_trial

//  because my machine needs to be told an executable is in the same directory

//  William C. Jagy     October 2012

int main()
{

set<mpz_class> Primes;

mpz_class n ;
n = 2;

//   g++  -o aa_GMP_trial aa_GMP_trial.cc  -lgmp -lgmpxx

for (unsigned m = 2; m <= 1654321; ++m)
{

{
n = m;
if (PrimeQ(m))
{  Primes.insert(n);

//    cerr << n << endl;
}
}
}

set<mpz_class>::iterator iter;
int count = 0;
for(iter = Primes.begin() ;  iter != Primes.end() ; ++iter)
{

mpz_class p = *iter;
//  cout << setw(8) << p;
++count;
//   if(0 == count % 10) cout << endl;

if (0 == count % 1000) cout <<  "progress   " << p << endl;

//   g++  -o aa_GMP_trial aa_GMP_trial.cc  -lgmp -lgmpxx

//   mpz_class target =  p - 1;
//   mpz_class p2 =  p;

mpz_class target = p * p - 1;
mpz_class p2 = p * p;

mpz_class q = 1;
mpz_class product = 1;

set<mpz_class>::iterator iter2;

if( p > 2)
{
for(iter2 = Primes.begin() ; q < p &&  iter2 != Primes.end() ; ++iter2)
{
q = *iter2;
product *= q;
product %= (p2);
if ( target == product)
{
cout  << p << setw(12) << q << endl;
}
}  // iter2 for q
} // p > 3

} // iter for p

cout << endl << endl;

//   g++  -o aa_GMP_trial aa_GMP_trial.cc  -lgmp -lgmpxx

return 0 ;
}


========================

• What is wrong with this. I said preformatted text, it should keep the columns. – Will Jagy Oct 25 '12 at 2:09
• It worked better when I had each line start in the first column. – Will Jagy Oct 25 '12 at 2:24
• No complaints with the C++ program. This is anti-numerical discrimination. – Will Jagy Oct 25 '12 at 16:54
• Interesting use of the symmetry of == -- do you do that to make life more interesting? :-) – joriki Oct 25 '12 at 18:18
• @joriki, yes, I feel I have a duty to entertain. However, it is also recommended programming practice in languages where = is assignment while == is equality comparison, since, if one mistakenly types 0 = x the compiler will call attention to the illegal assignment. – Will Jagy Oct 25 '12 at 19:58

Here's a heuristic argument of the kind that Hurkyl mentioned in a comment that gives a non-zero "probability" for all Euclid numbers to be squarefree.

The "probability" for a large number to be squarefree is

$$\prod_{n=1}^\infty\left(1-\frac1{p_n^2}\right)=\frac6{\pi^2}\;,$$

where $p_n$ is the $n$-th prime. The Euclid numbers grow so fast that we can asymptotically take them to be large numbers in the sense that they could potentially be divisible by the squares of all primes. (Any error incurred by this approximation will only cause us to underestimate their "probability" to be squarefree.) However, by construction $E_n$ is not divisible by the first $n$ primes. Thus, the $n$-th prime has $n-1$ chances of its square dividing a Euclid number. That makes the a priori "probability" of all Euclid numbers being squarefree approximately

$$\prod_{n=2}^\infty\left(1-\frac1{p_n^2}\right)^{n-1}\;.$$

The first few terms of this product are to be taken with a large lump of salt, but we're not interested in them, only in the asymptotic behaviour and in the part left after Hagen's exploration up to $p_{45}=197$. Given that Hagen found all Euclid numbers up to $n=45$ to be squarefree, every prime now has $45$ fewer chances for its square to divide a Euclid number, so the a posteriori "probability" for all Euclid numbers to be squarefree is

$$\prod_{n=47}^\infty\left(1-\frac1{p_n^2}\right)^{n-46}=\left(\frac{\pi^2}6\prod_{n=1}^{46}\left(1-\frac1{p_n^2}\right)\right)^{46}\prod_{n=47}^\infty\left(1-\frac1{p_n^2}\right)^n\;.$$

The corrective factor before the infinite product is only about $1.035$ (computations 1 and 2), so we can focus on the infinite product and approximate it using asymptotic results for large $n$:

\begin{align} \prod_{n=47}^\infty\left(1-\frac1{p_n^2}\right)^n &\approx\prod_{n=47}^\infty\left(1-\frac1{(n\log n)^2}\right)^n \\ &\approx\prod_{n=47}^\infty\exp\left(-\frac1{n\log^2 n}\right) \\ &\approx\exp\left(-\int_{47}^\infty\frac1{x\log^2 x}\mathrm dx\right) \\ &=\exp\left(-\frac1{\log47}\right) \\ &\approx0.77\;. \end{align}

Thus, together with the corrective factor of about $1.035$, there is now only roughly a $1$ in $5$ chance of finding a Euclid number that isn't squarefree even if there's no systematic reason preventing this. From a practical perspective, if there is one to be found, it's unlikely to be found by fully checking further Euclid numbers, which would soon become prohibitively difficult, since even going up to $n=100$ (with $p_n=541$) would only increase the product to $\exp(-1/\log100)\approx0.80$; it might be more efficient to check more numbers at higher $n$ for divisibility by smaller squares, which have a better hit rate.

Of course the same analysis holds for the numbers $P_n-1$.

[Update:]

Given the quote from Concrete Mathematics in Gerry's comment, we know that the square of no prime up to $p_{3000000}\approx5\cdot10^7$ divides a Euclid number; so the remaining chance of finding one that does is only approximately $1-\exp(-1/\log3000000)\approx6.5\%$.