Qué resto hace 34! licencia cuando se divide por 71??

Question

¿Qué es el resto de $ \frac{34!}{71} $? ¿Existe alguna forma objetiva de resolver esto?

Me encontré con una solución que inmediatamente comienza afirmando que $69!$mod $71$ es igual a $1$ y he perdido ahí.

Answer 1

Mientras que sin duda podemos mostrar que $35! \equiv \pm 1 \pmod{71}$, decidir entre estos dos es que al parecer, lejos de primaria. Esto ha sido tratado en MathOverflow, y las respuestas no dan la siguiente fórmula, si $p > 3$ es un primer congruente a $3$ mod $4$: $$ \left( \frac{p-1}{2} \right)! = (-1)^{(1 + h(-p))/2} $$ con $h(-p)$ denota el número de Clase del campo $\mathbb{Q}(\sqrt{-p})$. En este caso el número de clase de $\mathbb{Q}(\sqrt{-71})$ $7$ (fuente: 1, 2), así tenemos $$ 35! \equiv (-1)^{\left( 1 + 7 \right)/2} = 1 \pmod{71} $$ y $$ 34! \equiv (35)^{-1} 35! = (-2)(1) \equiv \boxed{69} \pmod{71}. $$

Answer 2

De $$69!=1\mod 71\Rightarrow 34!36!=-1\mod 71$$ Multiplying both sides by $4$ and noting that $35\cdot 2 =-1\mod 71, \ 36\cdot 2 = 1\mod 71$, we get $$(34!)^2=4\mod 71\Rightarrow x^2=4\mod 71$$ where $34!=x\mod 71$ So, $$71|(x-2)(x+2)\Rightarrow x+2=71, or \ x=2\Rightarrow x=69\ or\ 2$$ since $1\le x\le 70$.

Answer 3

Continuando en la línea de Georgina Mukhopadhyay la respuesta de un método que es apenas más fácil de lo que en realidad computing $34!\pmod{71}$ simplemente multiplicando el factor por factor:

Por Wilson del teorema sabemos que $70!\equiv-1\pmod{71}$, del que se desprende que $$(34!)^2\times35\times36\equiv34!\times36!\equiv70!\equiv-1\pmod{71}.$$ Debido a $2\times35\equiv-1\pmod{71}$ $2\times36\equiv1\pmod{71}$ vemos que $$(34!)^2\equiv-4\times(34!)^2\times35\times36\equiv4\pmod{71},$$ lo que muestra que $34!\equiv\pm2\pmod{71}$.

Tenga en cuenta que $-1$ no es un residuo cuadrático módulo $71$$71\equiv3\pmod{4}$. Sin embargo $2$ es una ecuación cuadrática de residuos debido a $71\equiv-1\pmod{8}$, y por lo tanto $-2$ es no un residuo cuadrático módulo $71$. Algunos de la mano contando muestra que la plaza de la parte libre de $34!$ es igual a $$3\times5\times11\times19\times23\times29\times31.$$ Así que la pregunta ahora es si este es un residuo cuadrático módulo $71$. Por la ley de la reciprocidad cuadrática, y usando el hecho de que $19\equiv3\pmod{8}$$23\equiv-1\pmod{8}$, vemos que \begin{eqnarray*} \left(\frac{3}{71}\right)&=&-\left(\frac{-1}{3}\right)=1,\\ \left(\frac{5}{71}\right)&=&\left(\frac{1}{5}\right)=1,\\ \left(\frac{11}{71}\right)&=&-\left(\frac{5}{11}\right)=-\left(\frac{1}{5}\right)=-1,\\ \left(\frac{19}{71}\right)&=&-\left(\frac{14}{19}\right)=-\left(\frac{2}{19}\right)\left(\frac{7}{19}\right)=-\left(\frac{5}{7}\right)=-\left(\frac{2}{5}\right)=1,\\ \left(\frac{23}{71}\right)&=&-\left(\frac{2}{23}\right)=-1,\\ \left(\frac{29}{71}\right)&=&\left(\frac{13}{29}\right)=\left(\frac{3}{13}\right)=\left(\frac{1}{3}\right)=1,\\ \left(\frac{31}{71}\right)&=&-\left(\frac{9}{31}\right)=-1. \end{eqnarray*} Nos encontramos con un número impar de no-plazas en el producto anterior, lo que demuestra que es no es un residuo cuadrático módulo $71$, y, por tanto,$34!\equiv-2\equiv69\pmod{71}$.