Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

migrated from stackoverflow.com Nov 2 '11 at 23:34

This question came from our site for professional and enthusiast programmers.

5 Answers 5

up vote 1 down vote accepted
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.
share|improve this answer

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.

share|improve this answer
    
But a is the remainder when b is divided by m, so I think it should be something like k*m + a = b where k is an integer? –  curiou57 Nov 2 '11 at 22:55
    
Right, sorry about that my brain froze on typing it out. –  JB King Nov 2 '11 at 23:00
    
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. –  curiou57 Nov 2 '11 at 23:04
    
@curiou57: Yes, because a ≡ b (mod m) and b ≡ a (mod m) are equivalent. –  ypercube Nov 2 '11 at 23:06

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

share|improve this answer
    
Both notations are standard; a ≡ b (mod m) and a mod m = b are equivalent. I don't think this is the issue. –  bnaul Nov 2 '11 at 22:48
    
I understand a mod b means that the remainder of dividing a by b. But the first equation is written as (a^(p-1)) ≡ 1 (mod m) in that article and it means (a^(p-1)) divided by m gives 1 as remainder. –  curiou57 Nov 2 '11 at 22:50
    
@bnaul: They are not equivalent. 3 ≡ 11 (mod 8) is true but 3 mod 8 = 11 is false. –  ypercube Nov 2 '11 at 22:52
    
@Charles: You are wrong. The equations listed make prefect sense. This is a very common notation in Number Theory books. –  ypercube Nov 2 '11 at 22:54
1  
@Charles: The modulo operator is different from congruence modulo n. –  tskuzzy Nov 2 '11 at 23:03

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.

share|improve this answer

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

share|improve this answer
1  
I think you mean symmetric. Reflexive means c ≡ c. –  copumpkin Nov 2 '11 at 22:41
    
@pumpkin: Woops, good catch! –  tskuzzy Nov 2 '11 at 22:41
    
@tskuzzy- So how do I interpret an equation of form a ≡ b (mod m)? Please read update.. –  curiou57 Nov 2 '11 at 22:58
    
@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. –  tskuzzy Nov 2 '11 at 23:00

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.