What remainder does $34!$ leave when divided by $71$?

Solution 1:

While we can certainly show that $35! \equiv \pm 1 \pmod{71}$, deciding between these two is apparently far from elementary. This has been dealt with on MathOverflow, and the answers there give the following formula, if $p > 3$ is a prime congruent to $3$ mod $4$: $$ \left( \frac{p-1}{2} \right)! = (-1)^{(1 + h(-p))/2} $$ with $h(-p)$ denoting the Class number of the field $\mathbb{Q}(\sqrt{-p})$. In this case the class number of $\mathbb{Q}(\sqrt{-71})$ is $7$ (source: 1, 2), so we have $$ 35! \equiv (-1)^{\left( 1 + 7 \right)/2} = 1 \pmod{71} $$ and $$ 34! \equiv (35)^{-1} 35! = (-2)(1) \equiv \boxed{69} \pmod{71}. $$

Solution 2:

From $$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$.

Solution 3:

Continuing in the line of Samrat Mukhopadhyay's answer, a method that is hardly any easier than actually computing $34!\pmod{71}$ by simply multiplying factor by factor:

By Wilson's theorem we know that $70!\equiv-1\pmod{71}$, from which it follows that $$(34!)^2\times35\times36\equiv34!\times36!\equiv70!\equiv-1\pmod{71}.$$ Because $2\times35\equiv-1\pmod{71}$ and $2\times36\equiv1\pmod{71}$ we see that $$(34!)^2\equiv-4\times(34!)^2\times35\times36\equiv4\pmod{71},$$ which shows that $34!\equiv\pm2\pmod{71}$.

Note that $-1$ is not a quadratic residue modulo $71$ as $71\equiv3\pmod{4}$. However $2$ is a quadratic residue because $71\equiv-1\pmod{8}$, and therefore $-2$ is not a quadratic residue modulo $71$. Some hand counting shows that the square-free part of $34!$ equals $$3\times5\times11\times19\times23\times29\times31.$$ So the question is now whether this is a quadratic residue modulo $71$. By the law of quadratic reciprocity, and using the fact that $19\equiv3\pmod{8}$ and $23\equiv-1\pmod{8}$, we see that \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*} We find an odd number of non-squares in the product above, which shows that it is not a quadratic residue modulo $71$, and hence $34!\equiv-2\equiv69\pmod{71}$.