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.
algebra-precalculuschinese remainder theoremdivisibilityelementary-number-theoryfactorial
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.
Best Answer
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}. $$