# hard problem of modular arithmetic

Can you show me how to prove this::

$$66^{11 k+66} + 11^{101 k+55}\equiv \left\{\begin{array}{ll} 22 \pmod{165}& \text{if k is odd,}\\ 77 \pmod{165} & \text{if k is even.} \end{array}\right.$$

-

It's $\rm \equiv 0\ (mod\ 11)\:,\:$ and $\rm\: mod\ 15\$ it's $\rm\ 6^n \equiv 6\$ plus $\rm\ (-4)^n \equiv -4,\:1,-4\:, 1\:, \ldots\$ equals $\rm\ 2, 7, 2, 7\:\ldots$

Hence it's $\rm\ 22,77,22,77\:\ldots\ (mod\ 11*15)$

-

First, $66^2 \equiv 66 \pmod{165}$. Therefore $66^{11k+66} \equiv 66 \pmod{165}$. Second, $11^3 \equiv 11 \pmod{165}$. Therefore for even $n > 0$, $11^n \equiv 121 \pmod{165}$, whereas for odd $n > 0$, $11^n \equiv 11 \pmod{165}$. If $n=101k+55$ then $n$ is odd iff $k$ is even. Thus for odd $k$ we get $66+121 \equiv 22 \pmod{165}$, and for even $k$ we get $66+11 \equiv 77 \pmod{165}$.

-
beautiful! – Timothy Wagner Dec 1 '10 at 17:56

Since $165=3\times 5\times 11$, work modulo each of $3$, $5$, and $11$ separately and then combine them using the Chinese Remainder Theorem.

-