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?

$\endgroup$
2
$\begingroup$
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.
$\endgroup$
2
$\begingroup$

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

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

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.

$\endgroup$
  • $\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 Nov 2 '11 at 22:55
  • $\begingroup$ Right, sorry about that my brain froze on typing it out. $\endgroup$ – JB King Nov 2 '11 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 Nov 2 '11 at 23:04
1
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

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

$\endgroup$
  • $\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 Nov 2 '11 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 Nov 2 '11 at 22:50
  • 2
    $\begingroup$ @Charles: The modulo operator is different from congruence modulo n. $\endgroup$ – tskuzzy Nov 2 '11 at 23:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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