# What is the remainder of $16!$ is divided by 19?

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

Thanks,
Chan

-

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.)

-
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

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

-
@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
@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

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$...)

-