$(1^n+2^n+3^n+4^n)\mod5$ and using euler totient function to solve this

Question

The problem gives us an integer $n$ which can be extremely large (can exceed any integer type of your programming language) and we need to calculate the value of the given expression .

$$(1^n+2^n+3^n+4^n)\mod5$$

I came across this solution but couldn't get any of its steps so , I understand $a^{\phi(n)}=1 \mod n $

at the end according to solution we just need to check

if( n%4==0 )
        printf("4");
    else
        printf("0");

Answer 1

$\phi(5)=4$ and $m^{4} \equiv 1 \pmod 5$ for $m \in \{1,2,3,4\}$

so $m^{4a+b} \equiv m^b \pmod 5$ for $m \in \{1,2,3,4\}$

so $1^{4a+b} +2^{4a+b} +3^{4a+b} +4^{4a+b} \equiv 1^{b} +2^{b} +3^{b} +4^{b} \pmod 5$

so you only need to check $1^{b} +2^{b} +3^{b} +4^{b} \pmod 5$ for small $b$, and this does indeed give $0,0,0,4,\ldots$ for $b=1,2,3,4,\ldots$ with the pattern repeating

Answer 2

The first point of confusion is that $n$ seems to be used for $2$ different things. Those $\phi(n)$'s should be replaced by $\phi(5)$. As for why the exponents are simply $n\mod4$, we have

$$a^n=a^{4q+r}=(a^4)^qa^r$$

Since $a^4\equiv 1\pmod5$, we have $a^n\equiv a^r\pmod5$ where $n\equiv r\pmod4$. All that remains are to check the four possible cases. If $n$ is a multiple of $4$, each term is equivalent to $1$ for an answer of $4$. If $n$ is odd, $1^n+4^n\equiv1^n+(-1)^n\equiv 1^n-1^n\equiv0\pmod5$. The last case to check is $n\equiv2\pmod4$. Since all squares are equivalent to $\pm1\pmod5$, this is equivalent to $2(1)+2(-1)\equiv0\pmod5$.