1
$\begingroup$

Find a number $0 \leq a < 73$ with $a≡9^{794}\mod 73$.

I know that $a$ and $73$ are relatively prime and $a^{72}≡1 \mod73$. But I couldn't use the theorem.

Can someone help me please?

$\endgroup$
  • 1
    $\begingroup$ Don't focus on powers of $a$. You're not asked to calculate powers of $a$. You're asked to calculate powers of $9$, in a very roundabout way. $\endgroup$ – Arthur May 26 at 14:37
  • $\begingroup$ Just use the theorem. $73$ is prime so $9$ is relatively prime to $73$ so $9^{72}\equiv 1\pmod {73}$. And If $9^{72}\equiv 1 \pmod {73}$ then $9^{72*11 + 2} \equiv (9^{72})^{11} *9^2 \equiv 1^{11}*9^2 \equiv 1*9^2\equiv 9^2 \pmod {73}$. $\endgroup$ – fleablood May 26 at 14:50
  • $\begingroup$ no i got it. thank you very much for your answers $\endgroup$ – user792583 May 26 at 14:55
1
$\begingroup$

$a\equiv9^{794}\equiv9^{72\times11+2}\equiv(\color{blue}{9^{72}})^{11}9^2\equiv(\color{blue}1)^{11}9^2\equiv81\bmod73$.

Can you take it from here?

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Yes 9^72≡1(mod73) I understood that and 81≡8(mod73) $\endgroup$ – user792583 May 26 at 14:42