I am trying to calculate $a^8 \bmod 15$ for $a = 1,2,\dots,14$
I get that because $a = 2,4,7,8,11,13,14$ are relatively prime to $15$, the answer will be $1$ in those cases. But how to get this for the other values of $a$?
I am trying to calculate $a^8 \bmod 15$ for $a = 1,2,\dots,14$
I get that because $a = 2,4,7,8,11,13,14$ are relatively prime to $15$, the answer will be $1$ in those cases. But how to get this for the other values of $a$?
This is essentially the same as Bill Dubuque's answer but with more words than symbols.
Since $8$ is a multiple of $3-1$, you know $a^8$ is $0$ or $1 (\rm{mod}\ 3)$ depending on whether $a$ is a multiple of $3$ or not. Similarly since $8$ is a multiple of $5-1$, you know $a^8$ is $0$ or $1 (\rm{mod}\ 5)$ depending on whether $a$ is a multiple of $5$ or not. So you have four cases:
If $a$ is both a multiple of $3$ and of $5$ then you want an answer which is $0 (\rm{mod}\ 3)$ and $0 (\rm{mod}\ 5)$. So $0$ is the obvious solution.
If $a$ is not a multiple of $3$ nor of $5$ then you want an answer which is $1 (\rm{mod}\ 3)$ and $1 (\rm{mod}\ 5)$. So $1$ is the obvious solution.
If $a$ is a multiple of $3$ but not of $5$ then you want an answer which is $0 (\rm{mod}\ 3)$ and $1 (\rm{mod}\ 5)$. So $6$ is the solution.
If $a$ is not a multiple of $3$ but is of $5$ then you want an answer which is $1 (\rm{mod}\ 3)$ and $0 (\rm{mod}\ 5)$. So $10$ is the solution.
Hint $\ $ Using CRT, work in parallel mod $3$ and mod $5$, then pullback to mod $15$.
Note $\rm\ mod\ (3,5)\!:\ \ (3n)^8 \equiv (0,1),\ \ (5m)^8\equiv (1,0)\ \ $ if $\rm\ \ 3n,5m\not\equiv 0\ (mod\ 15)$
i.e. $\rm\ \ mod\ 3\!:\ (3n)^8\equiv 0^8\equiv 0.\ \ \ mod\ 5\!:\ (3n)^8\equiv ((3n)^2)^4\equiv 1\ $ if $\rm\:5\nmid n,\:$ i.e. $\rm\:15\nmid 3n$
Now $\rm\: n\equiv (0,1)\ mod\ (3,5)\iff n\equiv\: 6\:\ mod\ 15$
and $\rm\ \ \:\! n\equiv (1,0)\ mod\ (3,5)\iff n\equiv 10\ mod\ 15$
This is better viewed via $\:\mathbb Z/15\:\cong\:\mathbb Z/3\times \mathbb Z/5,\:$ which proves instructive to make explicit if you have knowledge of this structural view of CRT (Chinese remainder).