Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
Join us in building a kind, collaborative learning community via our updated Code of Conduct.

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 ...

0
votes
0answers
62 views

How to prove a Mersenne number is not pseudoprime to the base 3?

I start think in finding a small divisor $p$ of $M_n$ then I obtain that $p\mid (3^{M_{n}-1}-1)$ hence $ord_{p}(3)\mid M_{n}-1$ Now can I prove p is the same as $M_{n}$ so that $M_{n}$ is not ...
-1
votes
1answer
118 views

The power of a prime in the prime factorization of a factorial [on hold]

How do we find—for example—how many $5$s are in the prime factorization of $n!$? I've read that it is $\lfloor n/5 \rfloor$, but why is that?
0
votes
0answers
51 views

Decomposition of prime into $q \cdot r + s$, where $q,r,s$ are primes

Moments ago I created a following conjecture: If $p$ is prime different from $2,3,5,7$ then there exist primes $q,r,s$ such that $q<p$ and $r<p$ and $s<p$ and $p=q \cdot r +s$. Is this true?...
-4
votes
0answers
244 views

About a pattern on prime numbers [on hold]

I have read in https://www.sciencealert.com/mathematicians-discover-a-strange-pattern-hiding-in-prime-numbers that says: "But this doesn't explain the magnitude of the bias the team found, or why ...
-6
votes
0answers
82 views

About inverse function of π(x) (the prime counting function) [closed]

If for a given π(prime(n)) or f(π(prime(n))), we can find prime(n), is this enough to help on solve RH?
8
votes
1answer
813 views

Are there infinitely many primes of this form?

The semiprime $87 = 3*29$ has a curious property: it's the fact that both $87^2 + 29^2 + 3^2 = 8419$ and $87^2 - 29^2 - 3^2 = 6719$ are prime numbers. This intrigued me and led me to wonder if ...
3
votes
1answer
164 views

A specific Diophantine equation restricted to prime values of variables.

Consider the following Diophantine equation $$x^2+x+1=(a^2+a+1)(b^2+b+1)(c^2+c+1).$$ Assume also that $x,a,b,c,a^2+a+1,b^2+b+1, c^2+c+1$ are all primes. We'll call such a quadruplet $(x,a,b,c)$ a ...
3
votes
1answer
87 views

Higher roots modulo prime complexity best algorithm

Given integers $a,\ell$ and prime $p$ we need to find the roots of the algebraic equation $x^\ell\equiv a\bmod p$. We know there are at most $\ell$ such $x$. What is the best method to find all such ...
5
votes
1answer
290 views

Does every prime $p$ appear in a $p$-term arithmetic progression of primes? [duplicate]

This is a follow-up to an earlier question. The answer to that question was found on this page. The discussion on OEIS seems to suggest that, for any prime $p$, there should exist a $p$-length ...
29
votes
4answers
3k views

Is there an 11-term arithmetic progression of primes beginning with 11?

i.e. does there exist an integer $C > 0$ such that $11, 11 + C, ..., 11 + 10C$ are all prime?
12
votes
1answer
252 views

Determine $2^{\frac{p-1}{4}}\equiv 1\pmod p$ or $2^{\frac{p-1}{4}}\equiv -1\pmod p$ when $p\equiv 1 \pmod 8$

Let $p=8k+1\equiv 1\pmod 8$ be a prime, thus $2$ is a quadratic residue module $p$. Euler's criterion show that $$2^{\frac{p-1}{2}}\equiv 1 \pmod p.$$ So we must have $$2^{\frac{p-1}{4}}\equiv \...
6
votes
2answers
356 views

Primality test for specific class of Proth numbers

Can you provide a proof or a counterexample for the following claim : Let $P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)$ Let $N=k\cdot 2^n+1$...
-3
votes
1answer
205 views

Is it true that there are infinite palindromic primes that when squared give palindromic number? [closed]

Can you prove that there are infinite palindromic primes that when squared give a palindromic number?
6
votes
0answers
114 views

$p >2$ is a prime, any facts about congruence relation between the class number of $Q(\sqrt p)$ and $Q(\sqrt-p)$?

Let $p$ be an odd prime. This is a question about the class number of $Q(\sqrt p)$ and $Q(\sqrt-p)$,which we denote by $h(p)$ and $h(-p)$ respectively. While doing my research on number theory I came ...
7
votes
1answer
313 views

Goldbach's conjecture for the Liouville function

Is it true that for every even integer $N > 2$, there exist positive integers $a,b$ such that $a + b = N$ and $\lambda(a) = \lambda(b) = -1$ ? Here $\lambda$ is the Liouville function.
0
votes
0answers
94 views

Does this recurrence yields only prime numbers?

The title of this question is merely illustrative, since I do not expect an answer by yes or not, but I seek some reference on the subject. In this article: https://pdfs.semanticscholar.org/e9be/...
4
votes
1answer
313 views

Density of integers with a large rough divisor

Let $N < 2^a$ be a positive integer chosen uniformly at random. Let $\tilde{N}$ be the result of removing from $N$ all its prime factors less than $2^b$. What is the probability that $\tilde{N}$ is ...
6
votes
1answer
181 views

Can a primitive root-permutation of $A=\{1, 2, \ldots, p-1 \}$ be a cycle of length $p-1$ only for finitely many $p$?

Let $p$ be an odd prime, $g$ a primitive root of $p$ and $A=\{1, 2, \ldots, p-1 \}$. Obviously, $\sigma_g(p)=\begin{pmatrix} 1 & 2 & \ldots & {p-1} \\ g^1\pmod{p} & g^2\pmod{p} &...
10
votes
1answer
442 views

How many zeta zeros are needed to accurately calculate five digits for π(1000000), where π(x) is the prime counting function?

John Derbyshire in his book PRIME OBSESSION says on page 343: "I’ll round off with a complete calculation of $\pi(1,000,000)$, the number of primes up to one million, using Riemann’s formula -- ...
6
votes
1answer
205 views

Upperbounding a sum of Legendre-Symbols

Let $p$ be a prime with $p\equiv 3 \mod 4$, for any $\mathcal{I} \subset \lbrace 0,...,p-1 \rbrace $ and any $\mathcal{J} \subset \lbrace 0,...,p-1 \rbrace $ with $\vert\mathcal{I}\vert \leq \sqrt{p} $...
-2
votes
0answers
56 views

Left-right discrepancy in a short interval containing k0 primes

Assuming Goldbach's conjecture, let $ r_{0}(n) : =\inf\{r\geq 0,(n-r,n+r)\in\mathbb{P}^{2}\} $ , $ k_{0}(n) : =\pi(n+r_{0}(n))-\pi(n-r_{0}(n)) $ , $ k_{0}^{+}(n) : =\pi(n+r_{0}(n))-\pi(n) $ and $ ...
4
votes
1answer
386 views

Reference for inequality for $\sum\limits_{d \mid n}\frac{\log d}{d}.$

Let $f(n)=\sum\limits_{d \mid n}\frac{\log d}{d}.$ It is not hard to see that $f(n)\ll(\log\log n)^2$. Is there any reference for this inequality? EDT 1: A possible answer is Analysis of the ...
2
votes
2answers
146 views

Sum of a terms in a divergent series taken along indices the sum of whose reciprocal diverges. Can the sum converge?

Let $\{x_n\}_{n=1}^{\infty}$ be a monotone decreasing sequence of positive real numbers such that $\sum_{n=1}^{\infty} x_n$ diverges. Also let $\{k_n\}_{n=1}^{\infty}$ be a strictly increasing ...
10
votes
1answer
348 views

Spacing of fractions with prime denominator

Let $X\ge 2$ be large. Let $$A = \left\{\frac{a}{q}: 1\le a < q\le X,\ (a, q) = 1\right\},$$ and let $$B = \left\{\frac{a}{p}: 1\le a < p\le X,\ (a, p) = 1,\text{ and $p$ is prime}\right\}.$$ ...
4
votes
1answer
348 views

Is there some numerical evidence that $ \pi(x+x^{1/e})-\pi(x)\geq 1 $ for any large enough $ x $?

Disclaimer : the following reasoning is a physicist's one and as such may not be suitable for this website. Still it may give rise to potentially interesting insights so I ask it anyway. I stumbled ...
3
votes
0answers
119 views

Cancellation in this exponential sum?

I would like to know whether it is possible to obtain cancellation in the sum $$\sum_{p \leq X} e^{{2\pi iX}/{p}}$$ where $X$ is a real number that goes to $\infty$, and $p$ denotes a prime number.
0
votes
1answer
94 views

Is $P_{2n} \ge 2P_n$ and $\pi(2x) \le 2\pi(x)$ inconsistent to the Prime k-tuple conjecture?

I posed a conjecture as follows that is a special case of Second Hardy–Littlewood conjecture: For $n, x \ge 2$ be two integers then: $$P_{2n} \ge 2P_n$$ and $$\pi(2x) \le 2\pi(x)...
0
votes
1answer
110 views

Sergei numbers : even integers n being a prime gap at least n times

Let's introduce Sergei (for SElf-Referential Gaps Extensible to Infinity, and as a wink to a mathematician friend of mine of Russian descent whose given name is Serge and quite interested in number ...
-3
votes
1answer
163 views

Can this weakening of Polignac's conjecture be proven?

Let $ A $ be a set of odd primes such that between any two consecutive elements thereof there is at least one prime gap that occurs infinitely often, i.e. an even integer $ g $ such that the ...
12
votes
2answers
1k views

Is every odd positive integer of the form $P_{n+m}-P_n-P_m$?

I am looking for a comment, reference, remark, or proof of three conjectures as follows: Conjecture 1: Let $x$ be an odd positive integer. Then there exist two integers $n, m \ge 2$ so that $$x=...
5
votes
1answer
481 views

Prove: If $P_n$ is $n$-$th$ prime number then $P_{n+m} \ge P_n+P_m$

Let $n > 1$ and $m > 0$ be two integers and $P_n$ be the $n^{th}$ prime. Prove: $$P_{n+m} \ge P_n + P_m .$$ Can you give a hint, reference, comment, or proof?
1
vote
0answers
92 views

Primes approximated by eigenvalues?

Let the matrix $T$ be defined by: $$\displaystyle T(n,k) = -\varphi^{-1}(\operatorname{GCD}(n,k))$$ where $\varphi^{-1}$ is the Dirichlet inverse of the Euler totient function. $$\varphi^{-1}(n) = \...
5
votes
2answers
708 views

$\pi((n+1)^2)-\pi(n^2) \le \pi(n)$ for all $n \ge 370$?

There are some conjectures of the form: There always exist at least $X$ prime numbers between $A$ and $B$. Examples: Bertrand's postulate: for every $n>1$ there is always at least one prime $p$ ...
4
votes
2answers
161 views

Example of concrete statement which requires probabilistic algorithm

In my paper I would like to include an example of easy concrete finitary statement which can be easily verified by probabilistic algorithm to any reasonable confidence level, but which looks ...
8
votes
2answers
393 views

Sign of permutation induced by modular exponentiation

Given a prime number $p$ and a primitive root $a$ modulo $p$, let $\sigma_{a,p}$ denote the permutation of the set $\{1, \dots, p-1\}$ which maps $b$ to $a^b$ modulo $p$. Question: Let $p$ be fixed. ...
0
votes
2answers
156 views

Prime factors of a sequence of integers which differ by consecutive prime differences

[Edited following Gerhard's answer. I had forgotten to state a crucial assumption; my apologies for the confusion. I have reworded slightly to try to make things clearer.] Let $p$ be the $k$-th odd ...
2
votes
0answers
182 views

Can we efficiently factor $n$ given that $n=pq$ where $p,q$ are primes satisfying $p=a^2+b^2, q=2ab+1$ for some $a,b$

Suppose we're given a particular number $n \in \mathbb{N}$. We're also given that $n=pq$ where $p,q$ are unknown primes satisfying $$ p=a^2+b^2 $$ and $$ q=2ab+1 $$ for some $a,b$. Is there an ...
3
votes
0answers
127 views

A Jacobian pair $(p,q)$ such that $\gcd(\deg(p),\deg(q))=2P$, $P \geq 5$ is prime

Let $p=p(x,y),q=q(x,y) \in \mathbb{C}[x,y]$ be a Jacobian pair, namely, $p_xq_y-p_yq_x \in \mathbb{C}^*$. Denote $a:= \deg(p)$ and $b:= \deg(q)$, where $\deg()$ denotes the total degree ($(1,1)$-...
2
votes
1answer
259 views

Sum of reciprocals of integers minus primes

For any integer $m>2$, let $P_m$ be the set of primes less than $m$, and let $$ f(m) = \sum\limits_{p \in P_m} \frac{1}{m-p}. $$ For example, $f(3)=\frac{1}{3-2}=1$, $f(4)=\frac{1}{4-2}+\frac{1}{4-...
1
vote
1answer
86 views

On the regularity of integer solutions of a simultaneous equation with consecutive prime coefficients

Let $p_1$ through $p_6$ be consecutive primes in ascending order, and consider the simultaneous equation $$p_1x+p_2y=p_3\\p_4x+p_5y=p_6$$ Motivating Question: For what $p_1$ does the system provide ...
0
votes
1answer
144 views

On the largest prime factor of $1+n^k$

For every positive integer $n>1$ , let $f(n)$ denote the largest prime factor of $n$. How fast does $f(1+n^k)$ grow with respect to $k$ ? Is it true that $f(1+n^k) > 2k, \forall n >2, \forall ...
4
votes
1answer
509 views

Are all the numbers $\pi(n^2)/n^2\ (n=1,2,3,\ldots)$ pairwise distinct?

For $x>0$ let $\pi(x)$ denote the number of primes not exceeding $x$. A well-known conjecture of Legendre states that $\pi(n^2)<\pi((n+1)^2)$ for any positive integer $n$. Here I ask the ...
0
votes
0answers
100 views

Does each prime $p>3$ have a quadratic nonresidue which is a Mersenne number?

Recall that the Mersenne numbers are those integers $M_p=2^p-1$ with $p$ prime. QUESTION: Is it true that for each prime $p>3$ there is a Mersenne number which is a quadratic nonresidue modulo $p$?...
3
votes
0answers
104 views

Number of prime differences

Has any progress been made since Chen on bounding \begin{equation*} G(n) = \#\{\epsilon N < p_1, p_2 \leq N: n = p_1 - p_2\} \end{equation*} from above? As far as I can tell, the best upper ...
2
votes
1answer
270 views

Use of weights in the GPY's and Tao-Maynard's work on the twin prime conjecture

I am going through James Maynard's paper, Small Gaps between Primes, and have a number of questions regarding his approach. First, I am wondering why uses weights in his approach. While I generally ...
0
votes
0answers
102 views

Mobius function on values of an irreducible quadratic polynomial

Are there infinitely many integers $n$ for which $n^2 + 1$ is square-free, and has an even number of (necessarily distinct) prime factors ?
2
votes
0answers
116 views

On primitive roots of the form $5^k+10^m$ with $k$ and $m$ nonnegative integers

Let $p$ be any prime. It is well known that the set $$G_p=\{0<g<p:\ g\ \text{is a primitive root modulo}\ p\}$$ has cardinality $\varphi(p-1)$, where $\varphi$ is Euler's totient function. It is ...
2
votes
0answers
92 views

What is the regularized sum of the following series (sum of all primes but spaced with zeros in place of non-primes)?

The sum over primes: $$\sum_{k=0}^\infty \{\text{k if k is prime, 0 otherwise}\}$$ I know that there is no known method to ascribe a reasonable value to the sum of the primes https://www.quora.com/...
2
votes
0answers
87 views

Does each odd prime $p$ have a primitive root $g < p$ which is the sum of two central binomial coefficients?

The central binomial coefficients are those integers $$\binom{2n}n=\frac{(2n)!}{(n!)^2}\ \ \ (n=0,1,2,\ldots).$$ QUESTION: Does each odd prime $p$ have a primitive root $g<p$ which is the sum of ...
1
vote
0answers
112 views

Common primitive roots modulo several primes

Motivated by the Chinese Remainder Theorem, I'm interested in common primitive roots modulo several primes. Let's first look at common primtive roots modulo two distinct primes. For any distinct ...