What is $3^{43} \bmod {33}$? I just took math final and one of the question was 

Find $3^{43}\bmod{33}$.

So, I used Euler's function; $\phi(33)=20$.    
$3^{20}\equiv 1\pmod{\!33}$
By using this fact, I got $27$. 
One thing that I don't understand is that to use Euler's function to find mod, shouldn't we have $\gcd(3,33)=1$? Here $\gcd(3,33)=3\neq 1$, but it gave the right answer.
 A: $3^{43}=3k\ $ for some $k\in\Bbb Z$. FLT - Fermat's little theorem.    
$\bmod 11\!:\:\: 3^{43}\stackrel{\text{FLT}}\equiv 3^{43\!\pmod{\!10}}\!\equiv 3^3\equiv 3k\!\stackrel{:3}\iff\! k\equiv 3^2\equiv 9$.   
$3^{43}=3(11m+9)=33m+27\ $ for some $m\in\Bbb Z$.
A: Carmichael's function, $\lambda(33)= \text{lcm}(\phi(3),\phi(11)) = 10$. So $3^{43} \equiv 3^3 \equiv 27 \bmod 33$.

Essentially this works because we are not looking for $a^{\lambda(q)} \equiv 1$. We are looking for $a^{k+\lambda(q)} \equiv a^k$ which will hold so long as $a^k$ has maximized the exponents of the prime powers that it shares with $q$. Certainly here where $33$ is squarefree we do not need to worry about accumulating prime powers. So $3^{43} \equiv 3^{33} \equiv 3^{23} \equiv 3^{13} \equiv 3^3 \bmod 33$.
A: Yes, to use Euler's theorem, i.e., $a^{\phi(n)} \equiv 1\pmod{n}$, you need $\gcd(a,n)$ to be $1$. Hence, your method is incorrect, though your final answer is correct.
The right way to proceed is as follows.
We have
$$3^{10} \equiv 1 \pmod{11} \implies 3^{43} \equiv 5 \pmod{11}$$
This means
$$3^{43} \equiv 5,16,27\pmod{33}$$
Further, $3$ divides $3^{43}$. Hence,
$$3^{43} \equiv 27\pmod{33}$$
A: As $(3^n,33)=3$ for integer $n\ge1$
let us find $3^{43-1}\pmod{\dfrac{33}3}$ i.e., $3^{42}\pmod{11}$
As $(3,11)=1$ and $\phi(11)=\lambda(11)=11-1=10,3^{10}\equiv1\pmod{11}$
$3^{42}\equiv3^2\cdot1^4\pmod{11}\equiv9$
As $a\equiv b\pmod m\implies a\cdot c\equiv b\cdot c\pmod{m\cdot c}$
$3^{42}\cdot3\equiv9\cdot3\pmod{11\cdot3}$
