What remainder does $34!$ leave when divided by $71$? What is the remainder of $34!$ when divided by $71$?
Is there an objective way of solving this?
I came across a solution which straight away starts by stating that
$69!$ mod $71$ equals $1$ and I lost it right there.
 A: 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$.
A: 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}$.
A: 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}.
$$
