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

What is the remainder of $\frac{34!}{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.

-
The reason it's true is because of Wilson's theorem if that's what you are asking. –  Jack Yoon May 14 '14 at 12:02
Like Jack said, Wilson's theorem gives $70!\equiv -1\pmod{71}$. The last factor $70$ is congruent to $-1$ modulo $71$, so if you remove that (divide by the unit $-1$) in the congruence, you have $69!\equiv +1\pmod{71}$. So that was the start. I don't know how your source continued from there to find $34!$. –  Jeppe Stig Nielsen May 14 '14 at 12:23
this is a relevant list. I'm not seeing any easy way to resolve the double-solution you get when solving the quadratic. –  C-S May 14 '14 at 13:09
another somewhat relevant oeis. –  C-S May 14 '14 at 13:13
@Goos See this OEIS sequence. and this one. –  Bill Dubuque May 14 '14 at 16:02

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

-

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

-
Not so fast. How do you know $x$ isn't $2$? –  C-S May 14 '14 at 12:55
Well, which is it? :D –  Zubin Mukerjee May 14 '14 at 13:07
I started writing up an answer because I thought I had solved it, then I realized I couldn't get rid of the $\pm$ in $\pm\, 2$ ... –  Zubin Mukerjee May 14 '14 at 13:36
Yeah, for any prime $p$ of the form $4k+3$, from Wilson's theorem we get $-1 \equiv (p-1)! \equiv -(((p-1)/2)!)^2$ so $((p-1)/2)! \equiv \pm 1$. But running through primes of this form with a computer shows no clear pattern of which sign occurs when. –  Jeppe Stig Nielsen May 14 '14 at 13:39
$-2$. I used factors of $70$, $72$, $143$, $285$, $425$, and $496$ to reduce it. –  Zubin Mukerjee May 14 '14 at 14:28

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

-
+1! I had thought of using quadratic residues to resolve the choice between $2$ and $-2$ but didn't think of doing it like this. –  C-S May 16 '14 at 20:54