Questions tagged [primes]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
1 answer
118 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
261 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
  • 405
7 votes
2 answers
475 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
112 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
  • 405
1 vote
2 answers
153 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
  • 405
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
  • 405
2 votes
1 answer
177 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
150 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
  • 405