Calculate $100^{1207} \mod 63$ I try to solve this question: Calculate $100^{1207} \mod 63$. There is the hint that i should calculate $100^{1207} \mod 7$, $100^{1207} \mod 9$, which is easy for me, but I don't see the relationship between this to questions. I guess it must have something to do with the fact, that $7*9 = 63$.
 A: Note that $$100^3\equiv 1 \mod 63$$
A: Well, its the Chinese remainder theorem:
$$x\equiv a \mod 7\quad \text{and}\quad x\equiv b \mod 9,\quad a,b\in{\Bbb Z}.$$
The solution is unique in the range of $0\leq x\leq 63-1$.
A: First note that $100$ and $63$ are coprime, and that $\phi(63)=\phi(3^2)\phi(7)=6^2$.
So 
$$100^{1207}=4^{1207}\,25^{1207}\equiv 4^{1207\bmod 36}\,25^{1207\bmod36}=4^{19}\,25^{19}\mod 63.$$
On the other hand, $4$ has order 3$\bmod 63$, so
$$4^{19}\,25^{19}\equiv  4\cdot5^{38}\equiv4\cdot5^{38\bmod 36}=4\cdot5^2\mod 63.$$
A: The Chinese remainder theorem tells us that if we know a number $x$ modulo $7$ and 
modulo $9$ we also know $x$ modulo $7\times 9 = 63$ because $7$ and $9$ are coprime. It even gives a formula to compute this $x$ modulo $63$, given these other two.
A: It certainly has to do with the fact that $7*9=64$ and also with the fact that the greatest common divisor of 7 and 9 is 1 (they are coprime). As explained by others, the Chinese Remainder Theorem can help solving this problem. It states the following:
Chinese Remainder Theorem

Let $m_1, ..., m_n$ be pairwise coprime ($gcd(m_i, m_j) = 1$ when $i
> \neq j$). Then the system of $n$ equations
$$x \equiv a_1 \mod{m_1}\\    ... \\ x \equiv a_n \mod{m_n}$$
has a unique solution for $x$ modulo $M$ where $M = m_1\dotsm m_n$.

So for this particular problem you can find $a_1$ and $a_2$ for $m_1 = 7$ and $m_2 = 9$ and then look for an $0 < x < 63$ that satisfies the equations for $m_1$ and $m_2$. Here are several methods you can use for this (Search by sieving might be the best for this case).
A completely different solution might use the fact that $100^3 \equiv 1\mod{63}$.
A: Using http://mathworld.wolfram.com/CarmichaelFunction.html, $$\lambda(63)=6$$
and $(100,63)=1$ and $1207\equiv1\pmod6$
$\implies100^{1207}\equiv100^1\pmod{63}\equiv?$
More generally,
$a^n\equiv a^{n\pmod6}\pmod{63}$ for $(a,63)=1$
