19
$\begingroup$

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.

Thanks in advance.

Regards, Pavan Kumar

$\endgroup$
  • $\begingroup$ Possible first hint: $\binom{46}{k}\equiv (-1)^k\pmod {47}$ $\endgroup$ – Thomas Andrews Jul 10 '13 at 18:48
  • 1
    $\begingroup$ 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. $\endgroup$ – Álvaro Lozano-Robledo Jul 10 '13 at 18:52
  • 1
    $\begingroup$ 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. $\endgroup$ – Tobias Kildetoft Jul 10 '13 at 19:19
  • 2
    $\begingroup$ But what is $\,e\pmod p\;$ ?? $\endgroup$ – DonAntonio Jul 10 '13 at 19:29
  • 1
    $\begingroup$ @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). $\endgroup$ – Tobias Kildetoft Jul 11 '13 at 6:13
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What is there in the three dots? All the residues modulo $\;47\;$ but $\,-1\\,$? If yes, why? $\endgroup$ – DonAntonio Jul 10 '13 at 19:48
  • 2
    $\begingroup$ 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? $\endgroup$ – DonAntonio Jul 10 '13 at 20:00
  • $\begingroup$ @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. $\endgroup$ – Oleg567 Jul 10 '13 at 20:06
  • $\begingroup$ @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$. $\endgroup$ – Oleg567 Jul 10 '13 at 20:33
  • $\begingroup$ 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... $\endgroup$ – DonAntonio Jul 10 '13 at 20:43
2
$\begingroup$

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
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.