2
$\begingroup$

I am trying to understand the modular exponentiation algorithm. Why is it that:

$x^2 \mod5 = (x\mod5)(x\mod5) \mod 5$

What is the basic reasoning behind this?

2 Answers 2

6

Write $x = m + 5n$ with $0 \leq m \leq 4$. No matter what you multiply $5n$ by, the result will be a multiple of $5$ and subsequently dropped by the "mod $5$" at the end. So, you might as well have dropped the $5n$ to begin with. That is, you could just take $x$ mod $5$ before carrying out the multiplication.

-1

I am not sure about the doubt in ur mind but i hope i am answering ur question! The reason for the last mod5 in the rhs is to ensure that the lhs and the rhs are compatible.As the lhs is a residue it is by defn a value between 0 & 5.However if u drop the final mod5 the rhs may not be a residue(note that it is a product of two residues,so not necessarily a residue by itself!). eg x=4 implies lhs =1 without the final mod5 the rhs value=16 !

  • 2
    Hi: welcome to math.SE! I just wanted to drop a few tips for better solution writing here. Correct spacing, linebreaks, and spelling are important for making a solution readable. It's also a good rule of thumb to avoid using idiosyncratic abbreviations where possible. People are more likely to read your post and upvote it if it is easy to read!2012-12-27