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!

  • 2
    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$.2012-12-18
  • 0
    could you expand on that a little please? I still dont quite grasp the concept2012-12-18
  • 12
    No, but you could try thinking about it for more than three minutes.2012-12-18

1 Answers 1

2

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$

  • 16
    Thank you for insuring that OP will never have to think again.2012-12-18
  • 0
    @AndréNicolas, thanks for your observation. Rectified.2012-12-18
  • 0
    Wish I knew my fault here that has caused the downvote2013-03-28
  • 0
    Wasn't me downvoting, but did you give any thought to the comments I left?2013-04-01
  • 0
    @GerryMyerson, then, I'm not sure if I understood your point clearly. Would you please elaborate a bit?2013-04-01
  • 0
    lab, my point was that, by doing the entire problem, you left nothing for OP to do. You deprived OP of the joy of figuring out some details for himself (or herself). And if this was a homework problem, you enabled OP to copy your solution and hand it in without him having to think about it or learn anything from it. Is that clearer?2013-04-02
  • 1
    @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.2013-04-02