1
$\begingroup$

This is from https://courses.cs.washington.edu/courses/cse311/14au/slides/lecture12-filled.pdf,

This procedure is used to solve a modular exponentiation problem, say enter image description here

Here is the procedure enter image description here

How do you get from the first step to the second step?

To get $a^2$ mod m on the left side, I would multiply both sides of the first step by a to get

$a^2$ mod m $\equiv a^2$ (mod m )

How do i get from that to $(a $mod m$)^2$ mod m?

$\endgroup$
  • $\begingroup$ to put things in latex you need a $ sign on either side of the expression and the equiv was wrong because you had a forward slash after it...hope my edits helped $\endgroup$ – Gabriel Feb 10 '15 at 1:45
  • $\begingroup$ @Gabriel Yeah they did. Thank you :) $\endgroup$ – committedandroider Feb 10 '15 at 1:49
1
$\begingroup$

We use the following lemma. If $x\equiv a \pmod{m}$ and $y\equiv b\pmod{m}$ then $xy\equiv ab\pmod{m}$. This may already have been proved in your course. If it has not, here is a quick proof. We want to show that $m$ divides$xy-ab$. Note that $$xy-ab=x(y-b)+b(x-a).$$ Since $m$ divides $y-b$ and $m$ divides $x-a$, the result follows.

We use the above lemma, taking $b=a$ and $x=y=a\bmod{m}$. We get $$(a\bmod{m})^2\equiv a^2\pmod{m}.$$ Thus the left side and the right side have the same remainder on division by $m$. It follows that $$(a\bmod{m})^2\bmod{m}=a^2\bmod{m},$$ which is what we wanted to show.

The result about $a^4\bmod{m}$ is proved in the same way.

$\endgroup$
  • $\begingroup$ Thanks for that explanation. Now I get why we proved that in the first place. Do you know why a mod m $\equiv$a(mod m) for any as though? Is that a property? I am just going to use it for now. $\endgroup$ – committedandroider Feb 10 '15 at 4:59
  • $\begingroup$ Divide $a$ by $m$. We get $a=qm+r$ for some $q$ and $r$, with $0\le r\lt m$. The number $r$ is the remainder, often called $a\bmof{m}$ by people in Computer Science. From $a=r+qm$, we conclude that $a\equiv r\pmod{m}$. $\endgroup$ – André Nicolas Feb 10 '15 at 5:05
  • $\begingroup$ That makes sense. But that's a $\equiv$ r (mod m), not a mod m $\equiv$ a (mod m) $\endgroup$ – committedandroider Feb 10 '15 at 6:04
  • $\begingroup$ Sorry, but how did you reach this conclusion - "the left side and the right side have the same remainder on division by m" ? $\endgroup$ – committedandroider Feb 10 '15 at 6:16
  • 1
    $\begingroup$ In general we have $x\equiv y\pmod{m}$ if and only if $y\equiv x\pmod{m}$. For $m$ divides $x-y$ if and only if $m$ divides $y-x$. $\endgroup$ – André Nicolas Feb 10 '15 at 6:55

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.