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.

This is how far I've been able to get.

By using Wilson's Theorem:

$$\begin{align} 70! &\equiv -1 \pmod{71} \\ 67!(68)(69)(70) &\equiv -1 \pmod{71} \\ 67!(68)(69)(-1) &\equiv -1 \pmod{71} \\ 67!(68)(69) &\equiv 1 \pmod{71} \\ \end{align}$$

EDIT: Here is how I proceeded using TMM's and Carl Mummert's hints.

$$\begin{align} &68 \equiv -3 \pmod{71}\\ and\\ &69 \equiv -2 \pmod{71}\\ \end{align}$$

So: $$\begin{align} 67!(-3)(-2) &\equiv 1 \pmod{71} \\ 67! &\equiv 6^{-1} \pmod{71} \\ \end{align}$$

By using the Euclidean algorithm: $$71 = 6 \cdot 11 + 5$$ $$6 = 5 \cdot 1 + 1$$ $$5 = 1 \cdot 5 + 0$$

Now, going backwards: $$\begin{align} 1 &= 6 - 5 \\ &= 6 - (71 - 6 \cdot 11) \\ &= 6 + 6(11) - 71 \\ &= 6(1 + 11) - 71(1) \\ &= 6(12) - 71(1) \end{align}$$

Therefore, $67! \equiv 6^{-1} \equiv 12 \pmod{71}$.

share|improve this question
3  
So $67! = 69^{-1}68^{-1}\pmod{71}$. Compute those two inverses and you're done. –  Carl Mummert May 12 '13 at 20:12
1  
You should consider using $ \cdot $ instead of $*$ to denote multiplication for two reasons. Typically, $*$ denotes convolution and $*$ looks ugly when you use it for multiplication. –  user17762 May 12 '13 at 20:46
    
The first steps can be condensed by replacing -1 with 70 right at the outset. –  Kaz May 12 '13 at 21:39
add comment

2 Answers

up vote 6 down vote accepted

Hint: $$69 \equiv -2 \pmod{71}, \qquad 68 \equiv -3\pmod{71}.$$ Further hint: $72 = 6 \cdot 12$, so the inverse you need to compute should not be too difficult...

share|improve this answer
    
Great, thanks. I used the the Euclidean algorithm backwards to find the inverse of 6 mod 71. Also worked out to be 12. –  icanc May 12 '13 at 20:20
1  
@icanc: For small numbers it usually helps to just try and see. As the inverse $x$ of $6$ must be between $1$ and $70$, we must have $6 \leq 6x \leq 420$ and therefore $6x \in \{72, 143, 214, 285, 356\}$. We can already eliminate the two odd numbers, and if necessary check the other three by hand. –  TMM May 12 '13 at 20:26
    
(That of course does not mean that you should not know the Euclidean algorithm. But sometimes it's easier to be smart and lazy...) –  TMM May 12 '13 at 20:32
add comment

Recall that if $$xy \equiv a \pmod{n}$$ then $$x \equiv ay^{-1} \pmod{n}$$ if $y$ is invertible in $\pmod{n}$. In your case, $n$ is $71$ a prime, which guarantees that any $y \not \equiv 0 \pmod{71}$ is invertible in $\pmod{71}$. Hence,, we have $$67! \times 68 \times 69 \equiv 1 \pmod{71} \implies 67! \equiv (69)^{-1} (68)^{-1} \pmod{71}$$ We have \begin{align} 68 \times 47 - 71 \times 45 & = 1\\ 69 \times 35 - 71 \times 34 & = 1 \end{align} Hence, $$(68)^{-1} \equiv 47 \pmod{71} \text{ and }(69)^{-1} \equiv 35 \pmod{71}$$ Hence, $$67!\equiv 35 \times 47 \pmod{71} \equiv 12 \pmod{71}$$

share|improve this answer
add comment

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.