Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
2  
The reason it's true is because of Wilson's theorem if that's what you are asking. –  Jack Yoon May 14 at 12:02
3  
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 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. –  Goos May 14 at 13:09
    
another somewhat relevant oeis. –  Goos May 14 at 13:13
    
@Goos See this OEIS sequence. and this one. –  Bill Dubuque May 14 at 16:02

3 Answers 3

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|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|improve this answer
4  
Not so fast. How do you know $x$ isn't $2$? –  Goos May 14 at 12:55
1  
Well, which is it? :D –  Zubin Mukerjee May 14 at 13:07
1  
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 at 13:36
4  
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 at 13:39
1  
$-2$. I used factors of $70$, $72$, $143$, $285$, $425$, and $496$ to reduce it. –  Zubin Mukerjee May 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|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. –  Goos May 16 at 20:54

Your Answer

 
discard

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.