All Questions
Tagged with nt.number-theory prime-numbers
519 questions with no upvoted or accepted answers
2
votes
0
answers
99
views
A problem in modular roots
We have three mutually coprime integers $r,t,M$ where $M\asymp K^{\frac12-2\epsilon}$ and $r,t\asymp K^{\frac14+\epsilon}$ holds with some fixed $\epsilon>0$ and $K>0$ is a large parameter. ...
- 13.9k
2
votes
0
answers
192
views
A conjecture on crossing numbers related to primes
For a permutation $\sigma\in S_n$, its crossing number $\text{cr}(\sigma)$ is the number of pairs $\{i,j\}$ with $i,j\in\{1,\ldots,n\}$ such that
$$i<j\le\sigma(i)<\sigma(j)\ \ \text{or}\ \ \...
- 15.6k
2
votes
0
answers
167
views
What about series involving strong primes?
I know about the importance in analytic number theory of the sutdy of series involving prime numbers or constellations of prime numbers, for example, if I am not wrong, major theorems are Mertens' ...
2
votes
0
answers
301
views
Distribution of Goldbach's weak-conjecture's prime-triples
From Harald Helfgott's proof of Goldbach's weak conjecture,1
we know that every odd number $> 7$ is the sum of three odd primes.
If $n$ is such an odd number, say that two sums that yield $n$
are ...
- 151k
2
votes
0
answers
112
views
Queries on distribution of prime divisors by magnitude?
Erdos-Kac law state a typical number of magnitude $n$ has $\log\log n$ prime factors and we know probability of square free integers is $\frac{6}{\pi^2}$.
What is the probability distribution of ...
- 13.9k
2
votes
0
answers
140
views
Primality radii and Sidon sets
I learned tonight what a Sidon set is, in a book about Erdős. This notion inspires me the following question :
For $n$ a large enough composite integer, say $r>0$ is a primality radius of $n$ if ...
- 6,984
2
votes
0
answers
121
views
How to choose a prime p s.t. n-th cyclotomic polynomial splits into as much as possible irreducible polynomials while p is almost constant size?
The reason I ask this question is that cyclotomic polynomial is critical to the construction of lattice-based cryptography. In most of the existing lattice-based cryptographic schemes, $n$ is usually ...
- 33
2
votes
0
answers
160
views
Where can I find a copy of this paper of Chowla and Vijayaraghavan?
Does anyone know where I can find a copy of Chowla and Vijayaraghavan's paper, ''On the largest prime divisors of numbers''?
The relevant literature say it was published in the Journal of the Indian ...
- 1,019
2
votes
0
answers
76
views
Is there an estimate available for a sum of the form $\sum_{\mathbf{x} \equiv \mathbf{a} (H) } \mu^2(x_1 x_2)$
I am interested in a sum of the shape
$$
\sum_{ \substack{ 1 \leq x_1, x_2 \leq B\\
\mathbf{x} \equiv \mathbf{a} (H) } } \mu^2(x_1 x_2).
$$
I figured it must have been considered before, but I have ...
- 3,625
2
votes
0
answers
100
views
sufficient criteria for a number to be composite
It is well known (since Euler) that if a positive integer $N$ can be written as a sum of two squares in at least two essentially different ways, then $N$ is composite.
In other words, if
$N=a^2+b^2=...
- 231
2
votes
0
answers
109
views
Roots of unity, vanishing sums and derivatives
Fix integers $n\geqslant1$ and $k\geqslant 0$. For an
integer $i$, the $k$-fold derivative of $x^i$ can be denoted by
$i^{\underline{k}}x^{i-k}$ where $i^{\underline{k}}$ means
$i(i-1)\cdots(i-k+1)$ ...
- 1,991
2
votes
0
answers
116
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 ...
- 15.6k
2
votes
0
answers
306
views
Conjectured initial values of Inkeri's primality test for Fermat numbers
This is a repost of this question .
Can you provide a proof or a counterexample to the claim given below ?
First , we shall give a definition of the Inkeri's primality test for Fermat numbers :
...
- 2,661
2
votes
0
answers
147
views
Skewes' number and the ratio $\frac{\operatorname{li}(x^{1/2})}{\operatorname{li}(x)-\pi(x)}$
(A complementary post is here.)
Given the prime counting function $\pi(x)$ and the logarithmic integral $\operatorname{li}(x)$, we have Table 1,
$$\begin{array}{|c|l|}
\hline
x&\operatorname{li}...
- 12.6k
2
votes
0
answers
282
views
Factorization in the Omnific Integers
I'm wondering if there's been any work done on prime factorizations of Omnific integers as products of prime Omnific integers.
I suspect that each Omnific integer has a unique prime factorization, ...
- 10.1k
2
votes
0
answers
107
views
Maximization of product over primes
I have the following maximization problem. Let $f(p)$ be a real function on the primes, having values in $(0,1)$. Assume that $Y$ is a given (large) positive number, and that we have the bound
$$\...
- 2,207
2
votes
0
answers
142
views
Applicability of results about prime gaps
I am interested in some general result about the gap between consecutive primes. This means that this result can be used in a proof of facts about all the primes: it is possible to use tables of gaps ...
2
votes
0
answers
183
views
Claim in OEIS will give some results about Legendre's and Brocard's conjectures
Claim in OEIS will give non-trivial results about Legendre's and Brocard's conjecture. The claim is very likely to be true, but I am not sure it is currently provable.
Brocard's conjecture
states ...
- 25.4k
2
votes
0
answers
197
views
Quasiprimes in arithmetic progressions
Let
$$\Lambda_z(n) = \sum_{d|n, d>z} \mu(d) \log(d/z).$$
As S. Graham proved in 1978,
$$\sum_{n\leq x} |\Lambda_z(n)|^2 \sim x \log(x/z).$$
provided $x\geq z$.
We also know that, by the large ...
- 20.2k
2
votes
0
answers
149
views
$f(x)$-th largest number of prime factors
Given a sufficiently well-behaved function $1\le f(x)\le x$ and a multiset $S=\{\omega(n): 1\le n\le x\}$, what can be said about the asymptotics of the $f(x)$-th largest member of $S$? In other words,...
- 9,114
2
votes
0
answers
236
views
On the cardinality of the set of right-truncatable primes
We say that the (base ten) prime number $p=a_{n}a_{n-1}a_{n-2}\cdots a_{1}a_{0}$ is right-truncatable if all of the following numbers are prime:
\begin{eqnarray*}a_{n},\\a_{n}a_{n-1},\\ a_{n}a_{n-1}...
- 8,842
2
votes
0
answers
392
views
How big can a set of integers be if all pairs have bounded gcd
In this recent MO question, it was shown that the maximal cardinality of a subset $A(M,N)$ of $[1,N]$ where the pairwise GCD's of all set elements are upper bounded by $M,$ with $M^2\leq N$ has size ...
- 10.4k
2
votes
0
answers
306
views
Avoiding Chinese Remainder Theorem
Given $k\in\Bbb N$ with $k<(\log_2N)^{\frac1\alpha}$ where $\alpha>2$ is fixed and $N$ being some integer such that $$N<\prod_{i=1}^k\pi_i^{a_i}$$ where $\pi_1,\pi_2,\dots,\pi_{k-1},\pi_k$ ...
user76479
2
votes
0
answers
246
views
Squarefree part of a Mersenne number
Consider the Mersenne number; $M_p=2^p−1$.
Let $M_p=a_pb^2_p$ where $a_p$ is positive, squarefree, and $p$ is prime.
A chinese paper written by Le Maohua "“On Mersenne Numbers”" states that the ...
- 121
2
votes
0
answers
617
views
Arithmetic progression and average of two prime numbers
Let $A=(a_n : n \in \mathbb{N})$ be the sequence given by:
$$
\ a_n = a_1 + (n - 1)d,\quad a_1,\ d,\ n \in \mathbb N,\quad d\gt a_1,\quad \gcd(a_1,\ d)=1.
$$
For all terms of $A$ greater than $\ \...
- 359
2
votes
0
answers
388
views
Relation between Maier's theorem and a conjecture of Montgomery and Soundararajan
Let us consider the number of primes in the interval $[N,N+h]$, with $h\leq N$. According to the answer given by Lucia to a previous question on the distribution of primes, it is natural to consider ...
- 965
2
votes
0
answers
207
views
n-ary quadratic forms with $S$-integer values
Let $Q(x_1,\ldots,x_n):=x_1^2+\cdots+x_n^2$ be an $n$-ary quadratic form.
Given a finite set of (rational) primes $S$ is there an algorithm or theorem that describes all solutions to $Q(x_1,\ldots,...
- 1,639
2
votes
0
answers
229
views
Analytic varieties for the primes and the twin primes
I am wondering what real and complex analysis say
about the primes and twin primes.
According to Wikipedia
analytic variety is defined locally as the set of common zeros of finitely many analytic ...
- 25.4k
2
votes
0
answers
311
views
A question concerning the strange arithmetic derivation
This question is related to Strange (or stupid) arithmetic derivation. The original question whether an unbounded sequence of iterates exists is still unanswered.
$$n=\prod_{i=1}^{k}p_i^{\alpha_i} \...
- 432
2
votes
0
answers
221
views
Determine whether if $n$ is a primitive pseudoperfect (semiperfect) number, then $\sigma(n)<2^{\sigma_0(n)}$
Determine whether if $n$ is a primitive pseudoperfect (semiperfect) number, then $\sigma(n)<2^{\sigma_0(n)}$.
$\sigma_k(n)$ is the division function and $\sigma(n)=\sigma_1(n)$. A number is ...
- 205
2
votes
0
answers
170
views
Steps required to recognise a $z$-smooth number
I am currently reading section 5 of Pomerance's paper The Number Field Sieve and I have a few questions about smooth numbers.
A number $x\in\mathbb Z_{\ge1}$ is called $z$-smooth if every prime ...
user37200
2
votes
0
answers
555
views
On the primitive prime divisors of $q^n-1$
Let $q=p^\alpha$ be a prime power.
We call $r$ a primitive prime divisor of $q^n-1$ where $r\mid (q^n-1)$ but $r\nmid (q^i-1)$ for each $1\leq i\leq n-1$. The set of all primitive prime divisors of $...
- 1,168
2
votes
0
answers
224
views
Something Diophantine
Hi there,
recently I came across the following divisibility question, and I wondered if much
can be said about it.
Let $p$ and $q$ be different primes, and suppose $p^n + q^r$ divides $p^{2m} - 1$, ...
- 4,547
2
votes
0
answers
310
views
Algorithm for keeping a concrete version of Euclid's argument simple
(A version of this same question was posted to stackexchange.)
Suppose we do what Euclid wrote about: starting with a finite set of primes, multiply them, add or subtract 1, factor the result, append ...
2
votes
0
answers
493
views
How small can intervals be and still contain a prime times a power of 2?
There was a question on MathOverflow which has since disappeared,
that was on sums of at most $M$ B-smooth numbers. It asked
several questions related to how many B-smooth numbers could be found in ...
- 13k
2
votes
0
answers
292
views
Prime divisors of the difference set
Fix $c\in(0,1)$, and let $N$ be a (large) positive integer. Given a set $A=\{0=a_1<\dots<a_n=N\}$ of density $\alpha:=n/N>c$ with $\gcd(A)=1$, I want to find a prime dividing as few ...
- 23k
1
vote
0
answers
102
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
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 $\...
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
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
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 $...
- 1,257
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 ...
- 499
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
1
vote
0
answers
152
views
On lacunary series connected with prime number theory
Consider the following lacunary sum with parameter $x$:
$$S(x)=\sum_{n=5}^{\infty}\sin^2\left(\frac{x\Gamma(n)}{n}\right).$$
As we can see for $x=\frac{\pi}{2}$
the sum becomes$$\sum_p\cos^2\left(\...
- 790
1
vote
0
answers
78
views
Partial sums of Möbius function and Euler characteristic of a simplicial complex for closed sets of a topology on the prime powers?
In A cell complex in number theory by Anders Björner, 2011 a number theoretic cell complex is described which has the property that the Euler characteristic is related to the Mertens function:
$$M(n) =...
- 3,064
1
vote
0
answers
99
views
On the existence of a sequence of prime numbers satisfying a recursion relation
I am interested in the following question. I will be grateful for any reference, comment, or solution.
Let $p_1\geq 5$ be a given prime number. Does there exist an infinite sequence of prime numbers $...
- 391
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
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
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
1
vote
0
answers
104
views
Validity of analysis of summation of function of primes using Abel–Plana summation:
Consider the analytic function $g(x)$
Define
$$f(x)=g(x)\frac{\sin^2\left(\frac{π\Gamma(x)}{2x}\right)}{\cos^2\left(\frac{π}{2x}\right)}$$
Note that:
$$f(p)=g(p) \text{ for prime } p$$
And $f(n)=0$ ...
- 790