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