Make a table showing the values of $a, a^2, a^3, a^4, a^7, (a^3)^7$ modulo 33 for 0 ≤ a ≤ 16, expressing the entries as integers in the interval [−16, 16]. Explain why two of the columns are the same.
I understand this question involves those two theorems but I don't know where to begin. Do I use Euler's totient function on each of the powers and find what each a is congruent to in mod 33?
Euler's theorem states $$a^{\varphi(n)}\equiv 1\mod n$$ for $(a,n)=1$. For $n=33$ we hence have $$a^{20}\equiv 1\mod 33$$ for $(a,n)=1$ , which implies $(a^3)^7=a^{21}\equiv a\mod 33$
It remains to show that $a^{21}\equiv a\mod 33$ is true as well for $a$ not coprime to $33$.
If $a$ is divisible by $3$ , but not $11$ , we get $a^{10}\equiv 1\mod 11$ (This time Fermat's little theorem) , implying $a^{21}\equiv a\mod 11$. Because of $a^{21}\equiv a\mod 3$ and the chinese remainder theorem, we get $a^{21}\equiv a\mod 33$
If $a$ is divisible by $11$ , but not $3$, we get $a^2\equiv 1\mod 3$ implying $a^{21}\equiv a\mod 3$. Analogue to the first case, we get $a^{21}\equiv a\mod 33$.
Finally, if $a$ is divisible by both $3$ and $11$ , we get $a\equiv 0\mod 33$ immediately implying $a^{21}\equiv a\mod 33$
Hence, the first and last column must coincide.