Find the smallest positive prime divisor of ...

Question

Problem:

That's a problem I have found on the web. I didn't understand the solution: Why??

Given solution:

How all this sequence has been transformed into $$33-{\lfloor {33\over p}\rfloor} \mod p$$

Thank you

Answer 1

If $p\nmid a$ then $a^{p-1}\equiv 1\pmod p$. This is Fermat's little theorem. Therefore $a^{(p-1)m}\equiv1\pmod p$. So, if $(p-1)\mid 60$ and $p\nmid a$ then $a^{60}\equiv1\pmod p$. This is true for $p\in\{ 2,3,5,7,11,13,31,61\}$. Of course $a^{60}\equiv1\pmod p$ if $p\nmid a$.

If $p\le 13$ then $\sum_{a=1}^N a^{60}\equiv t\pmod p$ where $t$ is the number of non-multiples of $p$ in $\{1,2,\ldots,N\}$.