1
$\begingroup$

I wanted to check if it is true, that $$a^{3b} \pmod n = (a^{b} \pmod n)^{3}\ ?$$

For example when $a = 2, b = 4, n = 5$ I have that $2^{12} \mod 5 = 1$ and $(2^4 \mod 5)^3 = 1$ Is that always true, or maybe the left side should be equal to something different?

$\endgroup$

2 Answers 2

1
$\begingroup$

Obviously, you should take $a^{3b} \mod n = (a^{b} \mod n)^{3} \mod n$

Otherwise, say, if your $(a^{b} \mod n)$ is not $1$ but, say, $4$, you'll get $a^{3b} \mod 5 = 64 $ which is technically incorrect (however, still understandable by a human).

$\endgroup$
3
  • $\begingroup$ Are you alluding to the difference between $=$ and $\equiv$? $\endgroup$ May 21, 2014 at 9:52
  • $\begingroup$ Yeah. Actually, I had modulo arithmetic at school long ago, but still pretty sure that with a normal $=$ sign you normally mean the actual equality of two numbers. And, especially, if you are writing a program, that may lead to a mistake because cubing the number $a^b (\mod n)$ will not necesarrily give you a number less than $n$ (that can be checked against $a^{3b} (\mod n)$). $\endgroup$
    – Shady_arc
    May 21, 2014 at 10:32
  • $\begingroup$ you have a point there, OP does not make it clear ... $\endgroup$ May 21, 2014 at 10:52
1
$\begingroup$

True, modulo division is if you are working in the ring $\mathbb{Z}/n\mathbb{Z}$, where $(\bar{a}^b)^3 \equiv \bar{a}^{3b}$ for any $\bar{a} \in \mathbb{Z}/n\mathbb{Z}$ (here the overbar means moduo $n$).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .