Encontrar el resto $R$ $(1^2+1)(2^2+1)...(p^2+1)$ dividido por $p$

Question

Encontrar el resto $R$ de $(1^2+1)(2^2+1)...(p^2+1)$ dividido por $p$, $p$ ser un número primo mayor que $3$.

Para $p \equiv 1 \mod 4$, existe un entero $j$ tal que $p\mid j^2+1$ (desde $-1$ es un residuo cuadrático de $p$), por lo tanto, $R=0$.

Para $p \equiv 3 \mod 4$, ¿cómo podemos encontrar $R$? No $R$ dependen del valor de $p$?

Answer 1

Si $p=2$ o $p\equiv 1\pmod{4}$, a continuación, $R$ es obviamente $0$ porque $-1$ es un residuo cuadrático módulo $p$. Suponemos que a partir de ahora en ese $p\equiv 3\pmod{4}$.

Deje $f(x)$ denotar el polinomio $x^p-x$ sobre el campo de Galois $K=\operatorname{GF}(p)$. Tenga en cuenta que $f$ factorizes en $$f(x)=\prod_{t\in K}(x-t).$$ Deje $E$ ser la extensión de $K[X]/(X^2+1)$ de $K$, que es el campo de Galois $\operatorname{GF}(p^2)$. (Aquí es donde utilizamos el supuesto de que $p\equiv 3\pmod{4}$, desde el $X^2+1$ es irreducible sobre $K$.) Escribir $i$ para la imagen de $X$ bajo la proyección canónica $K[X]\to K[X]/(X^2+1)=E$.

Ahora, tenemos $$R=\prod_{k=1}^p(k^2+1)=\prod_{k=1}^p(i-k)(-i-k)=\left(\prod_{k=1}^p(i-k)\right)\left(\prod_{k=1}^p(-i-k)\right).$$ Por la definición de $f$, obtenemos $$R=f(i)f(-i)=\left(i^p-i\right)\left((-i)^p-(-i)\right)=\left(i^{p-1}-1\right)\left((-i)^{p-1}-1\right).$$ Desde $\frac{p-1}{2}$ es impar, tenemos $$R=\left((-1)^{\frac{p-1}{2}}-1\right)\left((-1)^{\frac{p-1}{2}}-1\right)=\big((-1)-1\big)^2=4.$$ Esta es una igualdad en $K$. La traducción de este resultado a $\Bbb{Z}$, llegamos a la conclusión de que $$R=\begin{cases} 0&\text{if}\ p=2 \vee p\equiv 1\pmod{4},\\ 1&\text{if}\ p=3,\\ 4&\text{if}\ p>3 \wedge p\equiv 3\pmod{4}. \end{casos}$$

Answer 2

Si $ p $ no $ 3 $ modulo $ 4 $ la expresión dada es trivialmente $ 0 $, por lo que asumen $ p \equiv 3 \pmod{4} $.

Considere el polinomio

$$ P(x) = \prod_k (x + k) $$

donde el producto se toma sobre todos los $ k $ que son residuos cuadráticos mod $ p $ (excluyendo $ 0 $). En primer lugar, observe que si $ r $ es una ecuación cuadrática de residuos de mod $ p $, luego

$$ P(r) = \prod_k (r + k) = r^{(p-1)/2} \prod_k (1 + k r^{-1}) = \prod_k (1 + k) = P(1) = c $$

Además, se sigue por la vinculación de cada uno de no-identidad de residuos cuadráticos con su inverso que $ P(0) = 1 $. El único polinomio de mod $ p $ grado $ \leq (p-1)/2 $ que cumple con estas condiciones es $ (c-1) x^{(p-1)/2} + 1 $ (es fácil comprobar que tiene los valores necesarios, y la singularidad es fácil de ver). Desde $ P $ ha líder coeficiente de $ 1 $, se deduce $ c = 2 $, y por lo $ P(1) = 2 $. La expresión dada en la pregunta es $ P(1)^2 $, que por lo tanto es siempre igual a $ 4 $ mod $ p $.

Answer 3

Deje $p$ ser una de las primeras, con $p\equiv 3\;(\text{mod}\;4)$.

Reclamo: $$\prod_{k=1}^p (1+k^2)\equiv 4\;(\text{mod}\;p)$$ Prueba: \begin{align*} \prod_{k=1}^p (1+k^2)\;(\text{mod}\;p) &\equiv \prod_{k=1}^{p-1} (1+k^2)\;(\text{mod}\;p) \\[4pt] &\equiv \left(\prod_{k=1}^{\frac{p-1}{2}}(1+k^2)\right)^{\!\!2}\;(\text{mod}\;p) \\[4pt] \end{align*}

Por lo tanto, para demostrar la afirmación, basta para mostrar $$ \prod_{k=1}^{\frac{p-1}{2}}(1+k^2)\equiv 2\;(\text{mod}\;p) $$ Tenga en cuenta que $$1+1^2,1+2^2,...,1+\left({\small{\frac{p-1}{2}}}\right)^{\!2}$$ son distintos mod $p$, y son las raíces de la congruencia $f(x)\equiv 0\;(\text{mod}\;p)$, donde $$f(x)=(x-1)^{\frac{p-1}{2}}-1$$ Desde $p\equiv 3\;(\text{mod}\;4)$, se deduce que el $\frac{p-1}{2}$ es impar, por lo tanto el término constante de $f$ es $-2$.$\\[4pt]$

Tenga en cuenta que $f$ es monic, por lo tanto, por Vieta de la fórmula, ya $\frac{p-1}{2}$ es impar, y el término constante de $f$ es $-2$, el producto en $Z_p$ de las raíces de la $f$ es $2$, por lo que tenemos $$ \prod_{k=1}^{\frac{p-1}{2}}(1+k^2)\equiv 2\;(\text{mod}\;p) $$ lo que demuestra la demanda.

Por lo tanto, si $p$ es primo, con $p\equiv 3\;(\text{mod}\;4)$, obtenemos $R\equiv 2^2\;(\text{mod}\;p)$, por lo tanto $$ \begin{cases} R=4,\;\text{if}\;p > 3\\[4pt] R=1,\;\text{if}\;p = 3\\ \end{casos} $$

Answer 4

Con esta secuencia de comandos de MATHEMATICA usted puede marcar un montón

n=10000 primes = Select[Range[n], PrimeQ[#] && NextPrime[#] == 2 + # &] p[n_] := Product[1 + k^2, {k, 1, n}] For [j = 1, j <= Length[primes], j++, Print[primes[[j]], " ", Mod[p[primes[[j]]], primes[[j]]]]]

Qué decir acerca de este patrón para el primer grupo ?

$$ \{1,0,4,0,0,0,4,4,0,4,0,0,4,4,0,4,4,0,0,4,4,4,4,0,0,0,4,0,0,4,0,0,4,0,0,4,4,0,0,4,4,0,0,0,0,4,4,4,0,4,4,4,4,0,0,4,4,0,4,0,0,4,0,4,4,0,0,0, 4,0,4,0,0,4,0,4,4,0,0,0,0,4,4,4,4,0,4,0,4,4,0,0,4,4,4,0,0,4,4,0,4,0,0,0,4,0,4,4,0,0,0,0,4,4,0,0,0,0,4,0,0,0,4,4,4,4,0,0,4,4,4,0,0,0,0,4 ,4,4,0,0,0,4,4,0,4,0,0,4,4,0,4,0,4,0,0,0,4,4,4,0,4,4,4,4,4,4,0,0,4,4,4,0,0,0,0,0,4,4,4,4,4,0,0,0,4,4,0,0,0,4,4,0,4,0,0,4,4,0,0,0,0,4,4, 0,0,\cdots \} $$