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}...