# Finding the remainder of $49!$ when divided by $53$

I wish to find the remainder of $49!$ when divided by $53$. We have that $52! \equiv -1 \pmod {53}$ by Wilson's Theorem. So we have $52\cdot 51 \cdot 50 \cdot 49! \equiv -1 \pmod {53} \implies 6\cdot 49! \equiv 1 \pmod{53}$. I am not sure what to do here. I do have a feeling that some sort of manual check/trick is needed, but I am unable to see it.

• ${\rm mod}\ 53\!:\ \dfrac{\color{#c00}1}6 \equiv \dfrac{\color{#c00}{54}}6\equiv 9\ \$ – Bill Dubuque Mar 20 '14 at 17:28
• @rah4927 Looks like your above comments was intended for the answer below. – Bill Dubuque Mar 20 '14 at 17:31
• @Bill dubuque,yes,it was. – rah4927 Mar 20 '14 at 17:34
• @Andrew,no this is not out of your league.See millersville.edu/~bikenaga/number-theory/linear-diophantine/… for a reasonably good explanation of Linear diophantine equations.Enjoy. – rah4927 Mar 20 '14 at 17:36
• Also,to actually know about methods of solving them,a simple google search will suffice. – rah4927 Mar 20 '14 at 17:41

## 1 Answer

So, $\displaystyle49!\equiv 6^{-1}\pmod{53}$

Now, as $\displaystyle6\cdot9=54\equiv1\pmod{53}, 6^{-1}\equiv9\pmod{53}$

• For the generalization, we can use en.wikipedia.org/wiki/Continued_fraction#Some_useful_theorems – lab bhattacharjee Mar 20 '14 at 16:57
• @rah4927, as $(6,53)=1,6^{-1}\pmod{53}$ always exists. I've multiplied either sides by $6^{-1}$ – lab bhattacharjee Mar 20 '14 at 16:58
• Alright, so if I were to calculate another example, this would be right: I wish to find $24!$ mod $29$. We know that $28! \equiv -1$ mod $29$, so we have $5 \cdot 24! \equiv 1$ mod $29$, $24! \equiv 5^{-1}$ mod $29$ and since $6 \cdot 5 = 30 \equiv 1$ mod $29$ we have, because $5\cdot 24! \equiv 1$ mod $29$ that $24! \equiv 6$ mod $29$. Am I correct? – Andrew Thompson Mar 20 '14 at 17:01
• @Andrew,the method is indeed correct.And just for completeness,the inverse can also be found using other methods as solving a linear diophantine equation. – rah4927 Mar 20 '14 at 17:05
• As a first-year, such methods are still above my league :) – Andrew Thompson Mar 20 '14 at 17:06