nt.number theory – Sum of inverse squares of numbers divisible only by primes in the kernel of a quadratic character

Let $chi$ be a primitive quadratic Dirichlet character of d modulus $m$, and consider the product
$$prod_{substack{p text{ prime} \ chi(p) = 1}} (1-p^{-2})^{-1}.$$

What can we say about the value of this product? Do we have good upper or lower bounds?

Some observations, ideas, and auxiliary questions

  • When $chi$ is trivial, it has value $zeta(2)$.
  • In general, since Chebotarev density theorem (CDT) tells us that $chi(p)$ is equidistributed in the limit, I would “want” the value to be something like

$$Big(zeta(2)prod_{p | m} (1-p^{-2})Big)^{frac{1}{2}}.$$

However, if I’m not mistaken, it seems that the error terms in effective forms of CDT may cause this to be very far from the truth. We can’t ignore what happens before we are close to equidistribution as the tail and the head are both $O(1)$. We can’t even control the error term well (without GRH) because of Siegel zeroes.

  • I don’t think we can appeal to Dirichlet density versions of CDT since those only tell us things in the limit as $s$ goes to $1$ and here $s = 2$.
  • Is there a way to “Dirichlet character”-ify a proof of $zeta(2) = pi^2/6$ to get a formula for this more general case? At least with Euler’s proof via Weierstrass factorization, it seems that we would need some holomorphic function which has zeroes whenever $chi(n) = 1$.

I had a few other ideas but they all seem to run into the same basic problem of “can’t ignore the stuff before the limit”… am I missing something?

nt.number theory – Why is the mobius function multiplicative in the case where the numbers contain overlapping primes?

I’m trying to understand how the Mobius function is multiplicative in the case when the two numbers, let’s say m and n have overlapping prime, call it pi. Then if F is the Mobius function,

what I see is:

F(m)F(n) = -1*-1 = 1

Assuming they both have an odd number of prime factors. How does this become 0, as it should, since mn has a factor of pi2?

elementary number theory – Proving there are infinitely many primes in 5 ways

I need to remember for the test 5 different ways of proving that there are infinitely many primes. Now, I have learned to prove the infinity of primes by Euclid’s theorem, Euler’s theorem, Fermat numbers, Dirichlet, and the last I don’t remember. I will be happy to see how do you suggest to prove these proofs, so I can remember this for the test. It is my first course in number theory, so I only got elementary tools.

nt.number theory – Small multiplicative order modulo infinitely many primes

Let $a>1$ be an integer. Artin’s conjecture claims that if $a$ is not a perfect square, then $a$ is a primitive root modulo infinitely many primes $p$ (which moreover form a subset of positive density). Alternatively, I interested in situations where ${rm{ord}}_p(a)$ is relatively small compared to $p$ for infinitely many (or a positive density subset of) moduli $p$. So here is my question:

Question. What growth conditions on a function $f:Bbb{N}rightarrowBbb{N}$ guarantee that there exist infinitely many primes $p$ for which ${rm{ord}}_p(a)leq f(p)$? What if instead of the infinitude, we demand that the subset of such primes is of positive density?

I think it is very hard to answer this question if one aims for $f={rm{O}}(log p)$, because if for instance $k:={rm{ord}}_p(2)leqlog_2(2p)$, then $p$ must be a Mersenne prime $2^k-1$, and we do not know if there are infinitely many of those. So let us consider functions of growth ${rm{O}}(p^epsilon)$ where $epsilonin (0,1)$. Even knowing that there is a function $f={rm{O}}(p^epsilon)$ for which the answer to the question above is affirmative when $a=2$ would be very helpful to me.

Question. Are there $epsilonin (0,1)$ and $C>0$ for which the set of primes $p$ with ${rm{ord}}_p(2)leq Cp^epsilon$ is of positive density?

nt.number theory – If we denote $X$ to be the set of primes $p$ such that $N_p(f)>1$ for polynomial $f(x)$, is it true that $X$ has positive relative density?

Let $f(x)in mathbb{Z}(X)$ be an irreducible polynomial and $N_p(f)$ be the number of solutions of congruence $f(x)equiv 0pmod{p}$ for some prime $p$.

Then if we denote $X$ to be the set of primes $p$ such that $N_p(f)>1$, is it true that $X$ has positive relative density in the set of primes?

primes – RSA Encryption for specitic messages x with x = ap mod pq for ap-bq=1

I want to make a following proof but i got some difficulties with it.
Would be super if you people have any tips / advises.


Let (N,e) be our public key and (N,s) our private key with $N=pq$ and $ggT(varphi(n),e)=1$, as well as $esequiv 1mod N$.

I want to show that since Lemma of Bézout shows, that there are $a,bin mathbb{N}$ so that $ap-bq=1$, the message of $x=apmod N$ is equal to the encrypted message $y=x^e mod N$.

My Plan:

I started by using the Chinese remainder theorem. To show $xoverset{!}{=}y=x^emod N$ we need to show, that $xoverset{!}{=}x^emod p$ and $xoverset{!}{=}x^emod q$. I could also use the Chinese remainder theorem on $x=apmod N$.

So i need to show, that $ap mod p=(ap)^emod p$. Since ap is a multiple of p, it should be $apequiv 0mod p$ and so $(ap)^e=0mod p$. It follows that $apmod p=(ap)^emod = p= 0 mod p$.

I now need to show, that $apmod q=(ap)^emod q$. This is the part i am struggeling with. I know that $ap-bq=1$ but I have no glue how this is going to help me. I was thinking about somethink like $ap=(bq+1)mod q$ but i am not sure if this works / what to do next.

How differently would we model the distribution of primes if prime gap is larger?

Cramer’s conjecture based on his random model provides prime gaps are bound by $O(log^2p_n)$ where the gap is between $(n+1)$th and $n$th prime.

  1. How differently would primes be modeled if gaps of $O(2^{mathsf{poly}(loglog p_n)})$ were indeed accurate?

  2. $RH$ predicts a gap of $O(sqrt{p_n}log^2p_n)$ and so if this much larger gap were true will we be much off from 1. and would any ‘random’ model have any relevance?

elementary number theory – Twin primes false $implies (n^2 – 1)$ is the ideal generated by $f in Bbb{Q}[n]$ such that $f(Bbb{Z}) cap Bbb{P}^2$ is finite.

The set of all $f in Bbb{Q}(n)$ such that $f(n) in Bbb{P}^2 = { pq: p,q $ are prime $}$ finitely often is closed under composition and multiplication $fg$ by any element $g in Bbb{Q}(n)$. Since $Bbb{Q}(n)$ is a PID, the set of all such $f$ must be an ideal.

If the twin primes are finite, then $f(n) = n^2 – 1$ is one such function. It is indeed the only such function up to multiplication by $g in Bbb{Q}(n)$. How can I prove that?

If $f’$ is another such function then $f’ = fs + r$ for some $r = 0$ or $deg(r) lt 2$. But then $r = an + b$ for some $a,bin Bbb{Q}$.

primes – Central Trinomial Coefficients best time complexity

What is the fastest known time complexity for computing central trinomial coefficients?

Let $C_n=1,1,3,7,19,51,…$ (OEIS A002426) denote the coefficient of $x^n$ in $(x^2+x+1)^n$ starting at $n=0$.

It can be shown that, if $n$ is prime, then $C_n=1 pmod n$, because by the binomial theorem

$$(x + y)^n=sum_{k=0}^{n} binom{n}{k}y^kx^{n-k}=x^n+y^npmod n$$ so that

$$(x^2+x+1)^n = x^2+x+1pmod n$$


The computational complexity problem I am aiming on solving is, given a large integer $n$ (say, about RSA size), I would like to verify that the congruence

$C_n=1pmod n$

in polynomial time analogous to how $x^n=x pmod n$ can be computed using binary exponentiation.

Thanks for help.