What is $3^{43} \bmod {33}$?

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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