Prime numbers are natural numbers greater than 1 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

17
votes
2answers
903 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 ...
17
votes
2answers
531 views

What is the value of $\sum\limits_{i=1}^\infty\frac{1}{p_{p_i}}$ where $p_{i}$ is the $i$th prime?

What is the value of $\sum\limits_{i=1}^\infty\dfrac{1}{p_{p_i}}$ where $p_n$ is the nth prime (and so $p_{p_n}$ is the $k$th prime, where $k$ is the $n$th prime) ? Thus $\frac{1}{3}+\frac{1}{5}+\...
17
votes
1answer
271 views

The n-th prime is less than $n^2$?

Let $p_n$ be the n-th prime number, e.g. $p_1=2,p_2=3,p_3=5$. How do I show that for all $n>1$, $p_n<n^2$?
17
votes
4answers
753 views

$\# \{\text{primes}\ 4n+3 \le x\}$ in terms of $\text{Li}(x)$ and roots of Dirichlet $L$-functions

In a paper about Prime Number Races, I found the following (page 14 and 19): This formula, while widely believed to be correct, has not yet been proved. $$ \frac{\int\limits_2^x{\frac{dt}{\ln ...
17
votes
1answer
471 views

Short intervals with all numbers having the same number of prime factors

How to prove that for some $k, n_0$, for all $n \ge n_0$ it is never the case that all integers in $\{n, n+1, \dots, n + \lfloor (\log{n})^k \rfloor\}$ have exactly the same number of prime factors ...
17
votes
0answers
319 views

Algorithm to find primes up to $n$ in $O\left(\frac{n}{\log n}\right)$?

Consider the problem of given an integer $n$, generating a list of the primes not greater than $n$. An optimized version of the Sieve of Eratosthenes can do such task in $O(n)$, while the more modern ...
17
votes
0answers
422 views

A question about the divisibility of sum of 2 consecutive primes.

Well as I was curious about the sum of $2$ consecutive primes, after proving that the sum for the odd primes always has at least 3 prime divisors, I came up with this question: Find the least ...
16
votes
6answers
23k views

Determine whether a number is prime

How do I determine if a number is prime? I'm writing a program where a user inputs any integer and from that the program determines whether the number is prime, but how do I go about that?
16
votes
4answers
752 views

Why can't $p^p-(p-1)^{p-1}=n^2$ be a square?

Let $p$ be a prime number. Show that $p^p-(p-1)^{p-1}$ can't be a square. In other words, there is no $n\in\mathbb{N}^{+}$ such that $$p^p-(p-1)^{p-1}=n^2.$$
16
votes
6answers
1k views

Prove $a+b+c+d $ is composite

Let $a,b,c,d$ be natural numbers with $ab=cd$. Prove that $a+b+c+d$ is composite. I have my own solution for this (As posted) and i want to see if there is any other good proofs.
16
votes
3answers
2k 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$.
16
votes
2answers
522 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 ...
16
votes
1answer
562 views

Is it possible to assign a value to the sum of primes?

It is possible, by means of zeta function regularization and the Ramanujan summation method, to assign a finite value to the sum of the natural numbers (here $n \to \infty $) : $$ 1 + 2 + 3 + 4 + \...
16
votes
2answers
910 views

Is there an infinite number of primes constructed as in Euclid's proof?

In Euclid's proof that there are infinitely many primes, the number $p_1 p_2 ... p_n + 1$ is constructed and proved to be either a prime, or a product of primes greater than $p_n$. Trivially, we ...
16
votes
3answers
560 views

Solving $p_1^{e_1} p_2^{e_2}…p_k^{e_k}=e_1^{p_1} e_2^{p_2}…e_k^{p_k}$

Find all positive integers $k$, positive integers $e_i$, and distinct prime numbers $p_i$ for $1\le i\le k$, such that $$p_1^{e_1} p_2^{e_2}...p_k^{e_k}=e_1^{p_1} e_2^{p_2}...e_k^{p_k}.$$ Is this ...
16
votes
1answer
200 views

$|3^a-2^b|\neq p$, from a contest

I recently came across an old contest problem: (I did not find the solution anywhere) Find the least prime number which cannot be written in the form $|3^a-2^b|$ where $a$ and $b$ are ...
16
votes
2answers
369 views

Geometric mean of prime gaps?

The arithmetic mean of prime gaps around $x$ is $\ln(x)$. What is the geometric mean of prime gaps around $x$ ? Does that strongly depend on the conjectures about the smallest and largest gap such as ...
16
votes
1answer
391 views

Are all primes Euclid primes?

I was learning Euclid's theorem. If we repeat his construction (properly modified to give only primes) then will we skip any primes? Formally: $p_1 = 2$, and $p_{n + 1} = \text{smallest} \; q \in \...
16
votes
1answer
3k views

Quadratic sieve algorithm

I am stuck with the sieving stage of Quadratic Sieve algorithm. I've read lots of papers to this point but I can't find any guidlines how to choose sieving interval or how sieving is actually done ...
16
votes
2answers
372 views

Is this olympiad-like question about remainders an open problem?

Suppose that we are given two positive integers $x$ and $y$ such that $$x \mod p \leqslant y \mod p$$ for each prime number $p$. (Here, $x \mod p,\; y \mod p$ stand for the least non-negative ...
15
votes
4answers
3k views

Proof: 1007 can not be written as the sum of two primes.

The claim is: 1007 can be written as the sum of two primes. We want to prove or disprove it. Edit: My professor provided this definition in his previous assignment: An integer $n \geq 2$ is ...
15
votes
6answers
3k views

Is an arbitrary number of the form xyzxyz divisible by 7, 11, 13?

So I was given this question Choose any 3-digit number xyz and write it after itself as follows: xyzxyz. Check whether it is divisible by 7,11, 13. Is an arbitrary number of the form xyzxyz ...
15
votes
7answers
3k views
15
votes
3answers
1k views

A condition for being a prime: $\;\forall m,n\in\mathbb Z^+\!:\,p=m+n\implies \gcd(m,n)=1$

If $\;p=m+n$ where $p\in\mathbb P$, then $m,n$ are coprime, of course. But what about the converse? Conjecture: $p$ is prime if $\;\forall m,n\in\mathbb Z^+\!:\,p=m+n\implies \gcd(m,n)=1$ ...
15
votes
4answers
1k views

Prove there are no prime numbers in the sequence $a_n=10017,100117,1001117,10011117, \dots$

Define a sequence as $a_n=10017,100117,1001117,10011117$. (The $nth$ term has $n$ ones after the two zeroes.) I conjecture that there are no prime numbers in the sequence. I used wolfram to find the ...
15
votes
4answers
862 views

Prove that $n^2+n+41$ is prime for $n<40$

Here's a problem that showed up on an exam I took, I'm interested in seeing if there are other ways to approach it. Let $n\in\{0,1,...,39\}$. Prove that $n^2+n+41$ is prime. I shall provide my ...
15
votes
3answers
468 views

A prime of the form $38111111\ldots$

Let $z(n)$ denote the number given by $38$ followed by $n 1$'s. What is the least number $n$, such that $z(n)$ is prime ? With brute force, I checked up to $7000$ digits and did not find a prime. ...
15
votes
5answers
4k views

Proving that there are infinitely many primes with remainder of 2 when divided by 3

I need to prove that there are infinitely many primes with remainder of 2 when divided by 3. I started out similarly to Euclid's classic proof of an infinite number of prime numbers: Suppose there is ...
15
votes
4answers
794 views

Why do repunit primes have only a prime number of consecutive $1$s?

Repunit primes are primes of the form $\frac{10^n - 1}{9} = 1111\dots11 \space (n-1 \space ones)$. Each repunit prime is denoted by $R_i$, where $i$ is the number of consecutive $1$s it has. So far, ...
15
votes
3answers
1k views

Use this sequence to prove that there are infinitely many prime numbers. [duplicate]

Problem: By considering this sequence of numbers $$2^1 + 1,\:\: 2^2 + 1,\:\: 2^4 + 1,\:\: 2^8 +1,\:\: 2^{16} +1,\:\: 2^{32}+1,\ldots$$ prove that there are infinitely many prime numbers....
15
votes
1answer
1k views

Is there a prime number between every prime and its square?

For each prime number $p$, is there always an other prime number between $p$ and $p^2$ ? I tested it for prime numbers $< 500,000,000$, but I wanted to know if there is any mathematical proof of ...
15
votes
3answers
1k views

Finitely many Supreme Primes?

A challenge on codegolf.stackexchange is to find the highest "supreme" prime: http://codegolf.stackexchange.com/questions/35441/find-the-largest-prime-whose-length-sum-and-product-is-prime A supreme ...
15
votes
2answers
265 views

Primes of form $a^2 + 24b^2$

For a prime number $p \neq 2$, $3$, is it necessarily the case the prime number can be written in the form $a^2 + 24b^2$ if and only if $p \equiv 1 \text{ mod }24$? I think this has to be true based ...
15
votes
2answers
2k views

Elementary proof of Zsigmondy's theorem

I've been writing a not-so-short introduction to elementary number theory, supplying proofs for all theorems. When coming across Zsigmondy's theorem, it seemed difficult to find a proof available on ...
15
votes
2answers
785 views

Is there a better upper bound for the primorial $x\#$ than $4^x$

In the classic proof of Bertrand's postulate by Paul Erdős, he shows that $x\# < 4^x$ where $x\#$ is the primorial for $x$. Is there any tighter upper bound for a given primorial $x\#$? Ideally, ...
15
votes
4answers
709 views

Need help understanding Erdős' proof about divergence of $\sum\frac1p$

I'm looking at proofs from Proofs from the Book (Martin Aigner, Günter M. Ziegler). The proof I'm having trouble is the sixth proof of the infinitude of the primes they give (on page 5; although I'll ...
15
votes
1answer
631 views

Can the order of 2 mod p be arbitrarily small (relative to $p - 1$)?

Given a prime number $p$, let $\operatorname{ord}_p(2)$ be the multiplicative order of $2$ modulo $p$, i.e., the smallest integer $k$ such that $p$ divides $2^k - 1$. By Lagrange's theorem, $\...
15
votes
1answer
429 views

Proof of infinitude of primes using the irrationality of π

According to the section Proof using the irrationality of $\pi$ of the Wikipedia article on Euclid's theorem, Euler proved that: $$\frac{\pi}{4}=\frac34\cdot\frac54\cdot\frac78\cdot\frac{11}{12}\cdot\...
15
votes
1answer
397 views

Primey Pascal's Triangle

Imagine that we have a triangle that starts with 2,3 and grows like Pascal's triangle but instead uses the smallest prime $\geq$ to the sum of the above two primes. Visually: $$ \begin{array}{...
15
votes
2answers
215 views

why $ \rm{lcm}[1,2,3,\cdots,n]\in (2^n,4^n)$

Let $n\ge 7$ be positive integers,show that $$f(n)=\rm{lcm}[1,2,3,\cdots,n]\in (2^n,4^n)$$ Anyone know this problem background?or maybe have best proof or best result?
15
votes
1answer
1k views

If the abc conjecture has been proven what implication does that have for elliptic curve cryptography?

I am not a mathematician, but I was wondering if the proposed proof of the abc conjecture (PDF) by Shinichi Mochizuki of Kyoto University would contain insights and mathematical tools that would lead ...
15
votes
1answer
225 views

Consequences of the negation of the Riemann hypothesis

There are many sources documenting the consequences of the Riemann hypothesis, but I can't find one discussing the consequences of its negation, particularly concerning the prime distribution. Can ...
15
votes
1answer
607 views

Going from $\Lambda$ to a prime count

A 1997 paper of Étienne Fouvry and Henryk Iwaniec, Gaussian primes, concerns the prevalence of primes that are of the form $n^2+p^2$ for prime $p$. The asymptotic result is $$\sum_{n^2+p^2\le x}\...
15
votes
0answers
229 views

Continued fraction with prime reciprocal entries

We know that the reciprocals of the primes form a divergent series. We also know that a necessary and sufficient condition for a continued fraction to converge is that its entries diverge as a series. ...
14
votes
6answers
3k views

Prove a number is composite

How can I prove that $$n^4 + 4$$ is composite for all $n > 5$? This problem looked very simple, but I took 6 hours and ended up with nothing :(. I broke it into cases base on quotient remainder ...
14
votes
1answer
1k views

Finding smallest and largest prime factor of $\frac{200!}{180!}$

I originally started off by listing all the primes: $p<200$ then trying to calculate the prime factorisation of each (which I realise is a silly thing to do) I believe there must be a simpler way ...
14
votes
3answers
399 views

$\sum\limits_{\text{prime }p} 2^{-p}$ is an irrational number

I need help to prove the following result. $\displaystyle\sum_{\text{prime }p} 2^{-p}$ is an irrational number.
14
votes
1answer
714 views

How many digits of the googol-th prime can we calculate (or were calculated)?

Here, a lower and upper bound for the $n$-th prime are given. Applying the given bounds $$n(\ln(n\cdot\ln(n))-1)<p_n<n\cdot\ln(n\cdot\ln(n))$$ and the approximation $$p_n\approx n(\ln(n\...
14
votes
3answers
594 views

Are the logarithms in number theory natural?

I find the frequent emergence of logarithms and even nested logarithms in number theory, especially the prime number counting business, somewhat unsettling. What is the reason for them? Has it maybe ...
14
votes
2answers
1k views

Evidence against Goldbach's Conjecture?

It recently occurred to me that, unless I'm much mistaken, Goldbach's conjecture can easily be seen to be equivalent to a seemingly more general statement: Every number $n$ divisible by any $1<...