Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

prove $$18! \equiv -1 \pmod{437} $$

I do not want full solution to the above problem but if anybody can tell me how we can approach to it, I will really appreciate that.

share|improve this question
5  
Note $437 = 19\cdot 23$. –  Sean Eberhard Aug 26 '12 at 9:26

3 Answers 3

up vote 7 down vote accepted

hints :

  • $437=19\cdot 23$ (as proposed by Sean)
  • Wilson's theorem :-)
  • $19\cdot 20\cdot 21 \cdot 22=(-4)(-3)(-2)(-1)\pmod{23}$
share|improve this answer

As noted by Sean, $\,427=19\cdot 23\,$, thus using Wilson' theorem twice: $$(1)\,\,\,18!\cdot 19\cdot 20\cdot 21\cdot 22=22!=-1\pmod {23}\Longrightarrow $$ $$\Longrightarrow 18!=\frac{-1}{(-4)(-3)(-2)(-1)}=-\frac{1}{24}=-1\pmod {23} $$ $$(2)\,\,\,\,18!=-1\pmod {19}$$

share|improve this answer
2  
Is this not a full solution? –  awllower Aug 26 '12 at 10:43
    
Not yet...but almost. The gist of it all is number (1), as (2) is directly Wilson's Theorem –  DonAntonio Aug 26 '12 at 10:48
    
Indeed, this cqn be interpreted this way!! –  awllower Aug 26 '12 at 10:49

Wilson's Theorem: (p-1)! = -1 (mod p), p: is a prime number

Note: When I write the "equal" (=) sign, I mean the congruence sign.....

437 is not a prime number: 437 = 19*23

For: 19 By Wilson's Theorem => 18! = -1 (mod 19)

For 23: By W.T => 22! = -1 (mod 23) => 22*21*20*19*18! = -1 (mod 23)

For 22 = -1 (mod 23) For 21 = -2 (mod 23) For 20 = -3 (mod 23) For 19 = -4 (mod 23)

We multiply our reminders => (-1)(-2)(-3)*(-4) = 24

Back to our equation: 22*21*20*19*18! = -1 (mod 23) transformed to => (-1)(-2)(-3)*(-4) = 24 * 18! = -1 (mod 23)

For 24 = 1 (mod 23) (replace 24 by 1)

1 * 18! = -1 (mod 23)

So, 18! = -1 (mod 23)

Hope it helps you understand it more.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.