How to calculate the power modulo $990$ without a calculator?

Stumbled upon this problem while studying for my exam in discrete mathematics and I can't figure out how to solve it:

The problem: What is $$73^{1567}\mod\ 990$$ ?

• the result should be $127$ – Dr. Sonnhard Graubner May 23 '17 at 16:42
• Yes, but how do you solve it without a calculator? – Flipman May 23 '17 at 16:43
• We need Euler's theorem and the chinese remainder theorem (See answer below) – Peter May 23 '17 at 16:59

We calculate the power modulo $9,10$ and $11$ and apply the chinese remainder theorem.

$n=9$ is easy because of $73\equiv 1\mod 9$ the result is $1$

$n=10$ leads to $3^3$ , if we reduce the base mod $10$ and the exponent mod $4$

The result is therefore $7$

$n=11$ leads to $7^7$ , if we reduce the base mod $11$ and the exponent mod $10$

It is easy to calculate $7^3$ mod $11$ (result $2$), so $7^6\equiv 4\mod 11$, hence $7^7\equiv 6\mod 11$

So, we have the residues $1,7,6$. The chinese remainder theorem gives $127$. To find this, first look at the numbers congruent $1$ modulo $9$ ; we have $1,10,19,28,37$ Here, we have residue $7$ mod $10$. So, we have residue $37$ modulo $90$. We are lucky that $37+90$ has already the correct residue mod $11$.

use that $$73^{20}\equiv 1\mod 990$$