3
$\begingroup$

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?

5 Answers 5

-1

Mod, or modulas, is a binary operator, like '+'. You write a mod b. Writing a (mod b) is a bit like writing a (+ b). That said, you might see a note in with your equations. Just I might write time = money (minus taxes as previously discussed), that wordy chunk is part of my verbiage instead of my equation.

a mod b means that the remainder of dividing a by b. For example, 27 mod 5 = 1 or (27 mod 5) + 2 = 3.

Neither of the equations listed makes any sense, because mod is binary. You probably meant:

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

and

*c = (b^e) mod m

  • 2
    @Charles: The modulo operator is different from congruence modulo n.2011-11-02
2

They are both correct. The congruence sign is symmetric so c ≡ b^e is the same as b^e ≡ c.

However what it really means is this: a≡b (mod m) if and only if m|a-b (i.e. m divides a-b).

  • 0
    @curiou57: Neither. You should interpret it as: the remainder of a/m is equal to the remainder of b/m. Alternatively, you could say the remainder of (a-b)/m is 0.2011-11-02
2

Congruence is similar to equations where they could be interpreted left to right or right to left and both are correct.

Another way to picture this is:

a ≡ b (mod m) implies there exists an integer k such that k*m+a=b 

There are various ways to visualize a (mod m) number system as the integers mod 3 could be viewed as {0,1,2} or {-1,0,1} as 2≡-1 (mod 3) to give an example here.

Another point is that the (mod m) is applied to both sides of the congruence. For example, in dealing with polar coordinates, the angle co-ordinate would be a good example of the use of a modular operator as 0 degrees is the same as 360 degrees is the same as 720 degrees as the only difference is the number of rotations to get that angle.

But the problem the same equation a ≡ b (mod m) is interpreted as k*m + a = b and k*m + b = a in the two articles.

If there exists a k such that k*m+a=b then there also exists a -k such that a=b-k*m if you remember that in an equation one can add or subtract an element so long as it is done on both sides of the equation. Thus, while the constant is different there does exist such a term.

Casting out nines would be a useful exercise if you want some examples where m=9.

  • 0
    But the problem the same equation a ≡ b (mod m) is interpreted as k*m + a = b and k*m + b = a in the two articles.2011-11-02
2
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. 
1

It's a bit of a weird notation, but you should consider the and the (mod m) as a single unit. X ≡ Y (mod m) means that the two numbers/expressions X and Y are equal when you take the remainder mod m.