1
$\begingroup$

Show: $(27!)^6 \equiv 1 \pmod{899}$. Note: $899=30^2 - 1$.

Could anyone show me how to go through this please? I think I have to use Wilson's theorem which is $(p-1)! \equiv -1 \pmod p$ but not exactly sure how else to tackle this. Thanks!

$\endgroup$
3
  • 3
    $\begingroup$ Hints: $30^2-1=(30+1)(30-1)$; $30+1$ and $30-1$ are close enough to $27$ to make Wilson's Theorem an attractive option; $n\equiv-(p-n)\pmod p$. $\endgroup$ Dec 18, 2012 at 5:28
  • $\begingroup$ could you expand on that a little please? I still dont quite grasp the concept $\endgroup$
    – Jack
    Dec 18, 2012 at 5:31
  • 12
    $\begingroup$ No, but you could try thinking about it for more than three minutes. $\endgroup$ Dec 18, 2012 at 5:33

1 Answer 1

2
$\begingroup$

Using Wilson's Theorem, $28!\equiv-1\pmod{29}\implies 27!(28)\equiv-1$ $\implies 27!(-1)\equiv-1\implies 27!\equiv1\pmod {29}$

$\implies (27!)^6\equiv 1\pmod{29}$

Again $30!\equiv-1\pmod{31} \implies 27!(28)(29)(30)\equiv-1$ $\implies 27!(-3)(-2)(-1)\equiv-1\implies 27!(6)\equiv1 \implies 27!(30)\equiv5$ (multiplying either sides by $5$) $\implies 27!(-1)\equiv5\implies 27!\equiv-5\pmod{31}$

So,$(27!)^6\equiv 5^6\pmod{31}$

Now, $5^3=125\equiv1\pmod{31} \implies (27!)^3\equiv -1\pmod{31}$

$\implies (27!)^6\equiv (-1)^2\pmod{31}\equiv1$

So, lcm$(31,29)\mid \{(27!)^6-1\}$ but lcm$(31,29)=31\cdot 29=899$

$\endgroup$
7
  • 16
    $\begingroup$ Thank you for insuring that OP will never have to think again. $\endgroup$ Dec 18, 2012 at 6:05
  • $\begingroup$ @AndréNicolas, thanks for your observation. Rectified. $\endgroup$ Dec 18, 2012 at 6:11
  • $\begingroup$ Wish I knew my fault here that has caused the downvote $\endgroup$ Mar 28, 2013 at 9:00
  • $\begingroup$ Wasn't me downvoting, but did you give any thought to the comments I left? $\endgroup$ Apr 1, 2013 at 11:59
  • 1
    $\begingroup$ @GerryMyerson, I completed the answer it to make things perfect and also because it was not marked 'homework'. But, I got your idea and will try to follow it sincerely. $\endgroup$ Apr 2, 2013 at 15:05

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.