What is the remainder of $314^{164}$ divided by 165? 
What is the remainder of $314^{164}$ divided by 165?

Since 165 is not a prime, we cannot apply Fermat's Little Theorem directly. However since $165=3\times 5\times 11$, we could try to divide $314^{164}$ by each of the prime factors and hope things will work out.
After some calculations, I got:
$314^{164}\cong1(\mod 5)$
$314^{164}\cong1(\mod 3)$
$314^{164}\cong9(\mod 11)$
But then I don't see how to continue? A system of linear congruences reminds me of the Chinese Remainder Theorem though.
 A: $$314^{164} \equiv 1 \mod 15$$
$$314^{164} \equiv 9 \mod 11$$
There are just 11 numbers of the form $15a+1$ which are less than 165. Only one of them satisfies the $9 \mod 11$ criteria . That number is 31.
A: Here is a solution that does not make use of Fermat's Little Theorem.

The Algorithm:


*

*Input: $x=314,e=164,n=165$

*Output: $y=1$

*Repeat until $e=0$:


*

*If $e\equiv1\pmod2$ then set $y=yx\bmod{n}$

*Set $x=x^2\bmod{n}$

*Set $e=\left\lfloor\frac{e}{2}\right\rfloor$
C Implementation:
int PowMod(int x,int e,int n)
{
    int y = 1;
    while (e > 0)
    {
        if (e & 1)
            y = (y*x)%n;
        x = (x*x)%n;
        e >>= 1;
    }
    return y;
}

int result = PowMod(314,164,165); // 31

Intermediate Output:
   x   |   e   |   y
-------|-------|-------
   314 |   164 |     1
    91 |    82 |     1
    31 |    41 |     1
   136 |    20 |    31
    16 |    10 |    31
    91 |     5 |    31
    31 |     2 |    16
   136 |     1 |    16
    16 |     0 |    31


Please note that the complexity is $O(\log_2e)$, resulting in $\lceil\log_2164\rceil=8$ iterations.
A: The Chinese remainder theorem also includes a method for reconstructing the corresponding equivalence class mod $3\cdot5\cdot 11$.
We need to compute $15^{-1}\pmod{11}, 55^{-1}\pmod{3}$, and $33^{-1}\pmod{5}$.


*

*$a = 15^{-1}\pmod{11} = 4^{-1} \pmod{11} = 3$

*$b = 55^{-1}\pmod{3} = 1^{-1} \pmod{3} = 1$

*$c = 33^{-1}\pmod{5} = 2^{-1}\pmod{5} = 2$


Now, we examine the following sum:
$$
9\cdot 15 \cdot a
+ 1\cdot 55 \cdot b
+ 1\cdot 33 \cdot c = 405 + 55 + 66 = 526 \equiv 31\pmod{165}
$$
It is clear from the formula and the definition of $a,b,c$ that this will be congruent to $9\pmod{11}, 1\pmod{3}$, and $1\pmod{5}$.
Edit: an alternate method would be to use Euler's theorem, which says that $a^{\phi(165)} = 1 \pmod{165}$ if $(a,165) = 1$, which is true of $a = 314$.  Then $\phi(165) = \phi(3)\phi(5)\phi(11) = 80$, so that
$$
314^{164} = 314^{4} = (-16)^4 = 2^{16} = 65536 \equiv 31 \pmod{165} 
$$
A: Since 314 is relatively prime to 165, we can apply Euler's Theorem. By Euler's Theorem, 314^(phi of 165)≡1(mod 165). Phi of 165=80, therefore, 314^80 are 1(mod 165). 3^160 is also  1(mod 165). Now we have to compute 314^4 (mod 165). 314^4 is equal to 2^4 x 157^4. 2^4=2^4 mod 165. 157≡-8(mod 165), so 157^4≡(-8)^4(mod 165)≡2^12 (mod 165). Thus, we need to find 2^4 x 2^12(mod 165), which is 2^16(mod 165). Some computation gives a quotient of 397 and a remainder of 31.
