In programming terminology, the symbol $\bmod$ is "overloaded" in math to mean two different things: the modulus operator, and the "congruent mod $r$" relation.
The operator, written $a \bmod r$, is the equivalent of your %
operator. You can think of it as a function taking two integers and returning an integer: %(int a, int r) -> int
.
The relation, written $a \equiv b \pmod r$, is effectively a predicate: it is a statement with a true/false truth value, like a function returning bool
. So you can think of it as cong(int a, int b, int r) -> bool
. The connection between them is that cong(a, b, r) := ((a - b) % r == 0)
. Or ignoring what %
might do for negative numbers, cong(a, b, r) := (a % r == b % r)
.
Now, it may be that an extended passage of a math paper will be "working mod $r$". Formally, this means that all operations are not intended as operations on the integers $\mathbb{Z}$, but on the ring $\mathbb{Z}_r$ of integers mod $r$. Without getting into abstract algebra, you can think of it as roughly "the notation $a = b$ is now redefined as cong(a, b, r)
". Two numbers that are congruent mod $r$ are now considered to be the same number; they compare as equal.
It's true that the "scope" may not be specified explicitly, and the author may expect you to understand from context which ring we are working in. Usually, once you know enough abstract algebra to be able to read the paper at all, this does not lead to any confusion. A paper is after all written for a human mathematician to read, not for a compiler to parse.
However, if we say something like "Let $a,b,c \in \mathbb{Z}_r$", this means that a,b,c
are "declared", not as integers, but as objects of a class
for which the ==
operator is overloaded as cong(a, b, r)
. And so a following expression like $a + b = c$ means cong(a+b, c, r) == true
, where you can think of the +
operator also having been overloaded to return an object of the $\mathbb{Z}_r$ class.
Best Answer
Given integers $m,n$ (not both zero), Bezout's identity finds integers $x,y$ that satisfy: $$xm+ny=\gcd(m,n)$$
One important application is if we know $\gcd(m,n)=1$. Then, we can take the above equation modulo $n$ to get $$xm\equiv 1\pmod{n}$$ This is useful, because we have found the multiplicative inverse to $m$, modulo $n$.
We have a constructive (and fast) way to find $x,y$, using the extended Euclidean algorithm.
One reason a multiplicative inverse is useful is: suppose we want to find some integer $z$ satisfying the modular equation $$mz\equiv t\pmod{n}$$ Once we have found $x$, as above, we may multiply both sides by $x$ to get $$z\equiv 1z\equiv (xm)z\equiv xt\pmod{n}$$