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, privacy policy and cookie policy

Browse other questions tagged or ask your own question.