0
$\begingroup$

I was requested to find the remainder of $9^{52}*7^{33}$ when dividing it by $8$, using modular arithmetic. Let that remainder be $r$. I understand the following will apply:

$9^{52}*7^{33} \equiv r \mod{(8)}$

so that all I must find is the congruence of the product in the module $8$. But how can one go about solving this? I don't have any tries worth showing, since I simply ignore what procedure could be followed.

$\endgroup$
  • 1
    $\begingroup$ $7\equiv -1$ and $9\equiv 1$ mod $8$, so the expression is equal to $$1^{52}\cdot(-1)^{33}\bmod8=-1$$ $\endgroup$ – Don Thousand May 29 at 21:27
  • $\begingroup$ But doesn't this mean the remainder of the division is negative? That does not make sense. What am I missing? $\endgroup$ – lafinur May 30 at 1:53
  • $\begingroup$ $-1\equiv 7\bmod8$. $\endgroup$ – Don Thousand May 30 at 2:05
  • $\begingroup$ Of course, how silly of me. Thank you very much for answering my question. $\endgroup$ – lafinur May 30 at 2:26
0
$\begingroup$

Hint. Since $9$ is $1$ modulo $8$, so is any power. What can you say about odd powers of $7$ using the same kind of reasoning? To find a modulus after multiplying you multiply the two moduli.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Hint:

$9\equiv 1,\qquad 7 \equiv -1\mod 8.$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Doesn't all this imply that $r = -1$? Since I'm left with $-1 \equiv r \mod (8)$. How can a remainder be negative? $\endgroup$ – lafinur May 30 at 2:02
  • $\begingroup$ There exists versions of Euclidean division for which the remainder can be negative… This being said, it is only a hint. You still have to find the least positive integer which is congruent to $-1\bmod 8$. This shouldn't be too hard. $\endgroup$ – Bernard May 30 at 8:36

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.