Calculate $100^{1207} \mod 63$

Question

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

Answer 1

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

Answer 2

Note that $$100^3\equiv 1 \mod 63$$

Answer 3

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.

Answer 4

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

Answer 5

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

Answer 6

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$