Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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. – 6005 May 14 '14 at 13:09
another somewhat relevant oeis. – 6005 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}. $$

share|cite|improve this answer

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

share|cite|improve this answer
Not so fast. How do you know $x$ isn't $2$? – 6005 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}$.

share|cite|improve this answer
+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. – 6005 May 16 '14 at 20:54

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.