Chinese Remainder Theorem - Simplifying

Question

I have $mp = 156^{107} \pmod{17},\;$ which simplifies to $3^{11} \pmod{17}.$

How did he get the $11$?

Same for

$mq = 156^{107} \pmod {11},\;$ which simplifies to $2^7 \pmod {11}.$

How to get the $7$? I know how to get the $3$ and $2$

Answer 1

Hint: The Euler's Theorem states that: If $a$ and $m$ are coprime then $a^{\varphi(m)} = 1 \pmod{m}$, $\varphi(\cdot)$ is Euler's totient function. So, $3^{16}=1 \pmod{17}$ and $107=16\cdot 9 + 11$.

Update: Actually, since $17$ is prime, we could refer to the Fermat's little theorem.

Answer 2

I'd add that one deduces at once from Euler's theorem that, if $a$ and $m$ are coprime, $$a^{N}\equiv a^{N\bmod \varphi(m)}\mod m.$$ In particular, if $m$ is prime, $\varphi(m)=m-1$.