Find $x$ in $1!+2!+\ldots+100!\equiv x \pmod{19}$

Question

Here I come from one more (probably again failed) exam. We never did congruence with factorials; there were 3 of 6 problems we never worked on in class and they don't appear anywhere in scripts or advised literature.

First is this one:

Find $x$ in $1!+2!+\ldots+100! \equiv x \pmod {19}$

I got that every $x$ after $19!$ is $0$.

But I am left with $1!+2!+\ldots+18!$, and my calculator can't calculate $18!$ without exponential, so there must be some simpler way, but I have never learned that.

Answer 1

If $n\geq 19$, obviously $n!\equiv 0\pmod{19}$, so it is enough to compute: $$ \sum_{n=1}^{18} n!\pmod{19}.$$ Moreover, by Wilson's theorem we have $18!\equiv -1\pmod{19}$ and $9!\equiv -1\pmod{19}$ since $-1$ is not a quadratic residue $\!\!\pmod{19}$.

Let we fill a simple table: $$ \begin{array}{|c|c|}\hline n & 1 & 2 & 3 & 4 &5 &6 & 7 & 8 & 9 \\\hline n!\pmod{19} & 1 & 2 & 6 & 5 & 6 & 17 & 5 & 2 & 18\\\hline\end{array}$$ that gives $\sum_{n=1}^{9}n!\equiv 5\pmod{19}$. By exploiting $9!\equiv -1\pmod{19}$, we also have
$\sum_{n=10}^{18}n!\equiv 3\pmod{19}$, hence: $$ \sum_{n=1}^{100}n! \equiv\color{red}{8}\pmod{19}.$$

Answer 2

$18! \equiv -1 \pmod{19}$ by Wilson's Theorem. Then you can find the modular inverse of $18$ modulo $19$, multiply both sides by it and you will get $17! \equiv 1 \pmod{19}$. You can continue simularly for the big numbers that are left.

Also you can go step by step in the multiplication. For example for $13!$ you can start:

$$13! \equiv 1 \cdot 2 \cdot ... \cdot 13 \equiv 2 \cdot 3 \cdot ... \cdot 13 \equiv 6 \cdot 4 \cdot ... \cdot 13 \equiv 5 \cdot 5 \cdot ... \cdot 13 \equiv 6 \cdot 6 \cdot ... \cdot 13 \equiv 17 \cdot 7 \cdot ... \cdot 13 $$ $$\equiv 5 \cdot 8 \cdot ... \cdot 13 \equiv 2 \cdot 9 \cdot ... \cdot 13 \equiv 1 \cdot 10 \cdot ... \cdot 13$$ $$ \equiv 10 \cdot 11 \cdot 12 \cdot 13 \equiv 15 \cdot 12 \cdot 13 \equiv 9 \cdot 13 \equiv 3 \pmod {19}$$