Questions tagged [primes]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3 votes
1 answer
165 views

How did Gauss determine the number of primes?

In Brian Conrey's article on Riemann's hypothesis, one reads in the very beginning: On Christmas Eve 1849 Gauss wrote a letter to his former student Encke in which he described his thoughts about the ...
Hans-Peter Stricker's user avatar
0 votes
1 answer
132 views

Euclid's use of antenaresis and Heath's commentary

In Book 7, Prop. 1. Euclid uses repeated subtraction to prove that two numbers are relatively prime. As explained here the Greek word for repeated subtraction is "antenaresis". There isn't ...
zeynel's user avatar
  • 257
16 votes
1 answer
4k views

Autistic Assistant of Gauss used to check Primality

The Arora-Barak book on complexity contains the following sentence with the following footnote, page 128: In primality testing, we are given an integer N and wish to determine whether or not it is ...
abrahimladha's user avatar
2 votes
2 answers
272 views

Simplest of the many proofs the prime harmonic series diverges

Over the history of mathematics, some key facts have had multiple and different proofs developed for them. Sometimes these different proofs provide a unique insight or understanding of those facts. ...
Penelope's user avatar
  • 415
7 votes
2 answers
480 views

$2^{11} - 1$ and the mystery of Huldaricus Regius

While researching on Mersenne numbers, I often stumble upon statements of this nature (it is not verbatim): Huldaricus Regius in 1536 proved that $2^{11}-1$ is not prime, providing a factorisation ...
Plasma Stark's user avatar
6 votes
1 answer
3k views

Who discovered this closed form formula for the n-th prime number?

The following is a formula for the $n$-th prime number ($[\,]$ represents the floor function). Who was the first person to discover it? $$\newcommand{\lowerbrack}[2]{% \raise{-#1}{\left[\raise{#1}{#...
user776490's user avatar
2 votes
0 answers
113 views

First motivation for extending Riemann Zeta to complex domain?

Euler developed the Euler Product Formula which shows that the Riemann zeta function encodes information about the prime. $$\zeta(s)=\sum_{n}\frac{1}{n^{s}}=\prod_{p}(1-\frac{1}{p^{s}})^{-1}$$ Riemann ...
Penelope's user avatar
  • 415
2 votes
2 answers
158 views

Was Cramér the first to interpret the PNT's $1/\log(x)$ as probability of primes?

The Cramér probabilistic model of primes is built on the assumption that the probability of $n$ being prime is $$\Pr(n)=\frac{1}{\log (n)}$$ This is not a big leap from the Prime Number Theorem which ...
Penelope's user avatar
  • 415
0 votes
0 answers
57 views

Any historical work on the distribution of prime gaps?

I am looking to see whether historic mathematicians did any work to explain the slightly unexpected distribution of prime gaps? I would have expected Gauss, who studied lists of primes and proposed a ...
Penelope's user avatar
  • 415
2 votes
1 answer
181 views

History of primality testing

Consider a uniform random variable $n$ which is an integer in the interval $2^{1023} < n < 2^{1024}$. What is the oldest algorithm capable of determining whether or not $p$ is a probable prime ...
forest's user avatar
  • 181
1 vote
1 answer
152 views

Euler's proof of infinite primes first since Euclid?

Q. Is it true that Euler's proof of infinite primes was the first since Euclid's which was from around 300BC? Note: By Euler's proof, I mean the use of his Euler product formula for the zeta function ...
Penelope's user avatar
  • 415