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

Question

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.

Answer 1

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

Answer 2

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

1. $a = 15^{-1}\pmod{11} = 4^{-1} \pmod{11} = 3$
2. $b = 55^{-1}\pmod{3} = 1^{-1} \pmod{3} = 1$
3. $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} $$

Answer 3

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.

Answer 4

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.