$(3^{34})/55$ find out the reminder

Question

$\cfrac{(3^{34})}{55}$ find out the reminder

My Approach

$3^1$ mod $55$=$3$

$3^2$ mod $55$=$9$

$3^3$ mod $55$=$7$

$3^4$ mod $55$=$6$

and the pattern repeats ..

So,I did $3$^$4$.$8$ +$2$=$3^2$=9 mod $55$=$9$.

Can anyone guide me how to solve the problem?Pleae correct me if I am wrong?

Answer 1

$55=5\cdot11$

$3^2\equiv-1\pmod5\implies3^{34}=(3^2)^{17}\equiv(-1)^{17}$

$\implies3^{34}\equiv-1\pmod5\equiv4\ \ \ \ (1)$

As $(3,11)=1,3^{10}\equiv1\pmod{11}$ and $34\equiv4\pmod{10}$

$\implies3^{34}\equiv3^4\pmod{11}\equiv4\ \ \ \ (2)$

Apply CRT on $(1),(2)$

Otherwise by observation $3^{34}\equiv4\pmod{11\cdot5}$ as $(11,5)=1$

Answer 2

Note that last term of $3^4$ is 1 so applying for $3^{17}$ last digit is 3 so the remainder when divided by 55 is 53 so can you do for 34 using the patterns you have applied for first few powers. Hint $mod(11.5)$ so in general (11,5) has common divisor 1

Answer 3

The Chinese remainder theorem says that we can focus on $\mod{11}$ and $\mod 5$, and stitch together the answers afterwards. Since $5$ and $11$ are prime, we can exploit Fermat's little theorem.

Modulo $5$: Fermat's little theorem gives $3^4\equiv 1$. This implies $3^{32} = 3^{4\cdot 8}\equiv 1$, and therefore $3^{34}\equiv 4\equiv -1\pmod 5$ (i will use whichever seems most handy later).

Modulo $11$: Fermat's little theorem gives $3^{10}\equiv 1$, which implies $3^{30}= 3^{10\cdot 3}\equiv 1$. This gives $3^{34} \equiv 3^4 = 81\equiv 4\pmod{11}$.

Now that that's over with, it's time to use the Chinese remainder theorem to stitch these two together to an answer modulo $55$. But we see tha both modulo $5$ and modulo $11$, $3^{34}\equiv 4$, which makes the job simple: It's still $4\!\!\!\mod{55}$.

Answer 4

we calculate $3^{30}\equiv 34\mod 55$ and $3^4\equiv 26 \mod 55$ thus we get $$3^{34}\equiv 4 \mod 55$$

Answer 5

Using the CRT, as in other answers, is way better than this: but, for the fun of it...

$3$ is prime to $55$, and $\phi(55) = 10 \cdot 4 = 40$. So $ 3^{40} \equiv 1 \pmod{55}$, so $$3^{34} \cdot 3^6 \equiv 1.$$ On the other hand, $$2\cdot 3^3 = 54 \equiv -1.$$
Squaring the previous line and comparing with the line before, one gets $3^{34}\equiv 4$.