18
$\begingroup$

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!\,\,?$

$\endgroup$
3
  • 4
    $\begingroup$ $18!+1$ does not divide $437$; do you mean that $437$ divides $18!+1$? $\endgroup$ Nov 30, 2012 at 7:15
  • $\begingroup$ thanks for the correction. $\endgroup$
    – Phani Raj
    Nov 30, 2012 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, 2012 at 7:18

1 Answer 1

43
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Could you explain "relatively prime" in this context? 19 and 23 are prime - what's relative about that? $\endgroup$ Nov 30, 2012 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, 2012 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, 2012 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, 2012 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.