Generalized Gcd And Lcm

Generalized GCD

Suppose that

S \subseteq ℤ

is finite that is not all zero, then

\gcd (S)

is the largest positive integer that divides everything in

S

GCD of GCD's Is the Same as Their Union

Suppose that

T \subseteq 𝒫 (ℕ_{1})

such that

T

is finite and for every

S \in T, S

is finite, then we have

\gcd ({\gcd (S) : S \in T}) = \gcd (⋃ T)

Generalized Bezout Identity

There exists integers

x_{1}, \dots, x_{n}

such that

a_{1} x_{1} + a_{2} x_{2} + \dots + a_{n} x_{n} = \gcd (a_{1}, a_{2}, \dots, a_{n})

We prove this by induction, so for the base case we use the basic bezout identity to see that $g c d (a_{1}, a_{2}) = a_{1} x_{1} + a_{2} x_{2}$ .

Now suppose it holds true for $k \in ℕ_{2}$ and we'll show that it holds true for $k + 1$ , we have $\begin{matrix} \gcd (a_{1}, \dots a_{k + 1}) & a m p; = \gcd (\gcd (a_{1}, \dots, a_{k}), a_{k + 1}) \\ a m p; = \gcd (\sum_{i = 1}^{k} a_{i} x_{i}, a_{k + 1}) \\ a m p; = b (\sum_{i = 1}^{k} a_{i} x_{i}) + c a_{k + 1} \\ a m p; = \sum_{i = 1}^{k + 1} d_{i} a_{i} \end{matrix}$ The first line uses this fact, to get to the the second line we used the induction hypothesis and to get to the third line we used the basic bezout for 2 elements.

Divisible by Relatively Prime Numbers Means Divisible by Their Product

Suppose that

\gcd (a_{1}, \dots a_{n}) = 1

and

k \in ℤ

then

(\forall i \in [1, \dots n], a_{i} | k) ⟹ \prod_{i = 1}^{n} a_{i} | k

Since

\gcd (a_{1}, \dots, a_{n}) = 1

then there exists some

x_{1}, \dots, x_{n}

such that

\sum_{i = 1}^{n} a_{i} x_{i} = 1

, so that

\sum_{i = 1}^{n} a_{i} x_{i} k = k

we know that each

a_{i} | k

so that there is some

j_{i} \in ℤ

such that

k = a_{i} j_{i}

so we have

\sum_{i = 1}^{n} a_{i} x_{i} k = \sum_{i = 1}^{n}