# what is the remainder when $1!+2!+3!+4!+\cdots+45!$ is divided by 47?

Can any one please tell the approach or solve the question

what is the remainder when $1!+2!+3!+4!+\cdots+45!$ is divided by $47$?

I can solve remainder of $45!$ divided by $47$ using Wilson's theorem but I don't know what must be the approach for this model problems, as $47$ is a prime number I cannot convert it into another factorial and divide.

If any one of you viewing have any idea regarding the approach, please post your approach here.

Regards, Pavan Kumar

• Possible first hint: $\binom{46}{k}\equiv (-1)^k\pmod {47}$ – Thomas Andrews Jul 10 '13 at 18:48
• Have you tried to calculate this remainder for "smaller values of 47"? I.e., 47 is prime, try to calculate this first for 5, 7, 11, 13, etc. – Álvaro Lozano-Robledo Jul 10 '13 at 18:52
• Hint: Consider the series expansion for $\frac{1}{e}$. By doing this, you can show that $1! + 2! + \cdots + (p-1)!$ is congruent to $\frac{p-1}{e}$ mod $p$ (I forget if you need to round up or down) for arbitrary primes $p$. Now you get what you want from Wilson. – Tobias Kildetoft Jul 10 '13 at 19:19
• But what is $\,e\pmod p\;$ ?? – DonAntonio Jul 10 '13 at 19:29
• @DonAntonio I meant to round before doing the mod (I can see I did not make that very clear). Unfortunately, I wrote that rather hastily because I had to go, and now I can't fill in the details myself (and I seem to have misremembered some of the details, as it does not seem to fit my calculation for small primes). – Tobias Kildetoft Jul 11 '13 at 6:13

Just to compose table:

\begin{array}{|c|r|} \hline n! & \equiv \ldots (\bmod \:47) \\ \hline \\ 1! & 1 \\ 2! & 2\cdot 1 = 2 \\ 3! & 3 \cdot 2 = 6 \\ 4! & 4 \cdot 6 = 24 \\ 5! & 5 \cdot 24 = 120 \equiv 26 \\ 6! & 6 \cdot 26 = 156 \equiv 15 \\ 7! & 7 \cdot 15 = 105 \equiv 11 \\ \cdots \\ 44! & 44 \cdot 8 = 352 \equiv 23 \\ 45! & 45 \cdot 23 = 1035 \equiv 1 \\ \hline \end{array}

$45$ steps/rows in total.

Then to find sum: $S = 1+2+6+24+26+15+11+\ldots+23+1 = \color{#E0E0E0}{1052 \equiv 18 (\bmod \: 47)}$.

Here we use idea:
if $\qquad$ $k! \equiv s (\bmod \: p)$,
then $\;$ $(k+1)! \equiv (k+1)\cdot s (\bmod \: p)$,
and apply it step-by-step.

• What is there in the three dots? All the residues modulo $\;47\;$ but $\,-1\\,$? If yes, why? – DonAntonio Jul 10 '13 at 19:48
• Unless you calculate exactly all the elements $\,k!\pmod {47}\,$ , I can't see how can you know what the sum of the factorials are. Is this calculation what you're proposing to do? – DonAntonio Jul 10 '13 at 20:00
• @DonAntonio:: I think: let author of question calculate all elements $k!(\bmod \: 47)$, and later to add them all. My answer is: grayed "18". It is not so hard: 45 rows in the table, and 45 terms in the sum. – Oleg567 Jul 10 '13 at 20:06
• @DonAntonio, I got your first question :) . No, I don't see any rule/pattern in remainders. $8! \equiv 16! \equiv 29! \equiv 41 \mod 47$; and there are no remainders $3,5,7,9,10, \ldots$. – Oleg567 Jul 10 '13 at 20:33
• Oh, I know it is not hard...but it's terribly annoying and dull! Perhaps this is what the OP wanted to know, but I seriously doubt this will help him if instead $\,47\,$ her had $\,103\,$ or some other bigger prime... – DonAntonio Jul 10 '13 at 20:43

If you write the sum backwards you get

$45! + 44! + 43! + ... + 1! = (((···(45+1)44+1)43+1)···+1)2+1$

This creates the sequence

$t_0 = 45, \quad t_{n+1} = (t_n+1)(t_0-n)$

where we wish to find the value of $t_{44}$

This will take $44$ multiplications and $88$ additions, which seems pretty efficient.

Doing the arithmetic modulo $47$, I got $t_{44} \equiv 18 \pmod{47}$.

 n  t[n]     n  t[n]     n  t[n]     n  t[n]     n  t[n]
0    45     9    44    18    38    27    46    36    18
1     3    10    24    19    27    28     0    37    11
2    31    11     4    20    42    29    16    38    37
3    28    12    24    21    45    30    20    39    40
4    14    13     1    22    24    31    12    40    17
5    36    14    15    23    33    32    28    41    25
6    33    15    10    24     9    33    19    42    31
7    23    16    37    25    12    34    32    43    17
8    42    17    30    26    12    35     1    44    18