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.

learn more… | top users | synonyms

132
votes
5answers
16k views

Is $7$ the only prime followed by a cube?

I discovered this site which claims that "$7$ is the only prime followed by a cube". I find this statement rather surprising. Is this true? Where might I find a proof that shows this? In my ...
112
votes
6answers
22k 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 ...
70
votes
5answers
5k 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?
64
votes
13answers
6k views

Infiniteness of non-twin primes.

Well, we all know the twin prime conjecture. There are infinitely many primes $p$, such that $p+2$ is also prime. Well, I actually got asked in a discrete mathematics course, to prove that there are ...
58
votes
2answers
2k views

Least prime of the form $38^n+31$

I search the least n such that $$38^n+31$$ is prime. I checked the $n$ upto $3000$ and found none, so the least prime of that form must have more than $4000$ digits. I am content with a probable ...
49
votes
5answers
5k views

Is this of any real importance to the mathematical scientific community?

I'm a 31 year old engineer, and I've recently came up with a way to exactly predict the probability of the number of prime numbers between two different integers. For example using my way, the number ...
47
votes
4answers
3k 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$, ...
47
votes
3answers
2k views

$5^n+n$ is never prime?

In the comments to the question: If $(a^{n}+n ) \mid (b^{n}+n)$ for all $n$, then $ 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 ...
46
votes
3answers
3k 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 ...
45
votes
11answers
9k views

Why is Euclid's proof on the infinitude of primes considered a proof?

I've expressed Euclid's proof on the infinitude of primes on Mathematica: ...
43
votes
4answers
2k 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 ...
39
votes
7answers
2k views

Is $1$ a prime number?

Is 1 classified as a prime number? And if so, why? If not, why not?
39
votes
2answers
4k views

The square roots of different 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 ...
38
votes
17answers
4k 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 ...
38
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 ...
37
votes
11answers
6k 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.
37
votes
5answers
3k views

Does every prime divide some Fibonacci number?

I am tring to show that $\forall a \in \Bbb P\; \exists n\in\Bbb N : a|F_n$, where $F$ is the fibonacci sequence defined as $\{F_n\}:F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2}$ $(n=2,3,...)$. How can ...
35
votes
1answer
969 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$, ...
34
votes
2answers
441 views

Does $\lfloor \sqrt{p} \rfloor$ generate all natural numbers?

Our algebra teacher usually gives us a paper of $20-30$ questions for our homework. But each week, he tells us to do all the questions which their number is on a specific form. For example, last ...
33
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.
31
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 ...
31
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 ...
30
votes
2answers
6k 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 ...
30
votes
3answers
367 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 ...
30
votes
2answers
615 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
5answers
5k 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 ...
26
votes
2answers
657 views

A beautiful limit involving primes and composites

I observed the following limit empirically. Let $p_n$ be the $n$-th prime and $c_n$ be the $n$-th composite number then, $$ \lim_{n \to \infty}\frac{1}{n}\sum_{i=1}^{n}\frac{p_n c_n}{p_n c_n + ...
26
votes
3answers
483 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 ...
26
votes
1answer
1k 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 ...
25
votes
4answers
615 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
1answer
505 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?
25
votes
1answer
713 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 ...
25
votes
2answers
812 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
831 views

Is $1847^{2013}+2$ really a prime?

The number $1847^{2013}+2$ is a probable prime. Is it really prime? I started primo, but it seems to slow for this task. I noticed that there is a faster program used to find the primes ...
23
votes
5answers
2k 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 ...
23
votes
1answer
720 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}} = ...
22
votes
3answers
2k 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 ...
21
votes
3answers
1k 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 ...
21
votes
1answer
262 views

Is any closed-form representation known for the sum $\sum\limits_{n=1}^{\infty}\frac{\mu(n)\log n}{n^2}$?

Is any closed-form representation known for the sum $\sum\limits_{n=1}^{\infty}\frac{\mu(n)\log n}{n^2}$, where $\mu(n)$ is the Möbius $\mu$-function?
21
votes
2answers
8k 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 ...
21
votes
3answers
389 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 ...
21
votes
2answers
854 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 ...
20
votes
4answers
2k views

Sum of four squares not a prime

Let $ a, b, c, d $ be natural numbers such that $ ab=cd $. Prove that $ a^2+b^2+c^2+d^2 $ is not a prime. I am clueless on this one. I tried contradiction, but didn't get anywhere. Can you help? ...
20
votes
1answer
610 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 ...
20
votes
2answers
921 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 ...
20
votes
2answers
487 views

Primes approximated by eigenvalues?

Consider the matrix starting: $$\displaystyle T = -\begin{bmatrix} +1&+1&+1&+1&+1&+1&+1 \\ +1&-1&+1&-1&+1&-1&+1 \\ ...
19
votes
9answers
4k 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 ...
19
votes
5answers
2k 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 ...
19
votes
5answers
854 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
4answers
2k 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 ...