Prime numbers are natural numbers not divisible by any smaller number other than 1. This tag is intended for questions about, related to, or involving prime numbers.
91
votes
6answers
17k views
Deleting any digit yields a prime… is there a name for this?
My son likes his grilled cheese sandwich cut into various numbers, the number depends on his mood. His mother won't indulge his requests, but I often will. Here is the day he wanted 100:
But ...
56
votes
5answers
3k views
What is the Riemann-Zeta function?
In laymen's terms, as much as possible: What is the Riemann-Zeta function, and why does it come up so often with relation to prime numbers?
40
votes
4answers
2k views
$x$, $y$, $x+y$ and $x-y$ are prime numbers. What is their sum?
Here is the question:
The $x$, $y$, $x−y$ and $x+y$ are all positive prime integers. What is the sum of all the four integers?
Well, I just put some values and I got the answer.
$x=5$, $y=2$, ...
39
votes
3answers
2k views
How did Euler prove the Mersenne number $2^{31}-1$ is a prime so early in history?
I read that Euler proved $2^{31} -1$ is prime. What techniques did he use to prove this so early on in history? Isn't very large number stuff done with computers? Do you know if Euler had a team of ...
39
votes
4answers
1k views
How to understand and appreciate the prime number industry?
Why would I want to buy prime numbers? There is a website (found it!) selling a table of 400 digit primes for twenty dollars. Like an updated version of this. I have a layman's idea that prime numbers ...
37
votes
1answer
1k views
Sums of prime powers
You are given positive integers N, m, and k. Is there a way to check if
$$\sum_{\stackrel{p\le N}{p\text{ prime}}}p^k\equiv0\pmod m$$
faster than computing the (modular) sum?
For concreteness, you ...
36
votes
3answers
2k views
$5^n+n$ is never prime?
In the comments to the question: $a^n+n|b^n+n \Longrightarrow a=b$, there was a claim that $5^n+n$ is never prime (for integer $n>0$).
It does not look obvious to prove, nor have I found a ...
34
votes
8answers
2k views
32
votes
6answers
2k views
Is $2^{218!} +1$ prime?
Prove that $2^{218!} +1$ is not prime.
I can prove that the last digit of this number is $7$, and that's all.
Thank you.
30
votes
8answers
4k views
For any prime $p > 3$, why is $p^2-1$ always divisible by 24?
I know this is very basic and old hat to many, but I love this question and I am interested in seeing whether there are any proofs beyond the two I already know.
29
votes
4answers
1k views
Could G. H. Hardy make a product of two primes so big he couldn't find out which?
This question of course began as a slightly irreverent play on the riddle, "Can God make a stone so big He can't lift it?" Then I wondered about the answer.
Is it possible to exhibit a number that is ...
29
votes
3answers
257 views
Do we really know the reliability of PrimeQ[n] (for $n>10^{16}$)?
The algorithm Mathematica uses for its PrimeQ function is described on MathWorld. That web page says PrimeQ uses, "the multiple ...
29
votes
2answers
559 views
Proof of no prime-representing polynomial in 2 variables
In "The New Book of Prime Number Records", Ribenboim reviews the known results on the degree and number of variables of prime-representing polynomials (those are polynomials such that the set of ...
29
votes
2answers
1k views
Small primes attract large primes
$$
\begin{align}
1100 & = 2\times2\times5\times5\times11 \\
1101 & =3\times 367 \\
1102 & =2\times19\times29 \\
1103 & =1103 \\
1104 & = 2\times2\times2\times2\times ...
28
votes
2answers
2k views
The square roots of the primes are linearly independent over the field of rationals
I need to find a way of proving that the square roots of a finite set
of different primes are linearly independent over the field of
rationals. I've tried to solve the problem using elementary ...
27
votes
5answers
3k views
Are all prime numbers finite?
If we answer false, then there must be an infinite prime number. But infinity is not a number and we have a contradiction. If we answer true, then there must be a greatest prime number. But Euclid ...
25
votes
4answers
552 views
About the property of $m$: if $n < m$ is co-prime to $m$, then $n$ is prime [duplicate]
The number $30$ has a curious property:
All numbers co-prime to it, which are between $1$ and $30$ (non-inclusive) are all prime numbers!
I tried searching(limited search, of course) for numbers ...
25
votes
3answers
371 views
Sequence of numbers with prime factorization $pq^2$
I've been considering the sequence of natural numbers with prime factorization $pq^2$, $p\neq q$; it begins 12, 18, 20, 28, 44, 45, ... and is A054753 in OEIS. I have two questions:
What is the ...
25
votes
2answers
793 views
Elementary proof that $2x^2+xy+3y^2$ represents infinitely many primes?
We did in class $x^2+y^2$, which was easy, and we had for homework $2x^2+2xy+3y^2$, which I did (its values (if not square) must be divisible by form primes, or of the form $x^2+5y^2$, and clearly ...
24
votes
1answer
431 views
Are sines of primes dense in $[-1,1]?$
Let $P$ be the set of all prime numbers. Is $\sin(P)$ dense is $[-1,1]?$ How could we approach such a problem?
23
votes
13answers
2k views
Different ways to prove there are infinitely many primes?
This is just a curiosity. I have come across multiple proofs of the fact that there are infinitely many primes, some of them were quite trivial, but some others were really, really fancy. I'll show ...
23
votes
1answer
546 views
How many primes does Euclid's proof account for?
This is a passing curiosity, and I haven't found any duplicates, so I thought I'd share my thoughts.
In the most basic (or at least the most famous) proof of the infinitude of prime numbers, due to ...
23
votes
1answer
833 views
A prime number pattern
The algorithm
Given a natural number $n$ define a procedure as follows:
Generate a list of primes upto and possibly including, $n$
Assign $Z = n$
If $Z > 0$, subtract the largest prime from list ...
21
votes
5answers
1k views
How do you prove that a prime is the sum of two squares iff it is congruent to 1 mod 4?
It is a theorem in elementary number theory that if $p$ is a prime and congruent to 1 mod 4, then it is the sum of two squares. Apparently there is a trick involving arithmetic in the gaussian ...
21
votes
2answers
785 views
Did H. Lebesgue claim “1 is prime” in 1899? Source?
John Derbyshire, in his text "Prime obsession: Bernhard Riemann and the greatest unsolved problem in mathematics" states that
The last mathematician of any importance who did [consider the number ...
21
votes
0answers
415 views
Generalizing Ramanujan's proof of Bertrand's Postulate: Can Ramanujan's approach be used to show a prime between $4x$ and $5x$ for $x \ge 3$
Perhaps, I've been thinking too long about Ramanujan's proof, but it appears to me that his argument can be generalized beyond $x$ and $2x$. My argument below attempts to show that for $x \ge 1331$, ...
20
votes
3answers
833 views
Show that product of primes, $\prod_{k=1}^{\pi(n)} p_k < 4^n$
This an interesting problem my friend has been working on for a while now (I just saw it an hour ago, but could not come up with anything substantial besides some PMI attempts).
Here's the full ...
20
votes
3answers
332 views
Computing the product of p/(p - 2) over the odd primes
I'd like to calculate, or find a reasonable estimate for, the Mertens-like product
$$\prod_{2<p\le n}\frac{p}{p-2}=\left(\prod_{2<p\le n}1-\frac{2}{p}\right)^{-1}$$
Also, how does this behave ...
19
votes
5answers
719 views
a big number that is obviously prime?
I once heard it asserted that $91$ is the smallest composite number that is not obviously composite. The reasoning was that any composite number divisible by $2$, $3$, or $5$ is obviously composite, ...
19
votes
1answer
650 views
Are Primes a Self-Fulfilling Prophecy?
Assume the following process:
Let's start with the set of primes $\{p_k\}$
Then we use the Euler product being equivalent to Riemann's Zeta function
$$
\prod_{p \text{ prime}} \frac{1}{1-p^{-s}} = ...
18
votes
2answers
4k views
Why are very large prime numbers important in cryptography?
Firstly, you guys are awesome, and I learn quite a bit just from reading the questions of others.
Secondly, a friend asked me recently why large primes are important for data security, and I was ...
18
votes
3answers
1k views
Yitang Zhang: Prime Gaps
Has anybody read Yitang Zhang's paper on prime gaps? Wired reports "$70$ million" at most, but I was wondering if the number was actually more specific.
EDIT$^1$:
Are there any experts here who can ...
17
votes
9answers
3k views
Is there possibly a largest prime number?
Prime numbers are numbers with no factors other than one and itself.
Factors of a number are always lower or equal to than a given number; so, the larger the number is, the larger the pool of ...
17
votes
1answer
451 views
A continued fraction involving prime numbers
What is the limit of the continued fraction
$$\cfrac{1}{2+\cfrac{1}{3+\cfrac{1}{5+\cfrac{1}{7+\cfrac{1}{11+\cfrac{1}{13+\cdots}}}}}}\ ?$$
Is the limit algebraic, or expressible in terms of e or ...
17
votes
2answers
495 views
Question about a program generating palindromic prime numbers
I'm a programmer and software designer. I'm definitely not a mathematician and my maths is quite basic.
One of my colleagues challenged me to generate a palindromic prime number, at least 1000 digits ...
17
votes
1answer
426 views
Primes of the form $x^2 +ny^2$ where swapping $x$ and $y$ still gives a prime
I am studying primes of the form $x^2+ny^2$, and i was wondering if there are any known results about the primes of this form such that when you swap $x$ and $y$ you also get a prime. ie for ...
16
votes
4answers
994 views
Percentage of primes among the natural numbers
How high is the percentage of primes in $\mathbb{N}$?
($\mathbb{N} := \lbrace { 1, 2, 3, \ldots \rbrace }$ ; a prime is only divisible by itself and 1 in $\mathbb{N}$)
The percentage has to be lower ...
16
votes
6answers
2k views
Efficiently finding two squares which sum to a prime
The web is littered with any number of pages (example) giving an existence and uniqueness proof that a pair of squares can be found summing to primes congruent to 1 mod 4 (and also that there are no ...
16
votes
5answers
3k views
Is there a known mathematical equation to find the nth prime?
I've solved for it making a computer program, but was wondering there was a mathematical equation that you could use to solve for the nth prime?
16
votes
3answers
865 views
Does iterating $n \to 2n+1$ always eventually produce a prime number?
Is it the case that for every non-negative integer $n$, iterating $n \to 2n+1$ eventually produces a prime number? (This is the same as asking whether for every positive integer $n$, there is a ...
16
votes
3answers
924 views
Prime numbers stretch to infinity, but what about the distance between them?
That is, let $p_n$ be the nth positive prime number. Does $$L = \lim\limits_{n \to \infty} \left( p_{n+1} - p_n \right)$$ equal infinity?
16
votes
2answers
666 views
What is the millionth decimal digit of the (10^10^10^10)th prime?
What is the millionth decimal digit of the $10^{10^{10^{10}}}$th prime?
(This prime is, of course, far larger than the largest currently "known" prime, the latter having nearly 13 million ...
16
votes
3answers
756 views
Two Representations of the Prime Counting Function
The bounty for the best work out of Greg's answer, especially the
"solving for $\pi^*(x;q,a)$ in terms of all $\Pi^*$ functions (tedious but possible)"
part is over. Since Raymond's ...
15
votes
11answers
8k views
Real world applications of prime numbers?
I am going through the problems from Project Euler and I notice a strong insistence on Primes and efficient algorithms to compute large primes efficiently.
The problems are interesting per se, but I ...
15
votes
3answers
1k views
Primes of the form $n^2+1$ - hard?
I met a student that is trying to prove for fun that there are infinitely many primes of the form $n^2+1$. I tried to tell him it's a hard problem, but I lack references. Is there a paper/book ...
15
votes
3answers
1k views
Is a prime number still a prime when in a different base?
Is a prime number in the decimal system still a prime when converted to a different base?
14
votes
3answers
1k views
Is every positive nonprime number at equal distance between two prime numbers?
For example $8$ is in the middle of the interval between $5$ and $11$, $9$ is at equal distance between $7$ and $11$; $10$ between $7$ and $13$.
14
votes
3answers
480 views
RSA in plain English
I'm a computer science student, I'm not a mathematician, I don't know anything about number or group theory.
I'm looking at RSA, and I want to understand it.
I know what Fermats's little theorem and ...
14
votes
2answers
255 views
Prove that for any nonnegative integer n the number $5^{5^{n+1}} + 5^{5 ^n} + 1$ is not prime
My math teacher gave us problems to work on proofs, but this problem has been driving me crazy. I tried to factor or find patterns in the numbers and all I can come up with is that for $n > 0$, the ...
14
votes
2answers
573 views
A Conjecture of Schinzel and Sierpinski
Melvyn Nathanson, in his book Methods in Number Theory (Chapter 8: Prime Number's) states the following:
A conjecture of Schinzel and Sierpinski asserts that every positive rational number $x$ can ...
