I want to evaluate $\sum_{i=1}^{n} (x+i)^4$ So what i did is, after expanding it i reduce it to following form
$ x^{4} * n + 4 x^{3} * \sum_{i=1}^{n}i + 6x^2\sum_{i=1}^{n}i^{2} + 4x*\sum_{i=1}^{n}i^{3} + \sum_{i=1}^{n}i^4$
After doing this problem reduced to find $\sum_{i=1}^n i^a$ for $1\le a\le4$ .
This can be easily solved if $\sum_{i=1}^{n}i^4 = (n*(n+1)*(2n+1)*(3n^2 +3*n-1))/30 $ can be computed mod M ( M is not prime).
I know 30 = 6*5, so 6 will get canceled by n or (n+1) or (2n+1). Now for 5 there are 4 cases
1) n%5==1 then 3n^2+3n-1 is divisible by 5
2) n%5 = 2 then (2n+1) will help to cancel 5
3) n%5= 3 then 3n^2+3n-1 is divisible by 5 I
4) n%5 = 4 then n+1 will help to cancel 5.
I am not able to come up with solution when case 1 or case 3 appears. Basically i dont want to compute n^2, can anybody help me to arrive at solution