Solving $4^{667} ≡ x \pmod{13}$ without Eulers totient theorem or CRT

Question

Does anyone know any efficient ways to solve this without Euler's Totient Theorem or Chinese remainder theorem?

Answer 1

As $5*13=65$ we have

$$4^3 \equiv -1 \pmod{13}$$

Even without this observation, you can calculate $4,4^2, 4^3, ... \pmod{13}$ and since there are only at most 12 posibilities you know that the powers must repeat after at most 12 steps. Find the repeating pattern.

Note: As you calculate, you can make each number in the sequence $4,4^2, 4^3, ... \pmod{13}$ between $0$ and $12$ which makes the computation simpler.

Answer 2

Note $13\times 5 =65$ so $64=4^3\equiv -1 \mod 13$. Then $667=3\times 222+1$, so it is all $4=x\mod 13$, and we're done.