Is it trying to say that $(\operatorname{mod} 7)$ is neither associated with $29$ nor $15$?

604 Views Asked by At

I am reading Notes of Mathematics for Computer Science(MIT 6.042J). And I'm stuck in the Modular Arithmetic Section which I mark with a RED LINE.

I want to know what is trying to say. Is it trying to say that $(\operatorname{mod} 7)$ is neither associated with $29$ nor $15$? Here the Picture of that Equation

5

There are 5 best solutions below

4
On BEST ANSWER

This is largely a matter of finding whatever focus helps you to understand the process going on here. The $\pmod 7$ is describing what kind of equivalence ($\equiv$) we're using - so $\pmod 7$ is not "acting on" either of the numbers in reality. To bring the $\equiv$ and the $\pmod 7$ together, you could imagine that the comparator is written as $\color{red}{\underset{\bbox[2px]{\bmod 7}}{\equiv}}$ or even $\color{red}{\underset{\bbox[2px]{7}}{\equiv}}$ with reasonable clarity, if that is a useful way of understanding for you.

So what does $29 \equiv 15 \pmod 7$ (or in the above variant notation $29 \color{red}{\underset{\bbox[2px]7}{\equiv}} 15$) actually mean?

  • $29$ and $15$ sit in the same relation to the nearest respective multiples of $7$ - that is, $29$ is the same position in $(28, 35)$ as $15$ is in $(14,21)$
  • $(29-15)$ is divisible by $7$ (the two numbers are separated by an integer mulitple of $7$)
  • $29$ and $15$ have the same remainder when divided by $7$ (although for negative numbers this can be confusing/ambiguous).
1
On

It is trying to say that we identify all numbers modulo $7$. So $15$ isn't any more equal (equivalent) to $7$ than $29$ is. In other words, $$29\equiv 15\equiv 1 \bmod 7, $$ so they are all equivalent to $1$. Perhaps the equal sign is clearer. In the ring $\mathbb{Z}/7\mathbb{Z}$, we really have equality: $29=15=1$. On the other hand, in the ring $\mathbb{Z}$, these numbers are not equal, but only equivalent modulo $7$.

6
On

The author is talking about the placement of the phrase "(mod 7)". What the expression $29\equiv15$ (mod 7) is really saying is that 29 (mod 7) and 15 (mod 7) are equivalent. The placement of the "(mod 7)" after the 15 is not modifying the 15 alone, but the entire equivalent statement, i.e., $\left[29\equiv15\right]$ (mod 7). The author is really complaining about the way it is conventionally written, but is unable to do anything about it because the convention is "firmly entrenched."

In other words, don't worry about it. The author is just whining about the conventional notation, but it will not affect the overall mathematics.

2
On

It seems the point of the remark is to emphasize the symmetric property of the congruence relation i.e. $\,a\equiv b\iff b\equiv a\pmod m.\,$ This is not true for the operator mod, e.g we have $\,15\equiv 1\pmod 7\,$ and $\, (15\bmod 7) = 1\,$ and $\,1\equiv 15\pmod 7\,$ but $\ (1\bmod 7) \neq 15.\,$

The operational mod is antisymmetric since it converts its argument to normal form. The relational mod has no such preference, which often makes it more flexible in many contexts, e.g. $\,{\rm mod}\ 10\!:\,\ 9\equiv -1\,\Rightarrow\, 9^{2n}\equiv (-1)^{2n}\equiv ((-1)^2)^n\equiv 1^n\equiv 1,\,$ where we have used the flexibility of the congruence relation to choose a rep $\equiv 9\,$ which makes the power computation trivial.

Generally a congruence (to a fixed modulus) can be thought of as a generalized equality relation (i.e. an equivalence relation) that is, furthermore, consistent with the arithmetic operations (here obeys the Congruence Sum and Product Rules). This will be made more precise when you study quotient sets and algebras in abstract algebra.

1
On

In programming terms....

Because of some early programming languages and unfortunate choices of terminology, programmers often interpret "mod" as the remainder operator; e.g. 29%7 is the value 1.

But in mathematics, mod is an equivalence relation, which is, under a rather literal translation from mathematics to python:

def mod(n):
    return lambda x,y: (x-y) % n == 0

rel = mod(7) # Obtain the equivalence relation "mod 7"
rel(29, 15) # returns True

The text is trying to make sure you correctly interpret the phrase

$$ 29 \equiv 15 \pmod{7} $$

as

rel(29,15)

and not as

29 == 15 % 7