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.

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

share|improve this question
2  
$18!+1$ does not divide $437$; do you mean that $437$ divides $18!+1$? –  Brian M. Scott Nov 30 '12 at 7:15
    
thanks for the correction. –  Phani Raj Nov 30 '12 at 7:17
    
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. –  Phani Raj Nov 30 '12 at 7:18
add comment

2 Answers

up vote 32 down vote accepted

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.

share|improve this answer
    
Could you explain "relatively prime" in this context? 19 and 23 are prime - what's relative about that? –  Tim Pietzcker Nov 30 '12 at 14:25
    
Two numbers a,b are relatively prime (or "coprime") iff gcd(a,b)=1, see en.wikipedia.org/wiki/Coprime_integers. –  Landei Nov 30 '12 at 14:34
    
@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. –  camccann Nov 30 '12 at 15:10
1  
@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. –  Thomas Nov 30 '12 at 15:11
add comment

That's not so big numbers. This is a demonstration: 18! + 1 = 6402373705728001 = 14650740745373 * 437

Of course that's not as interesting as André's one.

share|improve this answer
2  
The OP was asking to solve it without calculation $18!$. –  martini Nov 30 '12 at 9:55
add comment

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.