# $\left(\sum\limits_{n=1}^{30}n^{61}\right)\pmod{961} \equiv\space?$

What's $$\large\left(\sum\limits_{n=1}^{30}n^{61}\right)\pmod{961} \equiv\space?$$

$$\mathscr{ A)\space404}$$

$$\mathscr{ B)\space434}$$

$$\mathscr{ C)\space465}$$

$$\mathscr{ D)\space496}$$

$$\mathscr{ E)\space527}$$ $$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,}\newcommand{\i}{\mathrm{i}}\newcommand{\text}[1]{\mathrm{#1}}\newcommand{\root}[2][]{^{#2}\sqrt[#1]} \newcommand{\derivative}[3]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\abs}[1]{\left\vert\,{#1}\,\right\vert}\newcommand{\x}[0]{\times}\newcommand{\summ}[3]{\sum^{#2}_{#1}#3}\newcommand{\s}[0]{\space}\newcommand{\i}[0]{\mathrm{i}}\newcommand{\kume}[1]{\mathbb{#1}}\newcommand{\bold}[1]{\textbf{#1}}\newcommand{\italic}[1]{\textit{#1}}\newcommand{\kumedigerBETA}[1]{\rm #1\!#1}$$

What have I tried? I tried to find sum of odd numbers so that I can eliminate odd number or even number choices. Then I realized the mod is odd, so I can't calculate the parity of the sum without using mod. What can I try now?

• Python says $D$, for what it's worth. Sep 9, 2017 at 10:07
• Correct, it's D. Sep 9, 2017 at 10:10

HINT:

$$r^{2m+1}+(31-r)^{2m+1}\equiv\binom{2m+1}131r^{2m}\pmod{31^2}$$

Here $m=30,r^{60}=(r^{30})^2\equiv1\pmod{31}$

$\implies31r^{60}\equiv31\pmod{31^2}$

• Very nice! ${}{}$ Sep 9, 2017 at 10:24
• @JyrkiLahtonen, Thanks. I should made further generalization $$\sum_{n=1}^{p-1}n^{2p-1}\pmod{p^2}$$ OR $$\sum_{n=1}^{p-1}n^{2r+1}\pmod{p^2}$$ for that matter Sep 9, 2017 at 10:27
• May be, may be not? It took me a while to figure out how to use your hint, but I did get there in the end :-) Sep 9, 2017 at 10:30

By Faulhaber's formula, $$S=\sum\limits_{n=1}^{30}n^{61}=\frac{1}{62}(B_{62}(31)-B_{62}(0))=\frac12\sum_{k=2}^{62}{62\choose k}B_{62-k}31^{k-1}.$$ By Von Staudt-Clausen Theorem, we have
$$S\equiv \frac12{62\choose 2}B_{60}\times31\equiv\frac12\frac{62\times61}{2}(-\frac{1}{31})31\equiv\frac{31}{2}\equiv31\times 481\equiv31\times16\equiv 496\pmod{31^2}$$