In arithmetic and computer programming, the extended Euclidean algorithm is an extension to the Euclidean algorithm, which computes, besides the greatest common divisor of integers a and b, the coefficients of Bézout's identity, that is integers x and y such that
a
x
+
b
y
=
gcd
(
a
,
b
)
.
{\displaystyle ax+by=\gcd(a,b).}
This is a certifying algorithm, because the gcd is the only number that can simultaneously satisfy this equation and divide the inputs. It...
Let $S$ be a formal language string over $\Sigma$, and $S_{\leqslant}$ the substring lattice. If $t$ is a substring of $S$, we write $t \leqslant S$. Define a substring ring of a string $S$ to be a unital ring $R_S$ together with a surjective map $\phi : R_S \to S_{\leqslant}$ such that:
For a...
-1
