Calculate $a^8 \bmod 15$ for $a = 1,2,\dots,14$

Question

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$?

Answer 1

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.

Answer 2

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).