I was solving some problems and I came across this problem. I didn't understand how to approach this problem. Can we solve this with out actually calculating $18!\,\,?$

  • 4
    $\begingroup$ $18!+1$ does not divide $437$; do you mean that $437$ divides $18!+1$? $\endgroup$ – Brian M. Scott Nov 30 '12 at 7:15
  • $\begingroup$ thanks for the correction. $\endgroup$ – Phani Raj Nov 30 '12 at 7:17
  • $\begingroup$ i got upto that point. Now we have to prove that 23(because 437=19*23) also divides 18!+1. i am unable to prove that part. $\endgroup$ – Phani Raj Nov 30 '12 at 7:18

Note that $437=(19)(23)$. We prove that $19$ and $23$ divide $18!+1$. That is enough, since $19$ and $23$ are relatively prime.

The fact that $19$ divides $18!+1$ is immediate from Wilson's Theorem, which says that if $p$ is prime then $(p-1)!\equiv -1\pmod{p}$.

For $23$ we need to calculate a bit. We have $22!\equiv -1\pmod{23}$ by Wilson's Theorem.

Now $(18!)(19)(20)(21)(22)=22!$.

But $19\equiv -4\pmod{23}$, $20\equiv -3\pmod{23}$, and so on. So $(19)(20)(21)(22)\equiv 24\equiv 1\pmod{23}$. It follows that $18!\equiv 22!\pmod{23}$, and we are finished.

| cite | improve this answer | |
  • $\begingroup$ Could you explain "relatively prime" in this context? 19 and 23 are prime - what's relative about that? $\endgroup$ – Tim Pietzcker Nov 30 '12 at 14:25
  • 1
    $\begingroup$ Two numbers a,b are relatively prime (or "coprime") iff gcd(a,b)=1, see en.wikipedia.org/wiki/Coprime_integers. $\endgroup$ – Landei Nov 30 '12 at 14:34
  • $\begingroup$ @TimPietzcker: Also, the significance in this context is that if a and b are relatively prime, and both divide c, then their product also divides c for hopefully obvious reasons. $\endgroup$ – camccann Nov 30 '12 at 15:10
  • 1
    $\begingroup$ @TimPietzcker The implication is still valid even if you were using, say, 12 and 35, even though those are not prime - it is enough that they not share any prime factors, which is what "relatively prime" means. $\endgroup$ – Thomas Nov 30 '12 at 15:11

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.