4
$\begingroup$

I posted the question here but I got no response.

I am looking for computing this cardinality: $$N(q)=\#\Bigg\{n \in \mathbb{N} \ | \ \gcd\bigg(n^2+1, \prod_{\substack{p \leqslant q \\ p\text{ prime}}}p\bigg)=1 , \ \ n^2+1 \leqslant \!\!\!\prod_{\substack{p \leqslant q \\ p\text{ prime}}}\!\!p \Bigg\},$$ by using Chinese remainder theorem.

First, for $p$ odd prime and $m\in\mathbb{Z}/p\mathbb{Z}$, the number of solutions of the equation $m^2 + 1 = 0 \pmod p$ is : $$ \begin{cases} 0 & \text{ if } p = 3 \pmod 4 \\ 2 & \text{ if } p = 1 \pmod 4 \end{cases}.$$

Using the Chinese remainder theorem and the fundamental counting principle, I get this result: $$N(q) = \bigg(\prod_{\substack{p \leqslant q \\ p \equiv 3[4] \\ p\text{ prime}}}p \bigg)\prod_{\substack{p \leqslant q \\ p \equiv 1[4] \\ p\text{ prime}}}(p-2) \label{1}\tag{1}$$ Formula \eqref{1} seems not correct as when I check $N(q)$ numerically I do not get the same results as by counting.

The true values are : $$N(7)=5, \ N(11)=15, \ N(13)=45 , \ N(17)=161, \ N(19)=698, \cdots$$

Question: Why my formula \eqref{1} is not correct !? And what is the correct formula ?

Many thanks for any help.

Numerically it's very likely that: $$N(q) \approx \dfrac{1}{\sqrt{\displaystyle \prod_{\substack{p \leqslant q \\ p\text{ prime}}}p }} \, \bigg(\prod_{\substack{p \leqslant q \\ p \equiv 3[4] \\ p\text{ prime}}}p \bigg)\prod_{\substack{p \leqslant q \\ p \equiv 1[4] \\ p\text{ prime}}}(p-2)$$

$\endgroup$
9
  • 2
    $\begingroup$ You can see yourself looking already at $q = 3$, say, that your solution overcounts: it allows all residue classes modulo $p$, but your condition $n^2 + 1 \le \prod p$ allows only some. For example, the only allowable $n$ when $q = 3$ are $n = 0$ and $n = 2$; since $n = 4$ is too big, we already get $N(3) = 2$, not $N(3) = \prod_{\substack{p \le 3 \\ p \equiv 3 \pmod4}} p = 3$ as predicted. $\endgroup$
    – LSpice
    May 3, 2020 at 6:03
  • 1
    $\begingroup$ First of all, you forgot $p=2$, secondly you Chinese remainders method works prexisely only for $n\leq \prod p$ but you need thoose $n$ with $n^2+1\leq \prod p$ $\endgroup$ May 3, 2020 at 6:05
  • $\begingroup$ @LSpice, we have $N(3)=2$, since the only numbers coprime to $6$ and less than $6$ are $1,5$ and both are written as $n^2+1$. As i say formula $(1)$ not correct. $\endgroup$ May 3, 2020 at 10:44
  • $\begingroup$ @PavelKozlov, thank you, i check and you you have right. $\endgroup$ May 3, 2020 at 10:51
  • $\begingroup$ It sounds like you disagree, but actually I think we (and @PavelKozlov) agree. $\endgroup$
    – LSpice
    May 3, 2020 at 13:59

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.