All Questions
Tagged with nt.number-theory prime-numbers
1,808 questions
3
votes
0
answers
1k
views
Formula for $\pi$ involving exponents of Mersenne primes
Can someone provide a proof for the following claim?
$$\pi=\dfrac{S_0S_2}{M_3M_5} \cdot\left(\displaystyle\prod_{p \equiv 1 \pmod{4} } \frac{p}{p-1}\right) \cdot \left(\displaystyle\prod_{p \equiv 3 \...
- 2,661
11
votes
0
answers
436
views
Can we rule out the possibility that $\sqrt[3]{2}$ is small modulo every prime?
Consider a prime $p$ such that the polynomial $X^3-2$ splits into linear factors over $\mathbb{F}_p$: $X^3-2 = (X-\alpha_p)(X-\beta_p)(X-\gamma_p)$. It seems reasonable to expect that (identifying $\...
- 1,914
2
votes
0
answers
191
views
The exponential sum over primes on average
In https://academic.oup.com/blms/article-abstract/20/2/121/266256?redirectedFrom=fulltext Vaughan shows the following bounds for the $L^1$-mean of the exponential sum over primes $$\sqrt x\ll \int _0^...
- 1,381
2
votes
0
answers
182
views
Integers as polynomials in infinite variables
This question is more of a request for reference or ideas than else. Forgive (or correct) if there are imprecisions or blatant mistakes.
The main idea is that the unique factorization theorem for $\...
- 29
11
votes
1
answer
637
views
Primes such that a given number has very small order
The following came up in (a previous version of) this answer.
Question. Let $a > 1$ be a positive integer, and $f \in \mathbf Z[x]$ a polynomial with positive leading term. Does there always exist ...
- 28.7k
3
votes
1
answer
188
views
Is there a uniform family of polynomials $f_p(x) =x^2 + a(p)x + b(p)$ such that $f_p(x)\in \mathbb{Z}[x]$ is irreducible and irreducible mod $p$?
Let $p\in\mathbb{Z}$ be a positive prime number.
Is there a "uniform" family of polynomials $f_p(x) =x^2 + a(p)x + b(p)$ of degree two such that $f_p(x)\in \mathbb{Z}[x]$ is both irreducible ...
- 237
4
votes
1
answer
266
views
Prime omega function values on a product of prime powers predecessors
Let $p_1, ... , p_n, ...$ be the prime numbers in order. Define
$$
P_n = \prod_{k=1}^n p_k^q
$$ It is known that $\omega(P_n) = n$ where $\omega(\cdot)$ is the little prime omega function. For a given,...
- 251
2
votes
0
answers
411
views
On two "versions" of abc conjecture
Let $a,b,c$ be coprime nonzero positive integers such that $a+b=c$. The ABC conjecture states that for any $\varepsilon>0$, we have $$c < C_{\varepsilon}\operatorname{rad}(abc)^{1+\varepsilon}.$$...
- 622
4
votes
1
answer
258
views
Density of numbers where a large prime factor satisfies a congruence
I am looking for an upper bound on the number of integers $n<x$ such that $n$ has a prime factor $p>\log(x)^{(1+\delta)}$ such that $p \equiv a \mod b$. Where $a,b$ are fixed and coprime and $0&...
0
votes
0
answers
75
views
Existence of smooth integers in every residue class with large modulus
Let us say that a positive integer $x$ is $y$-power smooth, if the largest prime power divisor of $x$ is at most $y$. In what follows, let $C$ be any real number larger than $1$ and, for an integer $x$...
- 1,663
1
vote
0
answers
195
views
Conjectural values of some determinants involving Legendre symbols (II)
Let $p$ be an odd prime, and let $(\frac{\cdot}p)$ denote the Legendre symbol. Motivated by the evaluation of the determinants
$$\det\left[\left(\frac{j+k}p\right)\right]_{1\le j,k\le(p-1)/2}\ \ \text{...
- 15.6k
2
votes
0
answers
156
views
Conjecture: $x^4+1$ is never Wieferich prime
Related to this question and Alexander Kalmynin's answer.
For natural $n$ define $J(n)=(2^{n-1}-1) \bmod n^2$
and if $n$ is power of two define $J(2^n)=1$ (this is artificial, just to
avoid triviality ...
- 25.4k
3
votes
1
answer
163
views
Increasing sequences and Wieferich primes
We are trying to show that primes of the form $a(n)$ can't be
Wieferich primes.
For natural $n$ define $J(n)=(2^{n-1}-1) \bmod n^2$
and if $n$ is power of two define $J(2^n)=1$ (this is artificial, ...
- 25.4k
3
votes
1
answer
401
views
Probability of finding a prime number between $x-\ln(x)$ and $x+\ln(x)$
Using my computer, I found that in the interval $[1, N]$ the probability of finding a prime number between $x-\ln(x)$ and $x+\ln(x)$ is greater than constant $c$ where $N=10^2, 10^3,...,10^{9}$, $x$ ...
- 1,776
6
votes
1
answer
393
views
Test for pair of odd primes $(p, 2p^2-1)$
Let $a(n)$ be A106483 (i.e., primes $p$ such that $2p^2-1$ is also prime).
Let $b(n)$ be an integer sequence such that $b(n) = B$ after the whole transformation where we start with $A = n$, $B = 1$, $...
- 4,938
4
votes
4
answers
913
views
Let $X$ be a positive integer. Then $\pi{(X+\ln^2{X})}-\pi{(X-\ln^2{X})}>\ln{X}$?
The prime-counting function is the function counting the number of prime numbers less than or equal to some real number $x$. It is denoted by $\pi{(x)}$. Using my computer I found that for any ...
- 1,776
4
votes
0
answers
238
views
Conjectural values of some determinants involving Legendre symbols (I)
$\newcommand\Legendre{\genfrac(){}{}}$Let $p$ be an odd prime, and let $\Legendre\cdot p$ be the Legendre symbol. In 2003, Robin Chapman evaluated the determinants
$$\det\left[\Legendre{i+j}p\right]_{...
- 15.6k
3
votes
0
answers
175
views
Proof of when 3 is a cubic residue modulo primes
I have recently been learning about cubic characters, and the machinery of Gauss and Jacobi sums used to prove the cubic reciprocity theorem, and using this, I can now determine when any prime is a ...
- 2,811
6
votes
0
answers
381
views
A possible variant of Zagier's one-sentence proof for Fermat's sum of two squares theorem?
Is it possible to modify Zagier's one-sentence proof of Fermat's sum of two squares theorem (see here) to prove certain non-trivial cases of Jacobi's four-square theorem (see here)?
Let $p$ be a prime ...
- 81
1
vote
0
answers
128
views
Effective Erdős–Kac theorem
I have some number $N$ and some integer $k>0$. I want to know what fraction of numbers up to $N$ have more than $k$ prime factors. (In my application, with repetition, but the $\omega$ version is ...
- 9,114
-1
votes
1
answer
147
views
Is it possible to have square-free order(s) in $\mathbb{Z}^\times_N$?
Suppose, $N=p\cdot q$ is the product of two safe primes $p=2p'+1$ and $q=2q'+1$ for some odd primes $p'$ and $q'$.
Let, $p_0,p_1,\ldots,p_m\ll p',q'$ be a few odd primes chosen uniformly at random ...
0
votes
1
answer
124
views
Could I possibly exploit distinct odd primes raised to 6 to solve Exact Three Cover, when reducing it in Subset Sum?
I'm solving Exact 3 Cover, given a list with no duplicates $S$ of $3m$ whole numbers and a collection $C$ of subsets of $S$, each containing exactly three elements. The goal is to decide if there are $...
- 101
0
votes
0
answers
98
views
Relation between elements with fixed exponent over different $\mathbb{Z}^\times_p$
A primitive root $h$ of $n$ is a generator of the cyclic modulo multiplicative group $\mathbb{Z}^\times_n$.
Suppose, $\mathbb{P}_{\langle 2\rangle,N}=\{p_i <N\mid \langle 2\rangle=\mathbb{Z}^\...
5
votes
1
answer
310
views
Is there a statement in Presburger arithmetic about primes this simple heuristic fails for?
I came up with the following conjecture while thinking about ways to formulate some heuristics about primes:
Conjecture: Given a statement $s$ in Presburger arithmetic, using an additional unary ...
- 3,319
5
votes
1
answer
750
views
Geometric mean of prime factors of all numbers up to n
Through numerical calculations I have discovered that for any natural number $n \geq 2$, the geometric mean of the prime factors of all natural numbers $\leq n$ can be approximated well by $1.6653 \...
- 1,228
12
votes
2
answers
1k
views
Prime differences and zero multiplicity
Concerning gaps between consecutive primes, Paul Erdős conjectured that:
$$\sum_{p_n < x} (p_n -p_{n-1})^2 = O(x \log x)$$
Let's call this hypothesis EH. Assuming the Riemann hypothesis (RH), ...
- 232
2
votes
0
answers
66
views
How to check that a number probably/likely has a divisor having a specific bit length/in range?
Given a randomly generated $\alpha\in\Bbb N$ where $\alpha$ is large thus hard to factor (no small prime composites). How to check that a divisor $F\in\Bbb N$ with a specific bitlengh $n\in\Bbb N∧n<...
- 87
2
votes
0
answers
121
views
How to know if a random natural number is a probable semiprime?
Let that $n\in\Bbb N$ generated from a hash function where $n$ is long enough to be hard to factor in the gnfs algorithm. How to check if $n$ is probably a semi‑prime in a faster way than factoring it ...
- 87
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
5
votes
2
answers
691
views
Representing natural numbers as sums of distinct prime powers
I am investigating whether every natural number $n > 18$ can be represented as a sum $p_1^{m_1} + \dots + p_k^{m_k}$, where $p_1, \dots, p_k$ are distinct primes, and $m_1, \dots, m_k$ are distinct ...
- 1,228
4
votes
0
answers
200
views
Effective bound for odd numbers expressed as sums of three primes
I am interested in the representation of odd numbers greater than five as sums of three primes, inspired by Harald Helfgott's seminal proof of the ternary Goldbach conjecture and the nuanced findings ...
2
votes
0
answers
147
views
Prime splitting in the division field of an elliptic curve
Let $E/\mathbb{Q}$ be an elliptic curve with good reduction at two distinct primes $p, \ell$. Suppose the mod $\ell$ Galois representation associated to $E$ is surjective. Let $K=\mathbb{Q}(E[\ell])$ ...
- 1,422
7
votes
1
answer
339
views
Rational prime factors in the components of powers of Gaussian primes
Let $\pi=a+bi\in \mathbb{Z}[i]$ be a Gaussian prime with $a$ and $b$ nonzero, and $b$ even. For odd rational primes $p=\pi\bar\pi$ and $q\neq p$, define $\pi^{\frac{1}{2}\left(q-\left(\frac{-1}{q}\...
0
votes
0
answers
58
views
Existence of minimal bases in additive combinatorics
Let $\mathbb{N}$ denote the set of natural numbers, including zero. A subset $X \subseteq N$ is a basis if $X + X = \mathbb{N}$. Clearly, if $X$ is a basis and $X \subseteq Y$, then $Y$ is also a ...
4
votes
0
answers
446
views
There are infinitely many prime which have arbitrary large gap in their digits in particular base expansion
Consider $m$ and $r$ is any fixed positive integer and $t$ is a variable $(t=0,1,2,3,...)$. Below, $[a]$ denotes the greatest integer function of $a$ (or floor function).
Claim 1 : There exists a ...
- 599
2
votes
0
answers
124
views
On the elliptic curve $X^3+6d^2X-7d^3 = Y^2$ and the ellipse $p^2+3q^2-d = 0$?
From the ellipse $p^2+3q^2 - d = 0$ we can find a solution to the equation,
$$a^3+b^3+c^3 = (c+m)^3$$
if we solve the elliptic curve,
$$E:=X^3+6d^2X-7d^3 = Y^2$$
More details can be found in this MSE ...
- 12.6k
2
votes
2
answers
197
views
On the primality of $j(n)=\varphi(p_n+1-n)+1$ when $j(n) \equiv 19 \pmod {100}$
Related to Power of primes.
Let $p_n$ denote n-th prime and $\varphi$ the totient function.
For natural $n$, define $j(n)=\varphi(p_n+1-n)+1$.
For $n$ up to $10^9$ if $j(n) \equiv 19 \pmod {100}$
then ...
- 25.4k
1
vote
2
answers
383
views
Is there any way to estimate this functions: $f(n)=\sum_{d|n}d\varphi(d)$ and $g(n)=\sum_{d|n}\frac{\varphi(d)}{d}$?
Let that $n$ be a natural number and $\varphi(n)$ be the Euler totient function. Is there any formula or estimation for computing functions $f,g$ such that:
$$
f(n)=\sum_{d\mid n}d\varphi(d)
$$
and
$$
...
- 139
0
votes
0
answers
122
views
Convergence of a series related to counting distinct prime factors
I am here to ask whether the following series is convergent for all real $z$. I am also asking whether this is everywhere real analytic. I conjecture that it is convergent for all real input, or at ...
1
vote
1
answer
325
views
Goldbach conjecture reformulation [closed]
As thought, the question below is a reformulation of the goldbach conjecture.
$ S = \{K - ap \mid a \geq 3, p \text{ is prime} < K/2 \} $, where $ a $ is an odd integer greater than or equal to 3, ...
- 23
12
votes
1
answer
2k
views
Power of primes
$n$ is a natural number $>1$, $\varphi(n)$ denotes the Euler's totient function, $P_n$ is the $n^\text{th}$ prime number and $\sigma(n)$ is the sum of the divisors of $n$. Consider the expression:
$...
- 45
2
votes
1
answer
379
views
Representation of 2 in sum of powers of positive-negative digits with some base
Define:A set $\mathcal{C}(t)$, a positive integer $n$ is in the $\mathcal{C}(t)$ if $x^t \pmod{n}$ describes a bijection from the set $\{0,1,...,n-1\}$ to itself.
Example table:
\begin{array}{|c|c|}
\...
- 599
7
votes
0
answers
271
views
A question about prime numbers, totient function $ \phi(n) $ and sum of divisors function $ \sigma(n) $
This question was previously posted to MSE here.
I noticed something with the totient function $ \phi(n) $ and sum of divisors function $ \sigma(n) $ when $n > 1$.
It seems than :
$ \sigma(4n^2-1) \...
- 71
4
votes
0
answers
536
views
Is the integer factorization into prime numbers normally distributed?
Edit:
Sorry, for the inconvenience: I have edited the question, since there was a misconception in my thinking.
Let $P_1(n) := 1$ if $n=1$ and $\max_{q\mid n, \text{ } q\text{ prime}} q$ otherwise, ...
- 3,064
5
votes
0
answers
131
views
Taking integer values of a sequence of Beurling primes
Let $P=(p_j)_{j=1}^\infty$ be an increasing sequence of real numbers with $1<p_1$ and $\lim_{j\to\infty}p_j=\infty$. As mentioned in [1], Beurling proved that if the multiplicative group $N_P$ ...
- 51
5
votes
2
answers
652
views
On the number of distinct prime factors of $p^2+p+1$
Is it true that, for each positive integer $c$, there exists a prime number $p$ such that $p^2+p+1$ is divisible by at least $c$ distinct primes?
- 934
8
votes
1
answer
657
views
Arithmetic sequences and Artin's conjecture
(Sorry if this is a naive question; it is not my area!)
Consider the following strengthening of Artin's conjecture on primitive roots (and Dirichlet's theorem) for the case of $n=2$: every arithmetic ...
0
votes
1
answer
292
views
Factorization trees and (continued) fractions?
This question is inspired by trying to understand the lexicographic sorting of the natural numbers in the fractal at this question:
Is $1 = \sum_{n=1}^{\infty} \frac{\pi(p_n^2)-n+2}{p_n^3-p_n}$ , ...
- 3,064
1
vote
0
answers
72
views
Is there an upper bound on the number of partitions of a finite set of primes into 3 sets the products of 2 of which sum to the product of the third?
Is there an upper bound on the number of partitions of a finite set $S$
of prime numbers into 3 sets $A$, $B$ and $C$ for which the following holds?:
$$
\prod_{p \in A} p \ + \ \prod_{p \in B} p \ = ...
- 19.6k
5
votes
1
answer
737
views
Smallest prime factor of numbers
The literature refers to smooth integers as \begin{equation}\Psi(x,y):=\#\{n\le x:P_1(n)\le y\},\end{equation} where $P_1(n)$ is the largest prime factor of $n$. There are lots of results studying $\...
user344548