1
$\begingroup$

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!

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

It's because $19 \equiv -4 \pmod{23}$ (or equivalently $23|(19-(-4))$), hence $19^3 \equiv (-4)^3 \pmod{23}$

$\endgroup$
1
$\begingroup$

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

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