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

159
votes
5answers
18k 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 ...
125
votes
6answers
23k 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 ...
85
votes
5answers
7k 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?
80
votes
4answers
3k 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 ...
78
votes
15answers
7k 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 ...
54
votes
10answers
3k views

Is $1$ a prime number?

Is 1 classified as a prime number? And if so, why? If not, why not?
52
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$, ...
52
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 ...
51
votes
12answers
10k 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: ...
51
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 ...
51
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 ...
49
votes
17answers
6k 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 ...
47
votes
7answers
5k views

The myth of no prime formula?

Terence Tao claims: For instance, we have an exact formula for the $n^\text{th}$ square number – it is $n^2$ – but we do not have a (useful) exact formula for the $n^\text{th}$ ...
46
votes
3answers
4k views

Do we have negative prime numbers?

Do we have negative prime numbers? $..., -7, -5, -3, -2, ...$
46
votes
2answers
615 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 ...
45
votes
2answers
5k 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 ...
44
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 ...
43
votes
5answers
4k 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 ...
42
votes
2answers
2k views

Does the string of prime numbers contain all natural numbers?

Does the string of prime numbers $$2357111317\ldots$$ contain every natural number as its sub-string?
41
votes
13answers
9k 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.
40
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
3k views

Is $n! + 1$ often a prime?

Related to this question, I wonder how often $n!+1$ is a prime? There is a related OEIS sequence A002981, however, nothing is said if the sequence is finite or not... or anything in that sense...
36
votes
1answer
1k 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$, ...
35
votes
2answers
1k views

Prime powers, patterns similar to $\lbrace 0,1,0,2,0,1,0,3\ldots \rbrace$ and formulas for $\sigma_k(n)$

Some time ago when decomponsing the natural numbers, $\mathbb{N}$, in prime powes I noticed a pattern in their powers. Taking, for example, the numbers $\lbrace 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16 ...
35
votes
2answers
883 views

Proof that $123456789098765432111$ is prime?

The mathematician Charles Weibel asks on his home page the following "fun question": How can you prove that 123456789098765432111 is a prime number? (He notes the fact $$12345678987654321 = ...
35
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 ...
35
votes
1answer
787 views

Estimate for $n$th prime

A good approximation I have found for $p_{n}$ is \begin{align} \int_{2}^{n}\log (x \log (x \log (x)))\ dx\\ \end{align} and seems to be a better estimate than $n \log (n)$. The error term seems to ...
34
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
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
6answers
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 ...
30
votes
3answers
466 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
657 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 ...
30
votes
1answer
625 views

Very tight prime bounds

Is it possible that $$\left|\operatorname{li}(n)-\sum_{k=1}^{\lfloor\log(n)\rfloor}\dfrac{\pi(n^{1/k})}{k}-\log(2)-\dfrac{1}{2}\right|<\dfrac{2\sqrt{n}}{e\log(n)}?$$ Since $$ ...
29
votes
2answers
4k views

Are weird numbers more rare than prime numbers?

By taking a look at the first few weird numbers: $$(70, 836, 4030, 5830, 7192, 7912, 9272, 10430)$$ It is certain that prime numbers occurs more often within this range of numbers. But are weird ...
29
votes
5answers
846 views

Can a Mersenne number ever be a Carmichael number?

Can a Mersenne number ever be a Carmichael number? More specifically, can a composite number $m$ of the form $2^n-1$ ever pass the test: $a^{m-1} \equiv 1 \mod m$ for all intergers $a >1$ ...
28
votes
7answers
2k views

Are Mersenne prime exponents always odd?

I have been researching Mersenne primes so I can write a program that finds them. A Mersenne prime looks like $2^n-1$. When calculating them, I have noticed that the $n$ value always appears to be ...
28
votes
3answers
561 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
2answers
11k 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 ...
26
votes
2answers
692 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
5answers
3k 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 ...
26
votes
2answers
826 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 ...
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
15answers
26k 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 ...
25
votes
4answers
629 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
535 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
797 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}} = ...
25
votes
1answer
800 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
1answer
899 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
6answers
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 ...