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

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

-3
votes
0answers
51 views

Number theory, discrete mathematics [on hold]

Let m>=2 be a prime number. Let x be any integer that is not congruent to 0(mod m). Show that there is a unique integer y which is less than m such that xy is congruent to 1(mod m). I've worked out a ...
2
votes
1answer
131 views

The largest number $y$ such that $(x!)^{x+y}|(x^2)!$

Since the multiplication of $n$ consecutive integers is divided by $n!$, then $(n!)^n|(n^2)!$ with $n$ is a positive integer. Are there any formula of the function $y=f(x)$ that shows the largest ...
7
votes
1answer
154 views

For which primes does this iterated function act transitively? (Sort of a finite analogue of Collatz conjecture.)

Background: I was trying to prove something having to do with cyclic group actions on matroids and was able to show that what I want holds if a particular elementary-looking number-theoretic property ...
1
vote
1answer
579 views

Is every prime greater than 5, less than the sum of the two previous primes?

Can one prove by elementary means (such as Paul Erdös' proof of Bertrand's Postulate) that every prime greater than 5 is less than the sum of the two primes immediately preceding it?
5
votes
1answer
288 views

consecutive prime gaps and explicit bound

I am aware of the theorem that $p_{n+1}- p_n \leq n^{0.525}$ which is true for all sufficiently large numbers due to Baker, but if i want to make the implicit "for all sufficiently large numbers" ...
6
votes
1answer
196 views

Prime plus square equals prime

Furstenberg–Sárközy's theorem states that if a set of positive integers has positive upper density, then there exists (infinitely many) pair of elements of the set, whose difference is a perfect ...
6
votes
0answers
100 views

Does the primality of the number of dimensions affect its properties?

Motivated by How does the parity of a dimension affect its properties? I dare to ask the following question (with thanks to my colleague Vedran Dunjko): We happen to live in a world of prime ...
1
vote
1answer
74 views

How many iterations the best biprime factoring method has to factor a number [closed]

I'm researching method of biprime number factoring. I have a biprime number 1012322327 * 1115382761 (19 decimal digits= 1129126872111204847). I'd like to know how many iterations (or trials) the best ...
-1
votes
0answers
61 views

$ \alpha $ s.t. $ (1-\varepsilon)\log^{\alpha}p_{n}\lt g_{n}\lt(1+\varepsilon)\log^{\alpha}p_n $ is dense in some open interval centered on $1$

Say a real $ \alpha $ such that the proportion of $ n $ such that $ (1-\varepsilon)\log^{\alpha}p_{n}\lt p_{n+1}-p_{n}\lt(1+\varepsilon)\log^{\alpha}p_{n} $ is a positive increasing function of $0\...
12
votes
3answers
727 views

Stronger versions of Wilson's Theorem

Problem Let $c \in \mathbb{N}$ $;$ $\exists$ a prime $p$ for which: $$p^c \mid (p-1)!+1$$ Does $\exists$ $M$ $\in$ $\mathbb{N}$ $;$ $\forall$ $c \geqslant M$ $;$ $\nexists$ $p$ ...
0
votes
0answers
233 views

Conjectured primality tests for specific classes of $k\cdot b^n \pm 1$

Can you provide proofs or counterexamples for the claims given below? Inspired by Lucas-Lehmer-Riesel primality test I have formulated the following two claims: First claim Let $P_m(x)=2^{-m}\...
3
votes
1answer
151 views

Almost-Primes in Short Intervals

Let $S$ be the set of integers which are a product of $k$ distinct primes, $k$ a fixed positive integer (the condition that the primes are distinct is not crucial). Landau used the Prime Number ...
2
votes
0answers
171 views

What is the sum of the binomial coefficients ${n\choose p}$ over prime numbers?

What is known about the asymptotics, lower and upper bound of the sum of the binomial coefficients $$ S_n = {n\choose 2} + {n\choose 3} + {n\choose 5} + \cdots + {n\choose p} $$ where the sum runs ...
1
vote
1answer
309 views

Primality test for generalized Fermat numbers

This question is successor of Primality test for specific class of generalized Fermat numbers . Can you provide a proof or a counterexample for the claim given below? Inspired by Lucas–Lehmer–Riesel ...
7
votes
1answer
258 views

Riemann sum formula for definite integral using prime numbers

I had asked this question in MSE. It got lot of upvotes but no answer (except one which was too long to be posted as a comment) hence I am posting it in MO. While answering another question in MSE I ...
0
votes
0answers
104 views

What is known about the lower bound for the integers $n$ for which $n$ minus the first $k$ odd primes are $k$ composite numbers?

Question edited in view of the comments below By Yamada's paper we can conclude that if $n>e^{e^{36}}$ be an even number then it can always be written as the sum of a prime and a semi-prime. My ...
0
votes
0answers
52 views

Distribution of witnesses that yields a factorization of $n$

For each natural odd number $n$, let $A_n$ be the set of all $1 < a < n$ for which $n$ is a pseudoprime to base $a$ but not a strong pseudoprime to base $a$. This is the set of bases for which ...
12
votes
1answer
341 views

Is the identity function a unique multiplicative homeomorphism of $\mathbb N$?

Endow the set $\mathbb N$ of positive integers with the topology $\tau$ generated by the base consisting of arithmetic progressions $a+b\mathbb N_0$ where $\mathbb N_0=\{0\}\cup\mathbb N$, where $a,b\...
6
votes
2answers
267 views

A simultaneous generalization of the Grunwald-Wang and Dirichlet Theorems on primes

By Grunwald-Wang Theorem, if for some odd number $n$ the equation $x^n=a$ has no solutions in $\mathbb Z$, then the equation $x^n=a\mod p$ has no solutions for some prime number $p$. I am interested ...
7
votes
2answers
728 views

A stronger form of the Dirichlet Theorem on prime numbers in arithmetic sequences

Question 1. Let $a,b>1$ be two natural numbers. Is there a prime number $p\in 1+b\mathbb N$ such that $a+p\mathbb Z$ is a generator of the multiplicative group of the field $\mathbb Z/p\mathbb Z$? ...
0
votes
0answers
122 views

Counting divisors of primes plus or minus 2

I was naively exploring the (usually) composites $\pm 2$ from a prime $p$, wondering if there might be some asymmetry, and made this histogram of the difference $\Delta$ in the number of divisors of $...
3
votes
1answer
228 views

Arithmetic properties of a sum related to the first Hardy-Littlewood conjecture

The starting point of this post is an earlier question, where I conjectured (and GH from MO confirmed) that the von Mangoldt function is the limit at $s=1$ of a certain Dirichlet series, $$\Lambda(m)=\...
3
votes
1answer
271 views

Primality test for specific class of $N=k \cdot b^n-1$

This question is successor of Compositeness test for specific class of $N=k \cdot b^n-1$ . Can you provide a proof or a counterexample to the following claim : Let $P_m(x)=2^{-m}\cdot \left(\left(...
1
vote
0answers
85 views

1-concatenable primes

If we choose some prime, say $11$, we can concatenate one digit to the left and one to the right to obtain another prime, for example, $2113$, we can do the same with $2113$ and obtain $121139$, a ...
11
votes
0answers
285 views

Prime numbers of the form $1+p+p^2+\dots+p^n$

I am looking at prime numbers of the form $Q=1+p+p^2+\dots+p^n$, where $p$ is also a prime number, $n$ is finite. Unfortunately I was unable to find any reference to such prime numbers in the ...
0
votes
0answers
82 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
126 views

The power of a prime in the prime factorization of a factorial [closed]

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
62 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?...
8
votes
1answer
855 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
246 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 ...
0
votes
0answers
120 views

An elementary size bound in number theory?

Given integer $a$ of size $R^\alpha$ with $\alpha\in(0,1)$ and $t$ large primes $R_i$ of roughly same size $R$ what is the smallest $T$ one needs so that there is an integer $0<K<R$ with as ...
4
votes
1answer
135 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
310 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
260 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 \...
7
votes
2answers
397 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
218 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
118 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 ...
8
votes
1answer
324 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
97 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
322 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
187 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
469 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
230 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} $...
4
votes
1answer
389 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
150 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
356 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
357 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
126 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
98 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)...