# SOLVEDCongruence of factorials when the mod isn't 10 or 15

#### dwsmith

MHF Hall of Honor
$$\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)}$$

#### undefined

MHF Hall of Honor
$$\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.

dwsmith

#### dwsmith

MHF Hall of Honor
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.

#### undefined

MHF Hall of Honor
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

#### roninpro

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?