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



ap11(modm) means that when ap1 is divided by m, the remainder is 1.



And according to the page on Modular Exponential




cbe(modm) means that when be 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 xy(modm), 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 limhrightarrow0fracsin(ha)h

How to find lim without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...