Thursday, 18 August 2016

Confused about modular notations



I am little confused about the notations used in two articles at wikipedia.



According to the page on Fermat Primality test



a^{p-1}\equiv 1 \pmod{m} means that when a^{p-1} is divided by m, the remainder is 1.



And according to the page on Modular Exponential




c \equiv b^e \pmod{m} means that when b^e is divided by m, the remainder is c.



Am I interpreting them wrong? or both of them are right? Can someone please clarify them to me?



Update: So given an equation say x \equiv y \pmod{m}, how do we interpret it? y divided by m gives x as remainder or x divided by m gives y as remainder?


Answer



x ≡ y (mod m)



is equivalent to:



x divided by m gives the same remainder as y divided by m






So, in your first example:



a^(p-1) ≡ 1 (mod m)



is equivalent to:



a^(p-1) divided by m gives the same remainder as 1 divided by m



But 1 divided by m gives remainder 1, so the above becomes:



a^(p-1) divided by m gives remainder 1







In your second example:



c ≡ b^e (mod m)


is equivalent to:



c divided by m gives the same remainder as b^e divided by m




But (assuming that 0 <=c < m) we have c divided by m gives remainder c, so the above becomes:



c is the remainder that b^e divided by m gives.






As it seems that the notation may be confusing, let me note that



x ≡ y (mod m)



should be read as:



[ x ≡ y ] (mod m)         --- the (mod m) is applied to the whole congruence


and not as:



x ≡ [ y (mod m) ]         --- and not just to the right part.


No comments:

Post a Comment

real analysis - How to find lim_{hrightarrow 0}frac{sin(ha)}{h}

How to find \lim_{h\rightarrow 0}\frac{\sin(ha)}{h} without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...