Find the remainder of $51!$ when divided by $61$?

Question

Find the remainder of $51!$ when divided by $61$ ?

---

My Try :

By Wilson's theorem $60! ≡ −1\pmod{61}$

Then, I can write

$(60)(59)(58)(57)(56)(55)(54)(53)(52)51!≡−1\pmod{61}$

$(−1)(−2)(−3)(−4)(−5)(−6)(−7)(−8)(−9)51!≡−1\pmod{61}$

$(362880)51!\equiv1\pmod{61}$

---

How can I proceed after this OR Is there any other approach ?

Answer 1

Continued from your working without evaluating $9!$ explicitly:

$$51!9!\equiv 1 \mod 61$$

$$51! 2(3)(4)(5)(6)(7)(8)(9) \equiv 1 \mod 61$$

Since $2(5)(6)=60$, $$51! (60)(3)(4)(7)(8)(9) \equiv 1 \mod 61$$

$$51! (-1)(3)(4)(7)(8)(9) \equiv 1 \mod 61$$

$$51! (3)(4)(7)(8)(9) \equiv -1 \mod 61$$ Since $9(7)=63$,

$$51! (3)(4)(8)(63) \equiv -1 \mod 61$$

$$51! (3)(4)(8)(2) \equiv -1 \mod 61$$ Since $2(4)(8)=64$, $$51! (3)(64) \equiv -1 \mod 61$$

$$51! (3)(3) \equiv -1 \mod 61$$

$$51! (9) \equiv -1 \mod 61$$

Let's do Euclidean algorithm to compute $9^{-1} \mod 61$:

$$61=9(6)+7$$ $$9=7+2$$ $$7=3(2)+1$$

Hence $$1=7-3(2)=7-3(9-7)=4(7)-3(9)=4(61-9(6))-3(9)=4(61)-27(9)$$

$$9^{-1}\equiv -27 \mod 61$$.

Hence $$51!\equiv 27 \mod 61$$

Answer 2

$60! = -1 \bmod 61$ ------------- By Wilson's theorem
$51! \times 52 \times \cdots \times 60 = -1 \bmod 61$
$51! \times (-9) \times \cdots \times (-1) = -1 \bmod 61$
$51! \times (-1) \times 9! = -1 \bmod 61$

Inverses in the following steps are calculated using Extended Euclidean algorithm. $51! = -1 \times (-1)^{-1} \times 9!^{-1} \bmod 61$
$51! = -1 \times (-1)^{-1} \times 362880^{-1} \bmod 61$
$51! = -1 \times (-1)^{-1} \times 52^{-1} \bmod 61$
$51! = -1 \times -1 \times 27 \bmod 61$

$51! = 27 \bmod 61$
Therefore, the remainder is 27.

Answer 3

Your try is quite right.

Continue with $362880 \text{ (mod 61)} = 52 = -9$. You're left to find an inverse of $9 \text{ mod } 61$.

But $9 \cdot 7 = 63 = 2 \text{ mod 61}$, and $2 \cdot 31 = 1 \text{ mod 61}$. So $9 \cdot 7 \cdot 31 = 1 \text{ mod 61}$. So $9^{-1} = 7 \cdot 31 = 34 = -27 \text{ mod 61}$. Then $(-9)^{-1} = 27 \text{ mod 61}$.

Hence, your answer is $\boxed{27}$.

N.B. : All equalities hold modulo $61$, if not explicitly mentioned.

Answer 4

As you noticed, the question is equivalent to finding $9!\pmod{61}$, and since $$ 9! = 2^6\cdot 3^4\cdot 70 \equiv 3\cdot 17\cdot 7 \equiv -70 \equiv 9\pmod{61} $$ it is enough to find $-9^{-1}\pmod{61}$, that is $-(3^{-1})^2\pmod{61}$.
Since $3^{-1}\equiv 41\pmod{61}$, the answer is $\color{red}{27}$.