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

dwsmith

MHF Hall of Honor
Mar 2010
3,093
582
Florida
\(\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
Mar 2010
2,340
821
Chicago
\(\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.
 
  • Like
Reactions: dwsmith

dwsmith

MHF Hall of Honor
Mar 2010
3,093
582
Florida
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
Mar 2010
2,340
821
Chicago
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
 
Nov 2009
485
184
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?