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