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.

Can anyone share me the trick to solve this problem using congruence?

Thanks,
Chan

share|improve this question
add comment

3 Answers

up vote 5 down vote accepted

If you've seen Wilson's theorem then you know the remainder when $18!$ is divided by $19$. To get $16!$ mod $19$, then, you can multiply by the multiplicative inverses of $17$ and $18$ mod $19$. Do you know how to find these? (Edit: Referring to both inverses might be a bit misleading, because you really only need to invert their product. See also Bill Dubuque's answer.)

share|improve this answer
    
I knew Wilson's Theorem, but really don't know how to find the inverse of 17, 18 mod 19. What's the inverse? Can you give me one example? Thanks. –  Chan Feb 26 '11 at 6:17
    
@Chan: $\rm 17 \equiv -2,\ 18\equiv -1 $ –  Bill Dubuque Feb 26 '11 at 6:21
    
@Chan: A general technique to find the inverse of $k$ mod $n$ when $k$ and $n$ are relatively prime is to use integer division and the Euclidean algorithm to find $a$ and $b$ such that $ak + bn = 1$. Since $bn$ is a multiple of $n$, $ak$ is congruent to $1$ mod $n$, and thus the congruence class of $a$ is the inverse of the congruence class of $k$. In this particular case, a further hint to make things easier is that $18\equiv -1$ and $17\equiv -2$ mod $19$. (This makes computations easier for inverting their product.) –  Jonas Meyer Feb 26 '11 at 6:21
    
Many thanks, I got it now ;) –  Chan Feb 26 '11 at 6:24
add comment

HINT $\ $ By Wilson's theorem $\ $ mod $19\::\ -1 \ \equiv\ 18\:!\ \equiv\ 18\cdot17\cdot 16\:!\ \equiv\ (-1)\ (-2)\cdot 16\:! $

Similarly we have the Wilson reflection formula $\rm\displaystyle\ (p-1-k)\:!\ \equiv\ \frac{(-1)^{k+1}}{k!}\ \ (mod\ p)\:,\ $ $\rm\:p\:$ prime

share|improve this answer
    
@Bill Dubuque: Thank you! –  Chan Feb 26 '11 at 6:24
    
@Bill Dubuque: If I have $2.16! \equiv 18 \pmod{19}$. Can I cancel out the $2$ from both sides? –  Chan Feb 26 '11 at 6:42
2  
@Chan: $\rm\ 2\:x\equiv 2\:y\ (mod\ 19)\ \iff\ 19\ |\ 2\ (x-y)\ \iff\ 19\ |\ x-y\ \iff\ x\equiv y\ (mod\ 19) $ –  Bill Dubuque Feb 26 '11 at 6:50
    
@Bill Dubuque: Thank you. So if $gcd(a, p) = 1$, then $ax \equiv ay \pmod{p} \implies x \equiv y \pmod{p}$, right? –  Chan Feb 26 '11 at 7:07
    
@Chan: $\rm\ n,m\ $ coprime $\rm\iff a\ n + b\ m = 1\ $ for some $\rm\:a,b\:\ \iff\ a\ n\equiv 1\ (mod\ m)\:,\:$ for some $\rm\:a\:$ $\rm\iff\ n $ is invertible/cancellable $\rm\:(mod\ m)$ –  Bill Dubuque Feb 26 '11 at 7:12
show 2 more comments

I almost think in this case it is just faster to break it down than calculate the inverses: First the factors between 1 and 10:

$$10!= (2\cdot 10)\cdot (4\cdot5)\cdot(3\cdot6)\cdot(7\cdot8)\cdot 9\equiv 1\cdot 1\cdot (-1)\cdot(-1)\cdot 9\equiv9$$

Now we have

$$16!\equiv 9\cdot 11\cdot 12\cdot 13\cdot 14\cdot 15\cdot 16\equiv9\cdot(-8)\cdot(-7)\cdot(-6)\cdot(-5)\cdot(-4)\cdot(-3)$$

$$\equiv 9\cdot(4\cdot5)\cdot(6\cdot3)\cdot(7\cdot8)\equiv 9\cdot(1)\cdot(-1)\cdot(-1)\equiv 9$$

Of course this doesn't generalize, but the computation is faster than finding 3 inverses and multiplying them. (Again of course that is not true for larger $n$...)

share|improve this answer
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.