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 ?

$\endgroup$
4
  • 1
    $\begingroup$ Are you trying to find the remainder of $53!$ or $51!$? $\endgroup$
    – Levent
    Dec 30, 2016 at 17:55
  • $\begingroup$ $362880 \equiv 52 \pmod {61}$ So $52\cdot 51! \equiv 1 \pmod{61}$ $\endgroup$
    – Darth Geek
    Dec 30, 2016 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, 2016 at 18:00
  • $\begingroup$ @fleablood It was a typo. Sorry for that . $\endgroup$
    – Jon Garrick
    Dec 30, 2016 at 18:06

4 Answers 4

Reset to default
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.

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

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

$\endgroup$
1
  • $\begingroup$ Thanks !! You made it very simplified :) $\endgroup$
    – Jon Garrick
    Dec 30, 2016 at 18:16
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}$.

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