Finding $m^2, m^3, m^4, m^7, (m^3)^7$ modulo 33

Question

I'm trying to find the values of $m^2, m^3, m^4, m^7, (m^3)^7$ modulo 33, for $m$ in $\{0,\dots, 16\}$ and for the values in $\{-16,\dots,0\dots, 16\}$. I'm not entirely sure how to proceed although I do know that I probably have to apply Fermat's Little Theorem in some way (i.e. $m^{32} \equiv 1$ mod 33, $m^{33} \equiv m$ mod 33).

Answer 1

$16^2=32*8=-1*8=25$ mod $33$

$16^3=25*16=50*8=17*8=34*4=1*4$ mod $33$

$16^4=4*16=2*32=-1*2=31$ mod 33

$16^7=16^4*16^3=16^4*4=16^2*32*32=16^2=25$ mod 33

$(16^3)^7=(4)^7=16^3*4=4*4=16$ mod 33

and so on..

You can not use Fermat because 33 is not prime.

Answer 2

As well as the hint... lonza leggiera gave in the comments, here are a few more ways to decrease the work:

• Note $(-x)^{2y}\equiv x^{2y}$, and $(-x)^{2y+1}\equiv-(x)^{2y+1}$.

This allows a rough cutting in half the work needed to calculate the latter ( it's basically negation or not on the first set). This works in any modular arithmetic, because if not, it would defy the normal arithmetic rules:$(-x)^{2y}= x^{2y}$, and $(-x)^{2y+1}= -(x)^{2y+1}$. Thus proving them incorrect.

EDIT: You can Also use Fermat but using prime factorization, Mod 3 they reduce to:

1,m,1,m,and m

if m is coprime to 3. Mod 11 The last can be reduced to m. Using CRT we can piece these together, to get the last is always equal to m mod 33. We have now reduced it to the cases mod 11 and CRT.