Congruence of factorials when the mod isn't 10 or 15

$\displaystyle 1!+2!+\dots +1000!\equiv x \ \mbox{(mod 11)}$

When $\displaystyle k\geq 11, k!\equiv 0 \ \mbox{(mod 11)}$

Since we are adding up to 11!, can this be done without $\displaystyle \sum_{i=1}^{10}k!$ individual?

$\displaystyle 1!+2!+\dots +10!\equiv x \ \mbox{(mod 11)}$

Quote:

---

Originally Posted by dwsmith

$\displaystyle 1!+2!+\dots +1000!\equiv x \ \mbox{(mod 11)}$

When $\displaystyle k\geq 11, k!\equiv 0 \ \mbox{(mod 11)}$

Since we are adding up to 11!, can this be done without $\displaystyle \sum_{i=1}^{10}k!$ individual?

$\displaystyle 1!+2!+\dots +10!\equiv x \ \mbox{(mod 11)}$

---

Well you can reduce mod 11 each time you multiply. So

1 $\displaystyle \equiv$ 1 mod 11
2 * 1 $\displaystyle \equiv$ 2 mod 11
3 * 2 $\displaystyle \equiv$ 6 mod 11
4 * 6 $\displaystyle \equiv$ 24 $\displaystyle \equiv$ 2 mod 11
5 * 2 $\displaystyle \equiv$ 10 mod 11
6 * 10 $\displaystyle \equiv$ 60 $\displaystyle \equiv$ 5 mod 11
7 * 5 ... etc.

Quote:

---

Originally Posted by undefined

Well you can reduce mod 11 each time you multiply. So

1 $\displaystyle \equiv$ 1 mod 11
2 * 1 $\displaystyle \equiv$ 2 mod 11
3 * 2 $\displaystyle \equiv$ 6 mod 11
4 * 6 $\displaystyle \equiv$ 24 $\displaystyle \equiv$ 2 mod 11
5 * 2 $\displaystyle \equiv$ 10 mod 11
6 * 10 $\displaystyle \equiv$ 60 $\displaystyle \equiv$ 5 mod 11
7 * 5 ... etc.

---

So there is no shortcut method of doing this type then? I just have to either add them or do them one at a time and then add the residuals, then.

Quote:

---

Originally Posted by dwsmith

So there is no shortcut method of doing this type then? I just have to either add them or do them one at a time and then add the residuals, then.

---

Have a computer do it for you? I don't know of any shortcut or formula beyond what I shared, although one might exist.

PARI/GP is a great CAS for number theory.

Code:

---

sum(i=1,10,i!%11)%11

---

You might be able to use Wilson's Theorem:

$\displaystyle (n-1)!\equiv -1\pmod{n}$ if and only if $\displaystyle n$ is prime.

In this case, you have $\displaystyle (11-1)!=10!\equiv -1\pmod{11}$. You can use this fact to get $\displaystyle 9!$ by multiplying by $\displaystyle 10^{-1}$ on both sides. You can get $\displaystyle 8!$ by multiplying by $\displaystyle 9^{-1}$ after that, and etc...

This method may not really save much time though - you still need to compute modular inverses and peel off terms in the factorial, one by one. Is it really so bad to compute the factorials by hand?