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.
$\endgroup$ 14 Answers
$\begingroup$$$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.
$\endgroup$ $\begingroup$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); // 31Intermediate 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 | 31Please note that the complexity is $O(\log_2e)$, resulting in $\lceil\log_2164\rceil=8$ iterations.
$\endgroup$ $\begingroup$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} $$
$\endgroup$ $\begingroup$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.
$\endgroup$
