1
$\begingroup$

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

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

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.