# Modular Arithmetic Question (Rosen Discrete Mathematics and its applications)

I came across this exercise in Rosen Discrete Mathematics and its applications and even after spending an hour plus googling I couldn't find an answer that could explain how this question is to be done. I saw somewhere that a certain theorem is used, but I'm not sure how it is applied.

$$(19^3\mod23)^2\mod31$$

The answer is: $$((-4)^3 \mod 23)^2\mod31=(-64\mod23)^2\mod31=25$$

Possibly useful theorem:

If $$a \equiv b\mod m, c\equiv d\mod m$$ then $$ac=bd(\mod m)$$

My question: I'm concerned with how I can get from $$19^3$$ to $$(-4)^3$$.

Thank you!

• Because $-4\equiv19\mod 23$ (because $23|23=19-(-4)$ – J. W. Tanner Nov 1 '19 at 16:13
• $19$ and $19 \pm 23k$ leave the same remainder when divided by $23$ – AgentS Nov 1 '19 at 16:14
• Also, $19^a$ and $(19\pm 23k)^a$ leave the same remainder when divided by $23$. – AgentS Nov 1 '19 at 16:17
• The composed mod operators look fishy. What is the exact statement of the problem? You may be misunderstanding relational vs operational mod. – Bill Dubuque Nov 1 '19 at 17:58
• @BillDubuque the exact statement is "33. Find each of these values." and exactly as what I have written above – IceTea Nov 2 '19 at 16:42

It's because $$19 \equiv -4 \pmod{23}$$ (or equivalently $$23|(19-(-4))$$), hence $$19^3 \equiv (-4)^3 \pmod{23}$$
You apply the given Congruence Product Rule. When we iterate it on the same congruence (i.e. by induction) we obtain the Congruence Power Rule $$\ \bbox[5px,border:1px solid #c00]{a\equiv b\,\Rightarrow\, a^n\equiv b^n}\,$$ for all $$\,n\in\Bbb N.\,$$ Therefore
$$\bmod 23 \!:\,\ 19\equiv -4\,\Rightarrow\, 19^3\equiv (-4)^3$$