All Questions
Tagged with nt.number-theory prime-numbers
316 questions
28
votes
2
answers
5k
views
Is Furstenberg's topology useful?
It's hard not to be amused and perhaps even amazed when first encountering Furstenberg's clever "topological" proof that there are infinitely many primes. Closer inspection, however, reveals ...
26
votes
5
answers
11k
views
Fastest algorithm to compute the sum of primes?
Can anyone help me with references to the current fastest algorithms for counting the exact sum of primes less than some number n? I'm specifically curious about the best case running times, of ...
- 627
25
votes
2
answers
1k
views
Integral polynomials dividing N!
Consider a polynomial $P(X)\in\mathbb Z[X]$. Is it true that $P(N)$ divides $N!$ for infinitely many integer $N$?
This question is motivated by the special case where $P(X) = X^2 + 1$ that appeared ...
- 485
25
votes
7
answers
3k
views
Question on consecutive integers with similar prime factorizations
Suppose that $n=\prod_{i=1}^{k} p_i^{e_i}$ and $m=\prod_{i=1}^{l} q_i^{f_i}$ are prime factorizations of two positive integers $n$ and $m$, with the primes permuted so that $e_1 \le e_2 \cdots \le e_k$...
- 15.4k
23
votes
1
answer
3k
views
Does the average primeness of natural numbers tend to zero?
This question was posted in MSE. It got many upvotes but no answer hence posting it in MO.
A number is either prime or composite, hence primality is a binary concept. Instead I wanted to put a value ...
- 5,470
22
votes
1
answer
2k
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 $(\...
- 1,730
22
votes
1
answer
2k
views
Reasons behind assuming the existence of Siegel zeros can be used to prove something stronger than assuming GRH?
There are few results that I am aware of where one can prove something stronger by assuming the existence of Siegel zeros than by assuming the GRH. For example Heath-Brown proved the existence of ...
- 3,625
22
votes
1
answer
852
views
How big can a set of integers be if all pairs have small gcd?
Suppose $A\subset[1,N]$ is a set of integers. If for any distinct $a,b\in A$ we have $(a,b)\leq M$ then how big can $|A|$ be?
If $M=1$ then $|A|$ is at most $\pi(N)$ since the map $a\mapsto P_+(a)$ (...
- 671
22
votes
1
answer
2k
views
Primes represented by two-variable quadratic polynomials
I'm looking over a paper, "Primes represented by quadratic polynomials in two variables" [1] which attempts to characterize the density of the primes in two-variable quadratic polynomials. ...
- 9,114
21
votes
1
answer
1k
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.
...
- 24.7k
21
votes
1
answer
1k
views
Primes that are sums of two squares with constraints on the squares
It is well known that there are infinitely many primes of the form $a^2+b^2$ (namely all primes congruent to $1$ modulo $4$). On the other hand, Euler raised the problem as to whether there are ...
- 213
21
votes
4
answers
2k
views
Prime factorization "demoted" leads to function whose fixed points are primes
Let $n$ be a natural number whose prime factorization is
$$n=\prod_{i=1}^{k}p_i^{\alpha_i} \; .$$
Define a function $g(n)$ as follows
$$g(n)=\sum_{i=1}^{k}p_i {\alpha_i} \;,$$
i.e., exponentiation is "...
- 151k
20
votes
1
answer
1k
views
Possible contemporary improvement to bounded gaps between primes?
In his summary of his book Bounded gaps between primes: the epic breakthroughs of the early 21st century, Kevin Broughan writes
Which brings me to my final remark: where to next in the bounded gaps ...
- 35.5k
20
votes
2
answers
4k
views
information-theoretic derivation of the prime number theorem
Motivation:
While going through a couple interesting papers on the Physics of the Riemann Hypothesis [1] and the Minimum Description Length Principle [2], a derivation(not a proof) of the Prime Number ...
- 3,871
20
votes
3
answers
2k
views
Refinements of the Riemann hypothesis
I have often read that the Riemann hypothesis is somewhat a statement like:
The primes are as regularly distributed as we can hope for.
For example $\pi(x) = Li(x)+ O(x^{\sigma+\epsilon})$ for ...
- 2,810
20
votes
3
answers
3k
views
What is the simplest proof that the density of coprime pairs does not go to zero?
By density of coprime pairs, I mean the proportion of pairs integers between $1$ and $x$ which are coprime.
This is known to be asymptotically $1/\zeta(2)$.
I want something much weaker, namely that ...
- 19k
19
votes
0
answers
540
views
Why $\gcd \{ {\rm ord}_p(q)\colon q\mid p-1 \}$ likes to be large?
For a prime $p$, let $F_p$ denote the greatest common divisor of the orders modulo $p$ of all prime divisors of $p-1$:
$$ F_p = \gcd \{ {\rm ord}_p(q)\colon q\mid p-1 \}; $$
thus, for instance, $F_3=...
- 23k
19
votes
2
answers
2k
views
Is there an explicit expression for Chebyshev polynomials modulo $x^r-1$?
This is an immediate successor of Chebyshev polynomials of the first kind and primality testing and does not have any other motivation - although original motivation seems to be huge since a positive ...
- 18.4k
19
votes
1
answer
2k
views
How many primes can there be in a short interval?
Given $n \in \mathbb{N}$, let $\pi(n)$ denote the number of prime numbers $\leq n$.
What is
$$
\limsup_{m \rightarrow \infty} \left( \limsup_{n \rightarrow \infty} \frac{\pi(n+m) - \pi(n)}{\pi(m)} \...
- 19.6k
19
votes
1
answer
3k
views
Sums of primes that are themselves prime
I'm not a math expert so this may be a trivial question; if $p_i$ is the $i$-th prime, let:
$$S(n) = \sum_{i=1}^n p_i$$
be the sum of the first $n$ primes and
$$P(n) = | \{1 \leq i \leq n \mid S(...
- 1,602
19
votes
1
answer
3k
views
A mysterious connection between primes and squares
Motivated by two previous questions of mine (cf. Primes arising from permutations and Primes arising from permutations (II)), here I ask a curious question which connects primes with squares.
...
- 15.6k
19
votes
3
answers
2k
views
On Euclid's proof of the infinitude of primes and generating primes
So looking at Euclid's proof he says
1)take a finite family of primes (F)
2)multiply all the primes and add one
3)this new number has at least 1 new prime factor
So I was wondering about what kind ...
- 809
18
votes
3
answers
5k
views
What is known about primes of the form $x^2-2y^2$?
David Cox's book Primes of The Form: $x^2+ny^2$ does a great job proving and motivating a lot of results for $n>0$. I was unable to find anything for negative numbers, let alone the case I am ...
18
votes
3
answers
6k
views
The multiplicative order of 2 modulo primes
Artin's Conjecture says that any positive integer, which is not a square, is a primitive root modulo infinitely many primes. Christopher Hooley gave in
Hooley, Christopher (1967). "On Artin's ...
- 25.5k
18
votes
1
answer
677
views
Could computing the next prime in a finite Euler product be made rigorous?
It is well known that:
$$\zeta(s):=\prod_{n=1}^{\infty} \frac{1}{1-p_n^{-s}} \qquad \Re(s) \gt 1$$
with $p_n =$ the $n$-th prime. It also known that:
$$\zeta(2n):= \frac{(-1)^{n+1} B_{2n}(2\pi)^{2n}}{...
- 4,169
18
votes
3
answers
2k
views
A binomial sum is divisible by p^2
This is a question I have since longer time, but I have absolutely no idea how to proceed on it.
Let $p>3$ be a prime. Prove that $\displaystyle\sum\limits_{k=1}^{p-1}\frac{1}{k}\binom{2k}{k}\...
- 33.8k
17
votes
0
answers
891
views
An elementary proof that, for every fixed $n \in \mathbf N^+$, there are infinitely many primes $\equiv -1 \bmod n$
This morning, I made a comment to a comment to a question of Ayman Moussa, only to point out that, among many others, there is an elementary proof of Dirichlet's theorem on the existence of infinitely ...
- 10.5k
17
votes
2
answers
3k
views
Does the equation $241+2^{2s+1}=m^2$ have a solution?
Let $p$ be a prime congruent to $1$ mod. 8.
If $p= 17$ one has : $p+ 8 = 5 ^2$.
If $p= 41$ one has : $p+ 8 = 7 ^2$.
If $p= 73$ one has : $p+ 8 = 9 ^2$.
If $p= 89$ one has : $p+ 32 = 11 ^2$.
If $...
- 1,980
17
votes
2
answers
2k
views
Polynomials for natural numbers and irreducible polynomials for prime numbers?
Let $p$ be a prime and $n$ be a natural number.
Define inductively for prime numbers: $f_1(x) := 1$, $f_2(x):=x$, $f_p(x) := 1+\prod_{q\mid p-1} f_q(x)^{v_q(p-1)}$.
Is $f_p(x)$ always irreducible for ...
- 3,064
15
votes
0
answers
487
views
Word complexity of primes mod 4
For an infinite binary word $w$, the word complexity $f_w(n)$ is defined as the number of different subwords of length $n$. The asymptotic behavior of this function is an important parameter of the ...
- 17k
15
votes
3
answers
1k
views
Does there exist a meromorphic function all of whose Taylor coefficients are prime?
More precisely, does there exist an unbounded sequence $a_0, a_1, ... \in \mathbb{N}$ of primes such that the function
$\displaystyle O(z) = \sum_{n \ge 0} a_n z^n$
is meromorphic on $\mathbb{C}$?
...
- 118k
15
votes
2
answers
2k
views
Question on the 52nd (known) Mersenne prime number
In a footnote to the list of known Mersenne prime numbers which can be found here, we read that the "ranking" therein is a provisional one since not all possible exponents between $57 \, 885 ...
- 8,842
15
votes
1
answer
4k
views
The Green-Tao theorem and positive binary quadratic forms
Some time ago I asked a question on consecutive numbers represented integrally by an integral positive binary quadratic form. It has occurred to me that, instead, the Green-Tao theorem may include a ...
- 25.7k
15
votes
1
answer
2k
views
Are there any Fibonacci numbers that are sandwiched between twin primes?
Note: These queries had come up during an earlier discussion: On Fibonacci numbers that are also highly composite. Am putting them up as a separate post.
Q: Are there any Fibonacci numbers that are ...
- 5,979
14
votes
1
answer
1k
views
Normal numbers, Liouville function, and the Riemann Hypothesis
This is a question about whether or not some number $\lambda^*$ is normal in base 2. More specifically, I am wondering if $\lambda^*$ is not normal. Proving it is normal would be next to impossible, ...
- 3,098
14
votes
6
answers
2k
views
Density of numbers having large prime divisors (formalizing heuristic probability argument)
I want to prove that the set of natural numbers n having a prime divisor greater than $\sqrt{n}$ is positive.
I have a heuristic argument that this density should be $\log 2$, which is approximately ...
- 7,320
14
votes
1
answer
1k
views
Hamming distance to primes
There is a positive density of odd numbers which are of the form $2^n+p$ (due to Romanoff), and a positive density which are not of this form (due to van der Corput and Erdos, see this paper for a ...
- 286
14
votes
1
answer
1k
views
Nonstandard proofs of the fundamental theorem of arithmetic
Thirty or so years ago, someone showed me a clever proof of the Fundamental Theorem of Arithmetic that did not make use of the lemma "If $p\mid ab$ then $p\mid a$ or $p\mid b$". I'm unable ...
- 19.7k
13
votes
1
answer
591
views
Is ${\rm lcm}\{{\rm ord}_p(q)\colon q\mid p-1,\ q>2\}>\sqrt p\ \,$?
The following question is "ideologically related" to the one I have recently asked.
For a prime $p$, let $M_p$ denote the least common multiple of the orders modulo $p$ of all odd prime divisors of $...
- 23k
13
votes
6
answers
4k
views
Applications and Natural Occurrences of Prime Numbers
I'm fascinated by prime numbers, and over the years, I've found multiple applications and natural occurrences for them. But can anyone suggest some alternatives that aren't in my list?
Applications ...
13
votes
2
answers
1k
views
Existence of relative Dirichlet density of primes starting with 1
This question is a duplicate of an existing MO question, but that other MO question has an accepted answer that does not actually answer the question, and I'm not sure how to fix that other than by re-...
- 82.7k
13
votes
4
answers
2k
views
Proving Mertens' theorem using the prime number theorem
Mertens' Theorem states that
$$\sum_{p \leq x}\frac{1}{p} = \log \log x + M + O(1/\log x).$$
This is weaker than the prime number theorem; in fact according to the Wikipedia page, the prime number ...
- 21.3k
13
votes
4
answers
3k
views
Computing the Mertens function
I wonder if anybody can help me with this problem.
I'm trying to compute the Mertens function for large $n$. The most obvious algorithm is just to compute all primes up to $\sqrt{n}$ and then to ...
- 133
13
votes
1
answer
919
views
Is there a "deep" reason that the first Perrin pseudoprime is large?
Let $f(x) \in \mathbb{Z}[x]$ be a monic irreducible polynomial with roots $\alpha_1, ... \alpha_k$, and let $\Delta$ be the discriminant of $f$. For any prime $p \nmid \Delta$, the Frobenius morphism ...
- 118k
13
votes
3
answers
1k
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? ...
- 1,049
13
votes
7
answers
4k
views
Are there any interesting or lesser known proofs related to Bertrand's Postulate
There are 3 standard proofs of Bertrand's Postulate:
(1) Chebyshev's original proof
(2) Ramanujan's simplification of Chebyshev's proof
(3) Erdos's proof
I recently learned about the very ...
- 1,049
11
votes
2
answers
1k
views
Chebyshev's approach to the distribution of primes
This is motivated by a recent question by Wadim.
The negative answer should be known, since t is very natural, in this case I would be happy to see any reference.
May Pafnuty Lvovich Chebyshev's ...
- 109k
11
votes
0
answers
1k
views
Are the twin primes the only positive double zeros of this real function?
Agno's answer
was extremely helpful.
For $x \in \mathbb{R}, x \ge 1$ define
$$ f(x) = \sin\frac{\pi(\Gamma(x)+1)}{\lfloor x \rfloor}$$
By Wilson's theorem the positive integer zeros of $f(x)$ are ...
- 25.4k
11
votes
2
answers
615
views
Jacobi symbols for two-square sums of primes
Given a prime $p\equiv 1\pmod 4$, Fermat's two-squares theorem discovered by Girard
states that there exists two integers $A,B$ such that
$p=A^2+B^2$.
For all primes up to $10^7$ the integers $A$ and $...
- 17.9k
11
votes
1
answer
436
views
How many numbers $\le x$ can be factorized into three numbers which form the sides of a triangle?
Note: Posting in MO since it was unanswered in MSE
Definition: We say that a natural number $n$ has triangular divisors if it has at least one triplet of divisors $n = d_1d_2d_3, 1 \le d_1 \le d_2 \...
- 5,470