4
$\begingroup$

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

Thanks,
Chan

$\endgroup$
5
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Chan
    Feb 26 '11 at 6:17
  • $\begingroup$ @Chan: $\rm 17 \equiv -2,\ 18\equiv -1 $ $\endgroup$ Feb 26 '11 at 6:21
  • $\begingroup$ @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.) $\endgroup$ Feb 26 '11 at 6:21
  • $\begingroup$ Many thanks, I got it now ;) $\endgroup$
    – Chan
    Feb 26 '11 at 6:24
3
$\begingroup$

Hint $ $ By Wilson's theorem $\bmod 19\!:\ \overbrace{{-}1}^{\large \color{#0a0}{18}} \equiv 18! \equiv\!\! \overbrace{18\cdot17}^{\large \color{#c00}{(-1)(-2)}}\!\!\cdot 16!\,$ $\Rightarrow\,16!\equiv \dfrac{\color{#0a0}{18}}{\color{#c00}2}\equiv 9$

Generally (Wilson reflection formula) $\rm\displaystyle\ (p\!-\!1\!-\!k)!\equiv\frac{(-1)^{k+1}}{k!}\!\!\!\pmod{\!p},\,$ $\rm\:p\:$ prime

$\endgroup$
8
  • $\begingroup$ @Bill Dubuque: Thank you! $\endgroup$
    – Chan
    Feb 26 '11 at 6:24
  • $\begingroup$ @Bill Dubuque: If I have $2.16! \equiv 18 \pmod{19}$. Can I cancel out the $2$ from both sides? $\endgroup$
    – Chan
    Feb 26 '11 at 6:42
  • 2
    $\begingroup$ @Chan: $\rm\ 2\:x\equiv 2\:y\ (mod\ 19)\ \iff\ 19\ |\ 2\ (x-y)\ \iff\ 19\ |\ x-y\ \iff\ x\equiv y\ (mod\ 19) $ $\endgroup$ Feb 26 '11 at 6:50
  • $\begingroup$ @Bill Dubuque: Thank you. So if $gcd(a, p) = 1$, then $ax \equiv ay \pmod{p} \implies x \equiv y \pmod{p}$, right? $\endgroup$
    – Chan
    Feb 26 '11 at 7:07
  • $\begingroup$ @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)$ $\endgroup$ Feb 26 '11 at 7:12
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

A more explicit answer would go like this:

By Wilson's Theorem, $18!$ is congruent to $-1 \pmod {19}$

$$18! = (18\cdot 17)(16!)$$

Then $(18\cdot 17)(16!)$ is congruent to $-1 \pmod{19}$

But note that $18$ is congruent to $-1 \pmod{19}$ and $17$ is congruent to $-2 \pmod{19}$

Then it follows that $(18\cdot 17)(16!)$ is congruent to $((-1)\cdot (-2))(16!)$ is congruent to $-1 \pmod{19}$

Simplifying, we get, $2\cdot(16!)$ is congruent to $-1 \pmod{19}$. But we need the remainder of $16!$, not $2\cdot 16!$. and $-\frac12$ isn't a valid answer.

Then also notice that $18$ is congruent to $-1 \pmod{19}$. Then $2\cdot 16!$ is congruent to $18 \pmod{19}$ by the fact that if $a$ is congruent to $b \pmod{p}$, then $b$ is congruent to $a \pmod{p}$

So we have that $2\cdot 16!$ is congruent to $18 \pmod{19}$ and from there, its just a matter of dividing both sides by $2$ to get $16!$ is congruent to $9 \pmod{19}$

$\endgroup$

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.