Questions where prime numbers play a key-role, such as: questions on the distribution of prime numbers (twin primes, gaps between primes, Hardy–Littlewood conjectures, etc); questions on prime numbers with special properties (Wieferich prime, Wolstenholme prime, etc.). This tag is often used as a ...

learn more… | top users | synonyms

2
votes
0answers
142 views

Best known Upper bound on Twin Primes [duplicate]

I know that there is a result from J Wu that the number of twin primes less than a given magnitude $N$ does not exceed $$\frac{2aCN}{\log^2{N}}$$ Where $C=\prod \frac{p(p-2)}{(p-1)^2}$ and $a$ is ...
33
votes
2answers
2k views

A question on maps from $\mathbb{Z}/p\mathbb{Z}$ to itself

Let $p\geq 3$ be a prime number, and let $u:\mathbb{Z}/p\mathbb{Z}\to \mathbb{Z}/p\mathbb{Z}$ be a map such that, for all $l\in \mathbb{Z}/p\mathbb{Z}$,$l\neq 0$, the map $k\mapsto u(k+l)-u(k)$ is a ...
17
votes
1answer
767 views

Infinitely many primes, and Mobius randomness in sparse sets

Problem 1: Find a (not extremely artificial) set A of integers so that for every $n$, $|A\cap [n]| \le n^{0.499}$, ($[n]=\{1,2,...,n\}$,) where you can prove that $A$ contains infinitely many primes. ...
2
votes
1answer
494 views

Prime numbers of a special kind

Is it proved that there is only a finite number of prime numbers of the form $2^{2n} + 2^n + 1$ (where $n \in \mathbb{N}$)?
9
votes
1answer
515 views

A conjecture by Euler about $8n+3$

Euler's conjecture: For any positive integer $n$, $8n+3$ can be represented as a sum $$8n+3=(2k-1)^2+2p,$$ where $k$ is a positive integer, and $p$ is a prime. I want to know whether there has been ...
5
votes
2answers
431 views

General Euclid-Fermat sequences

Question Fermat sequence $$ \forall_{n=1\ 2\ \ldots}\quad F_n:=2^{2^{n-1}}+1$$ has every two different terms relatively prime, and   $1$   does not appear as any of them. Thus it would be ...
12
votes
2answers
726 views

An Euler-proof that cannot be repaired?

Ed Sandifer writes on Euler's wonderful work on prime numbers: The sum of the series of reciprocals of prime numbers $\frac{1}{2}+\frac{1}{3}+\frac{1}{5}+...$ is infinitely large, and is infinitely ...
8
votes
1answer
602 views

Density of prime pairs whose gap is less than the average gap

By the prime number theorem we know that the "average gap" between the first $n$ primes is $\ln p_n$. I would like to know the density of consecutive prime pairs whose gap is less than the average gap ...
1
vote
0answers
130 views

Division between deformed Gausian integers

Let $P_3=${$z\in Z[\sqrt{-3}],|z|^2 \text { is a prime number}, >3$} Let $\alpha_1,...\alpha_n$ be distinct elements in $P_3$, and $l_1,...l_n\in Z^+$. Set ...
2
votes
0answers
315 views

On the primitive prime divisors of $q^n-1$

Let $q=p^\alpha$ be a prime power. We call $r$ a primitive prime divisor of $q^n-1$ where $r\mid (q^n-1)$ but $r\nmid (q^i-1)$ for each $1\leq i\leq n-1$. The set of all primitive prime divisors of ...
1
vote
1answer
92 views

On the set of divisors of $q-1$ and $q'-1$

For a natural number $n$ we denote by $\pi(n)$, for the set of prime divisors of $n$. Let $q=p^\alpha$ and $q'=r^\beta$ where $r$ and $p$ are odd prime numbers and $\alpha,\beta$ are natural numbers. ...
0
votes
1answer
216 views

For any n and some prime p there is an elemnet in Zp* of order n [closed]

How can I prove, that for any positive integer $n>0$ there is a prime $p$, such that the multiplicative group of the residue ring $Z_p^*$ contains an element $a$ of order $n$? No ideas at all...
6
votes
0answers
598 views

Would the following conjectures imply Cramer's conjecture?

Assume Goldbach's conjecture. Then for every $n\ge 2$ there exists at least one non-negative integer $r\le n-2$ such that both $n+r$ and $n-r$ are primes. Let's write $r_{0}(n):=\inf\{r\le n-2, ...
-1
votes
1answer
318 views

Mersenne Prime Sequences

Hi. Given the following sequence (of Mersenne primes): $ A_{1} = 2 $ $ A_{n} = 2^{A_{n-1}} - 1 $ The first five elements are all prime numbers: $ 2 $ $ 2^{2}-1=3 $ $ 2^{3}-1=7 $ $ 2^{7}-1=127 ...
2
votes
2answers
778 views

Finding primes using Euler's sum of divisors recurrence relation

Euler came up with following recurrence relation for the sum of divisors (refer to http://arxiv.org/abs/math/0411587) $$\sigma(n) = \sigma(n−1) + \sigma(n−2) − \sigma(n−5) − \sigma(n−7) \dots$$ Since ...
3
votes
1answer
329 views

The Nth number with M prime factors

Hi. Suppose we arrange all natural numbers in a matrix P defined as follows: P[I][J] = The Jth number with I prime factors. So P looks something like: 1 2 , 3 , 5 , 7 , 11 , 13 , 17 ...
0
votes
0answers
136 views

Prime-Counting Function

Would a summation of floor[cos^2π(((j-1)!+1)/j)] from j=1 to x be the same as π(x)?
1
vote
1answer
159 views

Behavior of a quantity related to Fermat's 4n + 1 Theorem

One of Fermat's theorems states that if $p = 4n + 1$ for some integer $n$, then $p$ can be expressed uniquely as a sum of two squares, $p = a^2 + b^2$. I am working on a problem and I would like to ...
3
votes
1answer
258 views

Primes in short intervals with a preassigned frobenius

Edited after mistake in the first version. It is known since Selberg that under the Riemann Hypothesis, given an $\epsilon>0$, there is a prime between $x$ and $x+O(x^\epsilon)$ for all $x$ in a ...
8
votes
0answers
675 views

Would the following conjectures imply $\lim\inf_{n\to\infty}p_{n+k}-p_{n}=O(k\log k)$?

Assume Goldbach's conjecture. Then for every $n\ge 2$ there exists at least one non-negative integer $r\le n-2$ such that both $n+r$ and $n-r$ are primes. Let's write $r_{0}(n):=\inf\{r\le n-2, ...
1
vote
1answer
983 views

The Jones-Sato-Wada-Wiens polynomial for prime numbers and differential calculus?

After works of Davis, Matijasevic, Putman and Robinson between 1960 and 1970, we know that every recursively enumerable set of numbers can be represented by a polynomial. In particular, it's the case ...
3
votes
1answer
370 views

Heuristic for Montgomery's conjecture

This is my third question on this site regarding Montgomery's conjecture -- and I apologize if this is too much -- but I am still not understanding well why this conjecture is believed to be true. ...
63
votes
6answers
6k views

Does Zhang's theorem generalize to $3$ or more primes in an interval of fixed length?

Let $p_n$ be the $n$-th prime number, as usual: $p_1 = 2$, $p_2 = 3$, $p_3 = 5$, $p_4 = 7$, etc. For $k=1,2,3,\ldots$, define $$ g_k = \liminf_{n \rightarrow \infty} (p_{n+k} - p_n). $$ Thus the twin ...
16
votes
1answer
4k views

Tightening Zhang's bound

Inspired by a blogpost by Scott Morrison and ongoing discussion there I decided to create this community wiki to track progress on the original bound of Yitan Zhang. The original bound was ...
4
votes
1answer
579 views

Goldbach's conjecture and Euler's idoneal numbers

Recently, I stumbled upon an interesting statement regarding Quadratic Forms. It is quite well-known and, as I will describe briefly, equivalent to Goldbach's conjecture. Let $p,q$ be odd primes and ...
19
votes
4answers
4k views

How does Yitang Zhang use Cauchy's inequality and Theorem 2 to obtain the error term coming from the $S_2$ sum

I have been reading Yitang Zhang's paper now for one and a half weeks and also volunteered to give a popular talk on the paper next week at Stockholm University. Today I found a detail in the proof ...
12
votes
2answers
1k views

Distinctive property of the primes 17 and 19?

Consider the question whether it is true that a prime number $p$ divides $1^1+2^2+3^3+....+(p-1)^{p-1}$ if and only if $p \in \{17,19\}$. For the obvious heuristic reasons, for large $n$ one would ...
8
votes
3answers
527 views

Asymptotic bounds on $\pi^{-1}(x)$ (inverse prime counting function)

What are the current best asymptotic bounds on $\pi^{-1}(x)$, where $\pi(x)$ denotes the prime counting function (number of primes at most $x$)? In other words, I am curious about the state of the ...
2
votes
1answer
226 views

Given an even integer N, what is the minimum set of primes such that any even number x <= N can be expressed as the sum of two primes from the set?

Given an even integer N, what is the minimum set of primes such that any even number $x \leq N$ can be expressed as the sum of two primes in the set? Goldbach's conjecture said Every even integer ...
4
votes
1answer
232 views

Estimate on the prime-counting function $\psi(x)$.

There is an elementary statement that I believe I have read somewhere, but I can't remember where. I'd like to know if the statement is correct (in which case it is surely standard) and if so, where I ...
4
votes
2answers
289 views

Are sums of the inverses of prime siblings finite?

PART I (Initial version) Let   $P$   be the set of all primes   $2\ 3\ \ldots$.   Let $$P_d\ \ :=\ \ \{\ p\in P\ :\ \exists_{q\in P}\ \ 0 < |p-q|\le d\ \}$$ and $$S_d\ :=\ ...
22
votes
1answer
1k views

Permutations of $(Z/pZ)^*$

Let $p$ be a prime integer, and let $(\mathbb Z/p\mathbb Z)^*$ be the set of non-zero elements of $\mathbb Z/p \mathbb Z$. Denote by $S((\mathbb Z/p \mathbb Z)^*)$ the group of permutations of ...
70
votes
4answers
26k views

Philosophy behind Yitang Zhang's work on the Twin Primes Conjecture

Yitang Zhang recently published a new attack on the Twin Primes Conjecture. Quoting Andre Granville : “The big experts in the field had already tried to make this approach work,” Granville ...
6
votes
6answers
826 views

Sequences equidistributed modulo 1

Let $\alpha$ be any positive irrational and $\beta$ be any positive real. We have the following results. H. Weyl (1909): The fractional part of the sequence $\alpha n$ is equidistributed modulo 1. ...
4
votes
1answer
457 views

p such that p+1 has a large prime factor, effectively

I was reading the Boneh-Franklin IBE paper, and it seemed rather conspicuous to me that they didn't address the question of how to find primes $p$ and $q$ satisfying what they need (on page 19). ...
0
votes
1answer
418 views

A possible consequence of Dirichlet's theorem about primes in arithmetic progression

EDIT : I copy-paste the beginning of a previous question since Gerry Myerson suggested this question should be self-contained. "let's consider a composite natural number $n$ greater or equal to $4$. ...
7
votes
1answer
176 views

Composing two-term sums from the same primes

The following is an old result of Erdős and Turán (American Mathematical Monthly, 1934): Given a set of $2^n + 1$ distinct positive integers, all of its two-term sums cannot be composed of the same ...
0
votes
4answers
320 views

The prime number $2$ [duplicate]

Possible Duplicate: Why is 2 so odd? I have read few books and articles, almost all of them refer that any prime $p>2$. Just wondering why it has to be $>2$?
2
votes
1answer
471 views

To express $e^{\sum \limits_{k=0}^\infty q^{2^k}}$ as product terms of $(1-q^k)^{c(k)}$

$|q|\lt1$ $A(q)=\sum \limits_{k=0}^\infty q^{2^k}$ Easily We can see that $$A(q)=q+A(q^2)\tag 1$$ Let's assume we redefine $A(q)$ as below $A(q)=-\sum \limits_{k=1}^\infty c_k \ln{(1-q^k)}$ I ...
2
votes
3answers
410 views

Is it true that $p^2+1$ is square free if $p>7$ is a Mersenne prime

For a problem in group Theory I need some information about the Mersenne primes: Let $p=2^a-1>7$ be a Mersenne prime and so $a$ is an odd prime. Is it true that $p^2+1$ is square free. i.e. if ...
5
votes
2answers
281 views

Does group of 4 equidistant successive prime exists ?

For example Group of 2 equidistant successive primes 3,5,7 distance 2 151,157,163 distance 6 Group of 3 equidistant successive primes ...
0
votes
1answer
262 views

Factorization of $p^2+1$ where $p$ is a Mersenne prime

Let $p=2^a-1$ be a Mersenne prime and so $a$ is an odd prime if $p>7$. We know that if $p=7$, then $(p^2+1)/2$ is equal to $5^2$. Can we prove that if $p>7$ , then $(p^2+1)/2$ is not equal to ...
3
votes
1answer
275 views

Least non primitive root

There is an abundant literature, and even here on MO no shortage of questions, on the question of the smallest prime primitivee root modulo $q$ (where $q$ is a prime, or more generally an odd prime ...
4
votes
3answers
270 views

A divergent series related to the number of divisors of of p-1

Let $d(n)$ denote the number of divisors of $n$. Is it known that the series $$\sum_{p \text{ prime}} \frac{1}{d(p-1)}$$ diverges? This would follow immediately from the Sophie Germain Conjecture. ...
1
vote
1answer
191 views

What are the best known lower and upper bounds for the second Chebyshev function $\psi(x)$

I was reading through Jitsuro Nagura's proof that there is always a prime between $x$ and $\frac{6x}{5}$ when $x \ge 25$. In the paper, he uses the following bounds for the second Chebyshev function ...
5
votes
2answers
324 views

special primes with p'=4p+1

How can I most quickly find a big prime, p, for which 4p+1 is also prime? For example, p=37 works. I wonder if these special primes have been researched and some characteristics are known. Are ...
4
votes
1answer
288 views

A “bit” of primes

Is there anything known/proved/conjectured about the distribution of: $$B(n) = \frac{(p_n-1)}{2} \bmod 2, \qquad p_n \mbox{ is the } n\mbox{-th prime}$$ i.e. the bit 1 of the binary representation ...
2
votes
0answers
119 views

Two products over primes

For $k \in \mathbb{N}$ define $$ f(k) = \prod_{\text{p prime}}\left(1+\frac{1}{p^k(p^k+1)}\right)$$ $$ g(k) = \prod_{\text{p prime}}\left(1+\frac{1}{p^k(p^k-1)}\right)$$ By the product for zeta ...
6
votes
2answers
600 views

At what point would an elementary generalization of Bertrand's Postulate be interesting?

I know that in 1952 Jitsuro Nagura was able to show that there is always a prime between $k$ and $\frac{6k}{5}$ for $k > 24$. At what point would an improvement on Nagura's result be interesting? ...
6
votes
2answers
732 views

Approximate number of primes below a given integer?

The problem of the complexity of the exact counting problem for primes is interesting. The best result we have about primes is that it is hard for TC0. But counting the number of witnesses to a TC0 ...