All Questions
Tagged with nt.number-theory prime-numbers
1,808 questions
6
votes
4
answers
887
views
Mathematical induction vis-à-vis primes
One of the most used proof-techniques is mathematical induction, and one of the oldest subjects is the study of prime numbers. Thanks to Euclid, we can consider the primes as a infinite monotone ...
- 12.9k
6
votes
1
answer
2k
views
Difficulty with "A new elementary proof of the Prime Number Theorem" by Richter
I'm studying Richter's "A new elementary proof of the Prime Number Theorem" paper, and I'm finding some problems understanding some parts of it. For example, I don't see how to get, in Lemma ...
- 2,060
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 ...
- 1,343
2
votes
0
answers
57
views
Wieferich primes and identities for the Euler quotients of $2^n+1$ and $\frac{2^n+1}{3}$
Let $n>1$ be odd integer.
Define the Euler quotient $a(n)=\frac{2^{\varphi(n)}-1 \bmod n^2}{n}$.
Number $n$ with $a(n)=0$ is Wieferich number and if it is prime
it is Wieferich prime.
It is open ...
- 25.4k
1
vote
0
answers
100
views
Curious congruences modulo $4$ involving primes
We define
$$S(n)=\sum_{a=2+(n\pmod 2)}^{n-2}
\sharp(\{j,1\leq j<n \pmod{a},(a,j)=1\})\ .$$
(Searching the OEIS yielded no results.)
For $n>2$ we have the following experimental observations (...
- 17.9k
2
votes
0
answers
110
views
+50
How to apply Pohlig Hellman using a very limited set of auxiliary inputs in that case?
So I was reading about Talotti, Paier, and Miculan - ECC’s Achilles’ Heel: Unveiling Weak Keys in Standardized Curves. The underlying idea is to lift the discrete logarithm problem to $\mathrm{prime}−...
- 87
-3
votes
0
answers
70
views
Is the upper bound on $H_{1}$ a decreasing function of the proportion of critical zeros of Zeta?
This question stems from https://arxiv.org/abs/2411.19762 and the numerical observation that the best unconditional upper bound for $H_{1}:=\lim\inf_{n\to\infty}p_{n+1}-p_{n}$, namely $H_{1}^{\flat}=...
- 6,984
15
votes
4
answers
2k
views
Square roots and prime numbers
Definitions:
Here I present a novel conjecture using basic mathematical tools like the sum of the
divisors of an integer $n$ called $\sigma(n)$, the sum of the squares of the positive divisors of n ...
- 127
1
vote
0
answers
116
views
Can all congruences for a third-order recurrence relation hold for some composite $n$?
Let $p$ be a prime with $p \gt 3$. Consider the polynomial $f = x^3 - 3x -1$. Suppose $f$ is irreducible over $\mathbb{F}_{p}$. Let $E$ be the splitting field of $f$ over $\mathbb{F}_{p}$, and let $\...
82
votes
3
answers
20k
views
Czelakowski's claimed proof of the Twin Prime Conjecture
It seems like the article "The Twin Primes Conjecture is True in the Standard Model of Peano Arithmetic: Applications of Rasiowa–Sikorski Lemma in Arithmetic (I)" by Janusz Czelakowski ...
- 105k
1
vote
0
answers
77
views
Conjecture about Euler quotients related to non-Wieferich numbers $W(n)=\frac{2^n+1}{3}$
For odd natural $n$ define the Euler quotient:
$$ a(n)=\frac{(2^{\phi(n)}-1) \bmod n^2}{n}=\frac{2^{\phi(n)}-1}{n} \bmod n$$
$a(n)=0$ is $n$ being Wieferich number (not necessarily prime).
For odd $n$,...
- 25.4k
3
votes
1
answer
596
views
Primes which are safe and Sophie Germain
If $p$ is a Sophie Germain prime then $2p+1$ is safe prime.
If $2p+1$ is safe prime then $p$ is Sophie Germain prime.
What is their conjectured distribution of primes $p$ which are both Sophie ...
- 4,985
0
votes
0
answers
78
views
Factoring totient of a prime
Is it any easy to factor $p-1$ when $p$ is a prime compared to general factorization problem?
What about when $2p+1$ is also a prime?
- 13.9k
3
votes
0
answers
192
views
What smoothing to use for PNT-like results?
Consider a Dirichlet series $\sum_n a_n n^{-s}$ with desirable analytic properties (e.g., analytic extension to $\Re s>0$); one example would be $a_n=\mu(n)$. Say we want to estimate $\sum_{n\leq x}...
- 20.2k
3
votes
1
answer
157
views
Three congruences for a Perrin-like sequence and pseudoprimes
Let $ V(n) $ be defined by the recurrence relation:
$$
V(n) = 3\,V(n-2) + V(n-3)
$$
with the initial conditions:
$$
V(0) = 3, \quad V(1) = 0, \quad \text{and} \quad V(2) = 6.
$$
If $ n $ is an odd ...
- 386
10
votes
1
answer
2k
views
What keeps asymptotic Goldbach's conjecture out of reach of current technology?
Despite the rather recent progress in prime number theory (see the proof of the ternary Goldbach conjecture by H.A. Helfgott, and the striking result of Yitang Zhang improved by Tao, Maynard and ...
CommunityBot
- 1
1
vote
1
answer
171
views
Are all integers up to $x$ but possibly $O_{\varepsilon}(x^{\varepsilon})$ the sum of $a$ squares and $b$ primes with $a+b\leq 3$?
This question is related to https://math.stackexchange.com/questions/3710032/conjecture-all-but-21-non-square-integers-are-the-sum-of-a-square-and-a-prime.
We know since Lagrange that every natural ...
- 1,028
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 ...
- 16.6k
31
votes
4
answers
2k
views
A Collatz-like function that bifurcates on primes
This is likely piling one mystery on another, but ...
I was exploring a function $f(n): \mathbb{N} \mapsto \mathbb{N}$ defined as follows:
$$
f(n) =
\begin{cases}
n^2 & \text{if} \;n \;\text{is ...
- 4,713
10
votes
2
answers
2k
views
Linear equations in primes
Quoting from Green-Tao, "Linear equations in primes" (especially Cor. 1.9 in https://arxiv.org/pdf/math/0606088.pdf), any system of linear forms of finite complexity and without any local obstructions ...
- 2,959
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 ...
- 12.9k
1
vote
1
answer
199
views
Weights in the proof of Chen's theorem in Nathanson's "Additive Number Theory The Classical Bases"
I was reading Professor Nathanson's graduate texts in mathematics 164: "Additive Number Theory The Classical Bases" (http://www.alefenu.com/libri/nathansonbases.pdf), and I was wondering if ...
- 13
2
votes
1
answer
221
views
A question on signed Stirling numbers of the first kind
Let $(x)_0=1$ and $(x)_n=x(x-1)\cdots(x-n+1)$ for $n=1,2,3,\ldots$. The signed Stirling numbers of the first kind, $s(n,k)$ with $n\ge k\ge0$, are defined by
$$(x)_n=\sum_{k=0}^ns(n,k)x^k.$$
Question. ...
- 7,226
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
0
votes
0
answers
241
views
Conjecture about some recurrent primes
I want to know if there are conjectures similar to this one, I know there is the Bell primes conjecture or Gardner conjecture (mentioned in this page https://en.wikipedia.org/wiki/Bell_number), but ...
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 ...
- 12.9k
1
vote
1
answer
374
views
$\{ x/p\} $ on average
This is a vague question: Lemma 2.2 of Friedlander and Lagarias' "On the distribution in short intervals of integers having no large prime factor" says that $$\sum _{p\leq w}\left (\{ x/p\} -...
- 14.6k
1
vote
0
answers
89
views
Test for odd prime triples in a $2p-1$ progression
Let $a(n)$ be A057326 (i.e., first member of a prime triple in a $2p-1$ progression).
Let $b(n) = B$ after $n-1$ iterations where we start with $A=n, B=1$ and for $i$ from $1$ to $n-1$ simultaneously ...
- 4,938
93
votes
3
answers
6k
views
A little number theoretic game
I came up with this little two player game:
The players take turns naming a positive integer. When one player says the number $n$, the other player can only reply in two different ways: They can ...
- 161
4
votes
0
answers
266
views
How dense are quotients of smooth numbers?
As usual, call a positive integer $y$-smooth if it has no prime factors greater than $y$. Write $S(x,y)$ for the set of $y$-smooth integers $\leq x$. Write $R(x,y)$ for the set of quotients $\{a/b: a,...
- 20.2k
0
votes
0
answers
374
views
Is the Conjecture of Representing Integers as Differences of Semiprimes and Primes Extendable to Products of Distinct Primes?
Conjecture:
Let $k$ and $l$ be fixed distinct positive integers ($k≠l$). Then, for every positive integer $n$, there exist prime numbers $p_1,p_2,…,p_k∈\mathbb{P}$ and $q_1,q_2,…,q_l∈\mathbb{P}$ such ...
- 17
1
vote
0
answers
127
views
Some property of the greatest prime factor
Let $n$ be a positive integer $\geq 2$ et denote by $ P^{+}(n)$ the greatest prime factor of $n$ my question is as follows:
If $a$ and $b$ are two numbers, is there any method to express or to bound $...
- 10.4k
1
vote
0
answers
170
views
Character sums over prime
Let $\chi$ be a quadratic character mod $q$. I am interested in finding the best result for how large $N$ should be such that it is guaranteed that
$$\sum_{p=1}^{N} \chi(p) \log p= o(N).$$
I am aware ...
- 3,065
9
votes
0
answers
324
views
Semi-primes represented by quadratic polynomials
According to Lemke-Oliver, irreducible quadratic polynomials $G$ with positive leading coefficient and $\rho(2)<2$, (where $\rho(m)$ denotes the number of incongruent solutions to the congruence $G(...
CommunityBot
- 1
1
vote
1
answer
729
views
Could the complex zeros of Riemann zeta function be of the form $ s=0.5+ik$ with $k$ a positive integer? [closed]
I have checked in Andrew Odlyzko, Tables of zeros of the Riemann zeta function, to know if there is an example of zeros of Riemann zeta function with integer imaginary parts, but I don't see that. I ...
- 13
-3
votes
1
answer
201
views
Formula for gaps between primes [closed]
The twin prime conjecture refers to:
$$
\liminf_{n\to \infty}\; p_{n+1} - p_{n} = 2.
$$
By reasoning I arrive at the following simple formula for gaps between primes:
\begin{align}
p_{...
- 26.9k
0
votes
0
answers
169
views
On a property of prime numbers
Let $p_i$ be the $i^{\rm th}$ prime number (i.e. $p_1=2,\ p_2=3,\ p_3=5,\cdots$)
What is the function of number of combinations of $c_1,\cdots,c_n$ in terms of $n$ such that,
$$\sum_{i=1}^{n}c_ip_i\ =\...
- 4,746
4
votes
1
answer
240
views
Do there exist prime numbers of the form $n \cdot 2^n + 1$, when $n \in \mathbb{N}$ and $n > 1$?
Recently, I was studying prime sequences of the form $k \cdot 2^n + 1$, and I noticed that primes of the form $n \cdot 2^n + 1$ almost do not exist, except for the $n = 1$ case.
Are there other prime ...
- 16.2k
0
votes
0
answers
102
views
Formalizing the "pseudorandomness" of primes
Many conjectures about primes seem to revolve around the idea of "primes are random". So I thought about how this "randomness" may be formally defined, and came up with the ...
- 1
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 \...
CommunityBot
- 1
2
votes
0
answers
76
views
upper and lower bounds on rowlands sequence
rowlands sequence is defined as follows
\begin{equation}
a_{n}=a_{n-1} + b_{n}
\end{equation}
where $b_{n} = gcd(a_{n-1}, n)$ for $n>h$
it originates from E. Rowlands 2008 paper "A Natural ...
9
votes
3
answers
9k
views
Algorithm for detecting prime powers
While reading Peter Shor's paper Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, I came across the following quote:
"This scheme will thus work as ...
- 1
3
votes
1
answer
216
views
Are there any positive integers $n$, $k$ such that $n > 2, k > 6$, and all prime factors of $n^k - 1$ are less than $n$?
I noticed that the prime factorization of $68^6 - 1$ is $3^2 \cdot 7^2 \cdot 13 \cdot 19^2 \cdot 23 \cdot 31 \cdot 67$, which makes all of its prime factors less than 68. This made me wonder the ...
- 105k
1
vote
0
answers
118
views
A primality criterion for specific class of $N=4kp^n+1$
Can you provide a proof for the following claim:
Let $P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4})^m+(x+\sqrt{x^2-4}\right)^m\right)$ .
Let $N= 4kp^n+1 $ such that $p$ is a prime number greater ...
- 2,661
4
votes
1
answer
409
views
On the parity of the sum $\sum_{1\le j<k\le p-1\atop p\nmid aj^2+bjk+ck^2}(aj^2+bjk+ck^2)$
QUESTION. Let $p$ be an odd prime and let $a,b,c\in\mathbb Z$. How to determine the parity of the sum
$$S_p(a,b,c)=\sum_{1\le j<k\le p-1\atop p\nmid aj^2+bjk+ck^2}(aj^2+bjk+ck^2)$$
in terms of $a,b,...
- 884
5
votes
0
answers
261
views
Primes generated by cyclotomic polynomials
Let $p$ be an odd prime, and let $f=\Phi_p$ be the $p$-th cyclotomic polynomial. Denote by $S_p$ the set of primes $q$ such that there exists a sequence of primes $p_1,\dots, p_g$ such that $p_1=f(1)=...
CommunityBot
- 1
29
votes
7
answers
7k
views
Asymptotic density of k-almost primes
Let $\pi_k(x)=|\{n\le x:n=p_1p_2\cdots p_k\}|$ be the counting function for the k-almost primes, generalizing $\pi(x)=\pi_1(x)$. A result of Landau is
$$\pi_k(x)\sim\frac{x(\log\log x)^{k-1}}{(k-1)!\...
- 14.6k
1
vote
0
answers
60
views
On the parity of $(2^{\varphi(n)}-1) \bmod{n^2}$
For odd integer $n$ define the function
$$ J(n)=(2^{\varphi(n)}-1) \bmod{n^2}$$
$J(n)$ is integer in $[0,n^2-1]$ and it is divisible by $n$.
Integer $n$ is Wieferich number
iff $J(n)=0$ and if $n$ is ...
- 25.4k
7
votes
1
answer
276
views
From $\Lambda_k$ and $\Lambda$ to $\mu$ (or $\lambda$)
Let $\{a_n\}_{n=1}^\infty$, $a_n \in \mathbb{C}$, $|a_n|\leq 1$. Let $\Lambda_k = \mu \ast \log^k$; in particular, $\Lambda_1$ equals the von Mangoldt function $\Lambda$. Suppose that we have ...
- 20.2k
5
votes
1
answer
172
views
On vanishing of $p$-adic logarithms
Might be related to Wieferich primes.
Let $p$ be odd prime and define the Fermat quotient
$$F(n)=\frac{(2^{n-1} -1)}{n} \mod n=\frac{(2^{n-1} \bmod n^2 )-1}{n}$$
For integer $b$ let $L_p(b)$ be the $p$...
- 9,061