# Compute a cardinality using Chinese remainder theorem

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)$$

• 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. May 3, 2020 at 6:03
• 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$ May 3, 2020 at 6:05
• @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. May 3, 2020 at 10:44
• @PavelKozlov, thank you, i check and you you have right. May 3, 2020 at 10:51
• It sounds like you disagree, but actually I think we (and @PavelKozlov) agree. May 3, 2020 at 13:59