Euclidean number

In number theory , a Euclidean number is a natural number of the form , where the product of the first prime numbers is bis ( prime faculty ). ${\displaystyle E_{n}=p_{n}\#+1}$ ${\displaystyle p_{n}\#=2\cdot 3\cdot 5\cdot 7\cdot \ldots \cdot p_{n}}$ ${\displaystyle n}$ ${\displaystyle p_{n}}$

Origin of name

These numbers were named after the ancient Greek mathematician Euclid , who was the first to prove in Euclid's theorem that there are infinitely many prime numbers. In doing so, he multiplied a set of prime numbers, added one to them and got a new number that none of the previous prime numbers could have as a divisor. So either this number was a prime number or it had prime divisors that did not appear in the previous prime number set. Euclidean numbers that are prime are called Euclidean prime numbers ( not all Euclidean numbers are prime numbers ).

Examples

• The first Euclidean number in the literature is either or , depending on whether you define or not. ${\displaystyle E_{0}=p_{0}\#+1=1+1=2}$ ${\displaystyle E_{1}=p_{1}\#+1=2+1=3}$ ${\displaystyle p_{0}\#:=1}$
• The first four prime numbers are and . The product of these four prime numbers is the prime faculty . So is the Euclidean number . ${\displaystyle 2,3,5}$ ${\displaystyle 7}$ ${\displaystyle p_{4}\#=7\#=2\cdot 3\cdot 5\cdot 7=210}$ ${\displaystyle E_{4}=p_{4}\#+1=7\#+1=210+1=211}$
• The first Euclidean numbers are (starting with ): ${\displaystyle n=(0),1,2,\ldots }$

(2), 3, 7, 31, 211, 2311, 30031, 510511, 9699691, 223092871, 6469693231, 200560490131, 7420738134811, 304,250,263,527,211, 13082761331670031, 614889782588491411, 32589158477190044731, 1922760350154212639071, 117288381359406970983271, 7858321551080267055879091 ... (sequence A006862 in OEIS )

• These Euclidean numbers have one or more prime factors. The following list gives the smallest of these prime factors for (with ): ${\displaystyle E_{n}}$ ${\displaystyle n=(0),1,2,\ldots }$

(2), 3, 7, 31, 211, 2311, 59, 19, 347, 317, 331, 200560490131, 181, 61, 167, 953, 73, 277, 223, 54730729297, 1063, 2521, 22093, 265739, 131, 2336993, 960703, 2297, 149, 334507, 5122427, 1543, 1951, 881, 678279959005528882498681487, 87549524399, 23269086799180847, ... (episode A051342 in OEIS )

Example:

You can see from the list above that the 7th digit (without ) is the number . So the smallest divisor of is number . ${\displaystyle (2)}$ ${\displaystyle 19}$ ${\displaystyle E_{7}=510511}$ ${\displaystyle 19}$

• The following list gives the largest of these prime factors for (with ): ${\displaystyle E_{n}}$ ${\displaystyle n=(0),1,2,\ldots }$

(2), 3, 7, 31, 211, 2311, 509, 277, 27953, 703763, 34231, 200,560,490,131, 676,421, 11,072,701, 78339888213593, 13808181181, 18564761860301, 19026377261, 525956867082542470777, 143,581,524,529,603, 2892214489673, 16156160491570418147806951, 96888414202798247, 1004988035964897329167431269, ... (Follow A002585 in OEIS )

Example:

You can see from the list above that the 7th digit (without ) is the number . So the greatest divisor of number is . ${\displaystyle (2)}$ ${\displaystyle 277}$ ${\displaystyle E_{7}=510511}$ ${\displaystyle 277}$

• The following list gives the first for which the Euclidean number is prime: ${\displaystyle n}$ ${\displaystyle E_{n}}$

(0), 1, 2, 3, 4, 5, 11, 75, 171, 172, 384, 457, 616, 643, 1391, 1613, 2122, 2647, 2673, 4413, 13494, 31260, 33237, ... ( Episode A014545 in OEIS )

Example:

The number is in the 6th position of the above list (without ) . So the 6th is Euclidean prime. ${\displaystyle (0)}$ ${\displaystyle 11}$ ${\displaystyle E_{11}=p_{11}\#+1=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17\cdot 19\cdot 23\cdot 29\cdot 31+1=200560490131}$

• The largest known Euclidean prime number (as of July 8, 2018) is . She has jobs and was discovered by Daniel Heuer on September 20, 2001. ${\displaystyle E_{33237}=p_{33237}\#+1=392113\#+1}$ ${\displaystyle 169966}$

properties

• Not all Euclidean numbers are prime numbers.

Proof:

Even the sixth Euclidean number is a composite number : . ${\displaystyle E_{6}=p_{6}\#+1=13\#+1=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13+1=30031=59\cdot 509}$ ${\displaystyle \Box }$

• Euclidean numbers are not prime to one another.

Proof:

A counterexample is sufficient:

${\displaystyle E_{8}=510.511}$and have the greatest common factor . ${\displaystyle E_{18}=1.922.760.350.154.212.639.071}$ ${\displaystyle {\operatorname {ggT} (E_{8},E_{18})}=277}$ ${\displaystyle \Box }$

• Let be any Euclidean number. Then: ${\displaystyle E_{n}}$

${\displaystyle E_{n}=4k+3}$ With ${\displaystyle k\in \mathbb {N} }$

In other words:

${\displaystyle E_{n}\equiv 3{\pmod {4}}}$

Proof:

The product of odd (prime) numbers is again odd and, written with congruences , is either or . The prime faculty is the product of and several odd prime numbers and thus either or . So it is in both cases . For a Euclidean number one has to add to the prime faculty and get what was to be shown. ${\displaystyle \equiv 1{\pmod {4}}}$ ${\displaystyle \equiv 3{\pmod {4}}}$ ${\displaystyle p_{n}\#}$ ${\displaystyle 2}$ ${\displaystyle \equiv 2\cdot 1\equiv 2{\pmod {4}}}$ ${\displaystyle \equiv 2\cdot 3=6\equiv 2{\pmod {4}}}$ ${\displaystyle \equiv 2{\pmod {4}}}$ ${\displaystyle 1}$ ${\displaystyle E_{n}=p_{n}\#+1\equiv 2+1=3{\pmod {4}}}$ ${\displaystyle \Box }$

• Let be a Euclidean number with . Then: ${\displaystyle E_{n}}$ ${\displaystyle n\geq 3}$

The last digit (i.e. the units digit) of is always . ${\displaystyle E_{n}}$ ${\displaystyle 1}$

In other words:

• ${\displaystyle E_{n}=10k+1}$with for ${\displaystyle k\in \mathbb {N} }$ ${\displaystyle n\geq 3}$
• ${\displaystyle E_{n}\equiv 1{\pmod {10}}}$ For ${\displaystyle n\geq 3}$

Proof:

For must be. Thus, in any case by and thus also divisible. has one in the ones place . If you add to that, you get a in the units place . ${\displaystyle n\geq 3}$ ${\displaystyle E_{n}-1=p_{n}\#+1-1=2\cdot 3\cdot 5\cdot \ldots \cdot p_{n}}$ ${\displaystyle E_{n}-1}$ ${\displaystyle 2}$ ${\displaystyle 5}$ ${\displaystyle 10}$ ${\displaystyle E_{n}-1}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle \Box }$

• Let be a Euclidean number. Then: ${\displaystyle E_{n}=2\cdot 3\cdot 5\cdot 7\cdot \ldots \cdot p_{n}+1}$

${\displaystyle E_{n}\equiv 1{\pmod {p}}}$ for all ${\displaystyle p\leq p_{n}}$

Proof:

The proof follows from the definition of the Euclidean numbers. with and . So is ${\displaystyle E_{n}=p_{n}\#+1=2\cdot 3\cdot 5\cdot 7\cdot \ldots \cdot p_{n}+1=k\cdot p+1}$ ${\displaystyle k\in \mathbb {N} }$ ${\displaystyle p\leq p_{n}}$ ${\displaystyle E_{n}=k\cdot p+1\equiv 1{\pmod {p}}}$ ${\displaystyle \Box }$

Unsolved problems

• Are there infinitely many Euclidean primes?
• Are all Euclidean numbers square-free ?

generalization

A Euclidean number of the 2nd kind (or also Kummer number , named after Ernst Eduard Kummer ) is an integer of the form , whereby the product of the first prime numbers is bis . ${\displaystyle {\overline {E}}_{n}=p_{n}\#-1}$ ${\displaystyle p_{n}\#=2\cdot 3\cdot 5\cdot 7\cdot \ldots \cdot p_{n}}$ ${\displaystyle n}$ ${\displaystyle p_{n}}$

Examples

• The first four prime numbers are and . The product of these four prime numbers is the prime faculty . Thus the fourth Euclidean number of the second kind is the number . ${\displaystyle 2,3,5}$ ${\displaystyle 7}$ ${\displaystyle p_{4}\#=7\#=2\cdot 3\cdot 5\cdot 7=210}$ ${\displaystyle {\overline {E}}_{4}=p_{4}\#-1=7\#-1=210-1=209}$
• The first Euclidean numbers of the 2nd kind are:

1, 5, 29, 209, 2309, 30029, 510509, 9699689, 223092869, 6469693229, 200560490129, 7420738134809, 304,250,263,527,209, 13082761331670029, 614889782588491409, 32589158477190044729, 1922760350154212639069 ... (sequence A057588 in OEIS )

• These Euclidean numbers of the 2nd kind have one or more prime factors. The following list gives the smallest of these prime factors for (with ): ${\displaystyle {\overline {E}}_{n}}$ ${\displaystyle n=1,2,\ldots }$

1, 5, 29, 11, 2309, 30029, 61, 53, 37, 79, 228737, 229, 304250263527209, 141269, 191, 87337, 27600124633, 1193, 163, 260681003321, 313, 163, 139, 23768741896345550770650537601358309, 66683309 2990092035859, 15649, 17515703, 719, 295201, 15098753, 10172884549, 20962699238647, 4871, 673, 311, 1409, 1291, 331, 1450184819, 23497, 711427, 521, 673, 519577, 1372062943, 53077, 56543 641, 349, 389, ... (sequence A057713 in OEIS )

Example:

You can see from the list above that the number is in the 7th position . So the smallest divisor of is number . ${\displaystyle 61}$ ${\displaystyle {\overline {E}}_{7}=510509}$ ${\displaystyle 61}$

• The following list gives the largest of these prime factors for (with ): ${\displaystyle {\overline {E}}_{n}}$ ${\displaystyle n=1,2,\ldots }$

1, 5, 29, 19, 2309, 30029, 8369, 929, 46027, 81894851, 876817, 38669, 304,250,263,527,209, 92608862041, 59799107, 1143707681, 69664915493, 1146665184811, 17975352936245519, 2140320249725509, ... (sequence A002584 in OEIS )

Example:

You can see from the list above that the number is in the 7th position . So the greatest divisor of number is . ${\displaystyle 8369}$ ${\displaystyle {\overline {E}}_{7}=510509}$ ${\displaystyle 8369}$

• The following list gives the first for which the Euclidean number of the 2nd kind is prime: ${\displaystyle n}$ ${\displaystyle {\overline {E}}_{n}}$

2, 3, 5, 6, 13, 24, 66, 68, 167, 287, 310, 352, 564, 590, 620, 849, 1552, 1849, 67132, 85586, ... ( continuation A057704 in OEIS )

Example:

The number is in the 6th position in the list above . Thus the 6th Euclidean prime number is of the 2nd kind. ${\displaystyle 24}$ ${\displaystyle {\overline {E}}_{24}=23.768.741.896.345.550.770.650.537.601.358.309}$

• The largest known Euclidean prime number of the 2nd kind (as of July 8, 2018) is . She has spots and was discovered by James P. Burt on February 28, 2012. ${\displaystyle {\overline {E}}_{85586}=p_{85586}\#-1=1098133\#-1}$ ${\displaystyle 476311}$

properties

• Not all Euclidean numbers of the 2nd kind are prime numbers.

Proof:

Already the fourth Euclidean number of the second type is a composite number: . ${\displaystyle {\overline {E}}_{4}=p_{4}\#-1=7\#-1=2\cdot 3\cdot 5\cdot 7-1=209=11\cdot 19}$ ${\displaystyle \Box }$

• Euclidean numbers of the 2nd kind are not coprime to one another.

Proof:

A counterexample is sufficient:

${\displaystyle {\overline {E}}_{19}=7.858.321.551.080.267.055.879.089}$and have the greatest common factor . ${\displaystyle {\overline {E}}_{22}=3.217.644.767.340.672.907.899.084.554.129}$ ${\displaystyle {\operatorname {ggT} ({\overline {E}}_{19},{\overline {E}}_{22})}=163}$ ${\displaystyle \Box }$

• Let be a Euclidean number of the 2nd kind with . Then: ${\displaystyle {\overline {E}}_{n}}$ ${\displaystyle n\geq 3}$

The last digit (i.e. the units digit) of is always . ${\displaystyle {\overline {E}}_{n}}$ ${\displaystyle 9}$

In other words:

• ${\displaystyle {\overline {E}}_{n}=10k+9}$with for ${\displaystyle k\in \mathbb {N} }$ ${\displaystyle n\geq 3}$
• ${\displaystyle {\overline {E}}_{n}\equiv 9{\pmod {10}}}$ For ${\displaystyle n\geq 3}$

Proof: works analogously to the above proof for "normal" Euclidean numbers.

For must be. Thus, in any case by and thus also divisible. has one in the ones place . If you subtract, you get a in the units place . ${\displaystyle n\geq 3}$ ${\displaystyle {\overline {E}}_{n}+1=p_{n}\#-1+1=2\cdot 3\cdot 5\cdot \ldots \cdot p_{n}}$ ${\displaystyle {\overline {E}}_{n}+1}$ ${\displaystyle 2}$ ${\displaystyle 5}$ ${\displaystyle 10}$ ${\displaystyle {\overline {E}}_{n}+1}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle 9}$ ${\displaystyle \Box }$

• Let be a Euclidean number of the 2nd kind. Then: ${\displaystyle {\overline {E}}_{n}=2\cdot 3\cdot 5\cdot 7\cdot \ldots \cdot p_{n}-1}$

${\displaystyle {\overline {E}}_{n}\equiv -1{\pmod {p}}}$ for all ${\displaystyle p\leq p_{n}}$

Proof:

The proof results from the definition of the Euclidean numbers of the 2nd kind with and . So is ${\displaystyle {\overline {E}}_{n}=p_{n}\#-1=2\cdot 3\cdot 5\cdot 7\cdot \ldots \cdot p_{n}-1=k\cdot p-1}$ ${\displaystyle k\in \mathbb {N} }$ ${\displaystyle p\leq p_{n}}$ ${\displaystyle {\overline {E}}_{n}=k\cdot p-1\equiv -1{\pmod {p}}}$ ${\displaystyle \Box }$

Unsolved problems

• Are there infinitely many Euclidean primes of the 2nd kind?

Individual evidence

1. ^ Neil Sloane : Euclid numbers: 1 + product of the first n primes. OEIS , accessed July 8, 2018 . 
2. ↑ Eric W. Weisstein : Euclid Number. Retrieved July 8, 2018 . 
3. ↑ 392113 # + 1 on Prime Pages
4. ↑ ^{a b} Neil Sloane : Euclid numbers: 1 + product of the first n primes - Comments. OEIS , accessed July 8, 2018 . 
5. ↑ Ernst Eduard Kummer : New elementary proof of the theorem that the number of all prime numbers is infinite . In: Preuss monthly report. Akad. D. Knowledge Berlin . 1878, p. 777-778 .
6. ^ Neil Sloane : Kummer numbers: -1 + product of first n consecutive primes - References. OEIS , accessed July 8, 2018 . 
7. ↑ 1098133 # - 1 on Prime Pages
8. ↑ 1098133 # - 1on primegrid.com (PDF)
9. ^ Neil Sloane : Kummer numbers: -1 + product of first n consecutive primes - Comments. OEIS , accessed July 8, 2018 . 

Web links

• Eric W. Weisstein : Euclid Number . In: MathWorld (English).
• Eric W. Weisstein : Euclid Number. Retrieved July 8, 2018 .