3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ ${\rm mod}\ 53\!:\ \dfrac{\color{#c00}1}6 \equiv \dfrac{\color{#c00}{54}}6\equiv 9\ \ $ $\endgroup$ – Bill Dubuque Mar 20 '14 at 17:28
  • $\begingroup$ @rah4927 Looks like your above comments was intended for the answer below. $\endgroup$ – Bill Dubuque Mar 20 '14 at 17:31
  • $\begingroup$ @Bill dubuque,yes,it was. $\endgroup$ – rah4927 Mar 20 '14 at 17:34
  • $\begingroup$ @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. $\endgroup$ – rah4927 Mar 20 '14 at 17:36
  • $\begingroup$ Also,to actually know about methods of solving them,a simple google search will suffice. $\endgroup$ – rah4927 Mar 20 '14 at 17:41
3
$\begingroup$

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

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

$\endgroup$
  • $\begingroup$ For the generalization, we can use en.wikipedia.org/wiki/Continued_fraction#Some_useful_theorems $\endgroup$ – lab bhattacharjee Mar 20 '14 at 16:57
  • $\begingroup$ @rah4927, as $(6,53)=1,6^{-1}\pmod{53}$ always exists. I've multiplied either sides by $6^{-1}$ $\endgroup$ – lab bhattacharjee Mar 20 '14 at 16:58
  • $\begingroup$ 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? $\endgroup$ – Andrew Thompson Mar 20 '14 at 17:01
  • $\begingroup$ @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. $\endgroup$ – rah4927 Mar 20 '14 at 17:05
  • $\begingroup$ As a first-year, such methods are still above my league :) $\endgroup$ – Andrew Thompson Mar 20 '14 at 17:06

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.