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!\,\,?$
$\begingroup$
$\endgroup$
-
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
$\begingroup$
$\endgroup$
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.
answered Nov 30 '12 at 7:18
-
$\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,bare relatively prime (or "coprime") iffgcd(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
aandbare relatively prime, and both dividec, then their product also dividescfor 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
