Merlin, who has unbounded computational resources, wants to convince Arthur that $$m|\sum_{p\le N,\ p\text{ prime}}p^k$$ for $(N,m,k)$ with $k=O(\log N)$ and $m=O(N).$ Computing this sum in the straightforward way (modular exponentiation and addition) takes time $N(\log\log N)^{2+o(1)}$ with FFT-based multiplication.* But Arthur can only perform $O(N)$ operations.
(Notation, for compatibility with earlier versions of this question: Let the sum equal $m\alpha$; then the question is whether $\alpha$ is an integer.)
Can Merlin convince Arthur with a string of length $O(N)$? If not, can he convince Arthur with an interactive proof (total communication, of course, must be $O(N)$)? If so, could Merlin use a string of length $o(N)$? Could Arthur use $o(N)$ time?
Arthur has no access to nondeterminism or other special tools (quantum methods, oracles other than Merlin, etc.) but has $O(N)$ space if needed. Of course Arthur need not compute the sum directly, he merely needs to be convinced that a given triple (N, m, k) makes the equation true or false.
Note that with $k=0$ it is possible to compute the sum in time $O(N^{1/2+\varepsilon})$ using the Lagarias-Odlyzko method. For $k>0$ the sum is superlinear and so cannot be stored directly (without, e.g., modular reduction) but it's not clear whether a fast algorithm exists.
I would also be interested in any algorithm to calculate the sum (modular or otherwise) other than by direct powering and addition.
* $N/\log N$ numbers to calculate, time $\lg k\log N(\log\log N)^{1+o(1)}=\log N(\log\log N)^{2+o(1)}$ for each calculation.