The infinite number of prime numbers was already known in ancient Greece. It seems that the proof of the following feeling is written in “Original theory
Suppose there are only 3 prime numbers. Let this be $p$, $q$, $r$. If $pqr+1$ is divided by $p$, $q$, or $r$, $1$ will be left. This violates the assumption that the prime numbers are only $p$, $q$, $r$. (This reasoning is the same for 4 or 5 primes. In other words, assuming that the number of primes is finite, a contradiction is always introduced.)
It uses the absurd method (a logic that derives contradiction from Assumption A and proves the negation of A). When I met this proof in middle school, I was a little moved. The absurdity method was cool, and I think it was wonderful that the contradiction was really easily drawn from the simple formula “total product of all prime numbers plus 1.”
Around the same time, I learned that there was a theme of “searching for large prime numbers”. With the advance of electronic computers, I found that a huge number of prime numbers that could not be found by hand calculation were found one after another, and a table was created such as who found what prime number in which year. ..
An amateur like me remembers the proof of the “Principle” and thinks of such a wrong thing.
You can easily get a huge prime number by multiplying all found prime numbers and adding 1!
Of course not. The assumption that there is a finite number simply leads to the situation where the total product plus 1 cannot be divided. In reality, the number of primes is infinite, and just because a finite number of primes are taken out and multiplied by 1 and added to 1, that does not mean that they are primes.
But right? The sum of the sum of $n$ primes plus one is at least indivisible by those primes. Therefore, in a sense, it can be said that it is a “divisible number”. In other words, there are quite a few prime numbers in them, right?
Considering Eratosthenes’s sieves
Therefore, it would be good to arrange the prime numbers in ascending order, take the first $n$, and add 1 to the total product of them to try.
First, take the first prime number $2$. Add $1$ to this, $3$ is a prime number.
Next. $2\cdot3+1=7$ is a prime number. How nice.
$2\cdot3\cdot5+1=31$ is also a prime number. Well, it’s in good shape.
How about $2\cdot3\cdot5\cdot7+1=211$? It’s easy to see that it’s not divisible by $11$ or $13$. You don’t have to try $17^2$ because it exceeds $211$. It turned out to be a prime number. Hmm, isn’t the story too good? Up to this point, I did my best by hand calculation.
How about $2\cdot3\cdot5\cdot7\cdot11+1=2311$? I gave up hand calculations. It’s not that difficult, but I’m not confident that I won’t make a mistake.
Here at the terminal
irb -r prime
Now, the Ruby interactive environment is started and the prime number library
prime is loaded.
irb(main):001:0> 2311.prime? => true
Oh, this is also a prime number! (You can confirm that an integer is a prime number with Integer#prime?)
I didn’t expect to see only so many prime numbers.
Let’s examine it programmatically. Write the following in Ruby.
require "prime" 1.step do |n| m = Prime.take(n).inject(:*) + 1 puts "%3d %s %d" %[n, (m.prime?? "o" :"x"), m] end
This program is not written to stop. It is designed to continue to infinitely investigate.
You can get an array of the first
n prime numbers with
You can get the total product with
- the value of
- Whether it is a prime number (
oif prime number,
- Value of “total product plus 1”
Just display and side by side.
The results were as follows.
1 o 3 2 o 7 3 o 31 4 o 211 5 o 2311 6 x 30031 7 x 510511 8 x 9699691 9 x 223092871 10 x 6469693231 11 o 200560490131 12 x 7420738134811 13 x 304250263527211 14 x 13082761331670031 15 x 614889782588491411 16 x 32589158477190044731 17 x 1922760350154212639071 18 x 117288381359406970983271
It goes all the way to $n = 18$, but it doesn’t go on forever.
It was a prime number up to $n = 5$, but then a composite number follows. Hmm sorry.
When I think that the prime number finally appears at $n = 11$, the composite number continues again.
Was it an illusion that I thought, “I think prime numbers are included in a good proportion?”