OMITS 2015 summation of mad facorials

Algebra Level 5

Find the remainder when $\sum _{ k=1 }^{ 40 }{ { (k }^{ 3 } } -1)k!$ divided by 97

please submit yours solutioon :D
this problems originally from OMITS 2015

The answer is 6.

1 solution

Pi Han Goh
Feb 2, 2015

Note that $k^3 - 1 = (k+1)(k+2)(k+3) - 6(k+2)(k+1) + 7(k+1) - 2$

Thus, we have

$(k^3 - 1) k!$

$= (k+3)! - 6(k+2)! + 7(k+1)! - 2k!$

$= [ (k+3)! - (k + 2)! ] - 5 [ (k+2)! - (k+1)! ] + 2 [ (k+1)! - k! ]$

This is a Telescoping Series, which gives the value

$\begin{aligned} (43! - 3!) - 5(42! - 2!) + 2(41! - 1!) & = & 43! - 5(42!) + 2(41!) + 2 \\ & = & 41! (2 - 5 * 42 + 43 * 42) + 2 \\ & = & 41!( 16 (97) + 46 ) + 2 \\ \end{aligned}$

Consider Modulo $97$

$\equiv 46(41!) + 2 \equiv \boxed{6}$

The penultimate step involved plenty of tedious arithmetic calculation by pairing as such

$41! = (1 \times 41) \times (2 \times 40) \times (3 \times 39) \times \ldots \times (25 \times 27) \times 26$

I hope there's a simpler solution than mine.

Sir, it seems that mine was 1000 times bigger than your solution! This solution is nice one.

Rudresh Tomar - 6 years, 4 months ago

How did you come up with that way of writing $k^3-1$ ?

Bogdan Simeonov - 6 years, 4 months ago

The first thing that came into mind was telescoping series, because I'm not going to calculate the remainder of 39 different numbers. So I tried to state the expression in terms of $a_{n+1} - a_n$

Pi Han Goh - 6 years, 4 months ago

This is exactly how I did it, and I was wondering if there was an easier way to simplify the last step as well.

Patrick Corn - 6 years, 4 months ago

Yes exactly. I too would write the same.

Kartik Sharma - 6 years, 4 months ago

I didn't understand the last step . Can you please explain ?

Anish Kelkar - 6 years, 4 months ago

I want to evaluate $41! \bmod {97}$ . In order to reduce the calculations, I paired the first term and last term together, second term and second last term together, and so on.

For example $1 \times 41 \equiv 41$ , $2 \times 40 \equiv 80 \equiv -17$ , $3 \times 39 \equiv 30$ , $4 \times 38 \equiv 76 \times 2 \equiv -21 \times 2 \equiv -42$ , $\space \ldots \space$ , $25 \times 27 \equiv 26^2 - 1 \equiv -3$ . Then combine all of them together, and repeat the process to get a single value, which is still very tedious to work with....

Pi Han Goh - 6 years, 4 months ago

However, I can reduce to two possible answers, which are $6$ , $95$ . But only one of them is right.

Here's my work, less tedious, but still...

By Wilson's Theorem

$\begin{aligned} 96! \bmod{97} & \equiv & 11 \\ 41! ( 42 \times 43 \times \ldots \times 96) & \equiv & -1 \\ 41! (-1 \times -2 \times \ldots \times -55) & \equiv & -1 \\ 41! \times 55! & \equiv & 1 \\ 41!^2 (42 \times 43 \times \ldots \times 55) & \equiv & 1, \text{ still plenty of work} \\ 41!^2 \times 11 & \equiv & 1 \\ 41!^2 & \equiv & 53, \text{ by Extended Euclidean Algorithm} \\ & \equiv & 53 + 97(4) \equiv 21^2 \\ \end{aligned}$

Which implies $41! \equiv 21, -21$ , but only one of these values are right.

Pi Han Goh - 6 years, 4 months ago

So that's quite tedious . I thought you were able to do simplification quite easily . Anyway, Thank you very much

Anish Kelkar - 6 years, 4 months ago

OMITS 2015 summation of mad facorials

The answer is 6.

1 solution

0 pending reports