x ≡ y (mod m)

is equivalent to:

x divided by m gives the same remainder asy 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 as1 divided by m

But1 divided by m gives remainder1, so the above becomes:

a^(p-1) divided by m gives remainder1

In your second example:

c ≡ b^e (mod m)

is equivalent to:

c divided by m gives the same remainder asb^e divided by m

But (assuming that0 <=c < m) we havec divided by m gives remainderc, so the above becomes:

c is the remainder thatb^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

andnot as:

x ≡ [ y (mod m) ]         --- and not just to the right part.

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

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

• $\begingroup$@tskuzzy- So how do I interpret an equation of form a ≡ b (mod m)? Please read update..$\endgroup$

  curiou57

  – curiou57

  2011-11-02 22:58:22 +00:00

  CommentedNov 2, 2011 at 22:58
• $\begingroup$@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.$\endgroup$

  tskuzzy

  – tskuzzy

  2011-11-02 23:00:12 +00:00

  CommentedNov 2, 2011 at 23:00

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.

• $\begingroup$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?$\endgroup$

  curiou57

  – curiou57

  2011-11-02 22:55:29 +00:00

  CommentedNov 2, 2011 at 22:55
• $\begingroup$Right, sorry about that my brain froze on typing it out.$\endgroup$

  JB King

  – JB King

  2011-11-02 23:00:10 +00:00

  CommentedNov 2, 2011 at 23:00
• $\begingroup$But the problem the same equation a ≡ b (mod m) is interpreted as km + a = b and km + b = a in the two articles.$\endgroup$

  curiou57

  – curiou57

  2011-11-02 23:04:33 +00:00

  CommentedNov 2, 2011 at 23:04

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 remaindermod m.

Mod, or modulas, is a binary operator, like '+'. You writea mod b. Writinga (mod b) is a bit like writinga (+ b). That said, you might see a note in with your equations. Just I might writetime = 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

• $\begingroup$Both notations are standard; a ≡ b (mod m) and a mod m = b are equivalent. I don't think this is the issue.$\endgroup$

  bnaul

  – bnaul

  2011-11-02 22:48:55 +00:00

  CommentedNov 2, 2011 at 22:48
• $\begingroup$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.$\endgroup$

  curiou57

  – curiou57

  2011-11-02 22:50:38 +00:00

  CommentedNov 2, 2011 at 22:50
• 2
  $\begingroup$@Charles: The modulo operator is different from congruence modulo n.$\endgroup$

  tskuzzy

  – tskuzzy

  2011-11-02 23:03:16 +00:00

  CommentedNov 2, 2011 at 23:03

• notation
• modular-arithmetic