6
$\begingroup$

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 ?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Are you trying to find the remainder of $53!$ or $51!$? $\endgroup$ – Levent Dec 30 '16 at 17:55
  • $\begingroup$ $362880 \equiv 52 \pmod {61}$ So $52\cdot 51! \equiv 1 \pmod{61}$ $\endgroup$ – Darth Geek Dec 30 '16 at 18:00
  • $\begingroup$ Your title says 53! but you are doing 51! Only need to do -7!53! = -1 mod 61. So solve $(-7!)^{-1}$. Figuring out the inverses of -1,... -7 is probably not hard. $\endgroup$ – fleablood Dec 30 '16 at 18:00
  • $\begingroup$ @fleablood It was a typo. Sorry for that . $\endgroup$ – Jon Garrick Dec 30 '16 at 18:06
4
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thanks !! You made it very simplified :) $\endgroup$ – Jon Garrick Dec 30 '16 at 18:16
11
$\begingroup$

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

|cite|improve this answer
$\endgroup$
7
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
1
$\begingroup$

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

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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