Greatest Common Divisor

suppose that \( a , b \in \mathbb{Z} \) such that \( \left( a, b \right) \neq \left( 0, 0 \right) \), then the greatest common divisor of \( a \) and \( b \) notated
as \( \gcd{\left ( a , b \right )} \) is the largest positive integer that divides each of \( a , b \)

Therefore \( \gcd : \mathbb{ Z } \times \mathbb{ Z } \to \mathbb{ N } _ 1 \)

GCD's Characterization

Let \( a, b \in \mathbb{ Z } \), and let \( g \in \mathbb{ Z } \) sugh that \( g \mid a \land g \mid b
\) and \[ \forall d \in \mathbb{ N } _ 1, \left( d \mid a \land d \mid b \right) \implies d \le g \]
if and only if \( g = \gcd \left( a, b \right) \)

Note that since \( d \mid g \implies d \le g \) we may use \( d \mid g \) on the right hand side of the implication

GCD is a Linear Combination

For any \( a, b \in \mathbb{ Z } ^ { \neq 0 } \), there exist integers \( s, t \in \mathbb{ Z } \) such
that \( \gcd \left( a, b \right) = as + bt \), moreover \( \gcd \left( a, b \right) \) is the smallest
such positive integer of the form \( as + bt \)

Define \( S := \left\{ am + bn: m, n \in \mathbb{ Z } \text{ and } am + bn > 0\right\} \), we first note that \( S \) cannot be empty. The only way it could be empty would be if that given any choice of \( m, n \) we have \( am + bn < 0 \), but if that's the case we can always see that \( - \left( am + bn \right) > 0 \) and note that \( - \left( am + bn \right) = a \left( -m \right) + b \left( -n \right) \), which shows that there is an element in \( S \).

Since \( S \subseteq \mathbb{ N } _ 0 \), the well ordering principle tells us that there is some smallest element of \( S \), say \( d = a j + b k \). We will prove that \( \gcd \left( a, b \right) = d \).

By the quotient remainder theorem, we have some \( q, r \) such that \( a = qd + r \) where \( 0 \le r < d \), from here we can see that \[ \begin{aligned} r &= a - qd \\ &= a - q \left( aj + bk \right) \\ &= a \left( 1 - qj \right) + b \left( qk \right) \end{aligned} \] at this point in time if \( r > 0 \), then we would have a contradiction because \( r \) would be a value smaller than \( d \) that is an element of \( S \), but we assumed that \( d \) was the smallest such element. Therefore, the only way forward is that \( r = 0 \)

If \( r = 0 \), then \( a = qd \) meaning that \( d \) divides \( a \), by copying the above text and replacing the variable \( a \) with \( b \) we obtain a proof that \( d \) divides \( b \) as well. To complete showing that \( d = \gcd \left( a, b \right) \) we need to prove that \( d \) is the smallest divisor.

Suppose that \( m \) is another common divisor of \( a, b \), then we have \( k_a, k_b \in \mathbb{ Z } \), such that \( a = k_a m \) and \( b = k_b m \), from \( d \)'s definition we see \( d = a j + bk = \left( k_a m \right) j + \left( k_b m \right) k = m \left( k_a j + k_b k \right) \), this shows that \( m \mid d \) so that \( m \le d \) showing that \( d \) is the largest divisor and we conclude \( d = \gcd \left( a, b \right) \)

Relatively Prime implies there is a Linear Combination of One

If \( a, b \) are relatively prime, then there exists \( s, t \in \mathbb{ Z } \) such that \( 1 = as +
bt\)

By the definition of \( a, b \) being reliatively prime, we know that \( \gcd \left( a, b \right) = 1
\), then we know that there are
integers \( s, t \) such that \( \gcd \left( a, b \right) = as + bt \)

Factoring GCD

For any \( k , a, b \in \mathbb{ Z } \) such that \( k \neq 0 \) we have
\[
\gcd \left( ka, kb \right) = \left\lvert k \right\rvert \gcd \left( a, b \right)
\]

Forced Division through GCD

Suppose we have \( n, a, b \in \mathbb{Z} \) and that \( \gcd (a, n) = 1 \), then if \( n \mid a b \)
then \( n \mid b \)

The gcd is a linear combination, and therefore \( ax + ny = 1 \) so that \( abx + nby = b \) since \( n \mid ab \) then we have some \( k \in \mathbb{ Z } \) such that \( ab = nk \) therefore \( nkx + nby = b \) so that \( n \left( kx + by \right) = b \) so therefore \( n \mid b \)

If you Can find a Linear Combination that Yields One, then Their gcd is one

Let \( a, b \in \mathbb{ Z } \), there exists \( x, y \in \mathbb{ Z } \) such that
\[
ax + by = 1
\]
if and only if \( \gcd \left( a, b \right) = 1 \)

\( \implies \) Suppose we have a \( d \in \mathbb{ Z } \) such that \( d \mid a, b \) then we know that \( d \mid ax + by = 1 \), therefore \( d = \pm 1 \), therefore by definition \( \gcd \left( a, b \right) = 1 \). \( \impliedby \) We know this because gcd is a linear combination

Swapping Factors

Prove that for any \( a \in \mathbb{ Z } \) we have
\[
\gcd \left( 5 a + 2, 7a + 3 \right) = 1
\]

Observe that \( \left( 5a + 2 \right) \left( -7 \right) + \left( 7 a + 3 \right) 5 = -35a + 35a - 14 + 15 = 1 \) and therefore \( \gcd \left( 5a + 2, 7a + 3 \right) = 1 \) as needed.

Coefficients have GCD one

Suppose that \( \gcd \left( a, b \right) = g \) and thus we have some \( x, y \in \mathbb{ Z } \) such that \( ax + b y = g \) then \( \gcd \left( x, y \right) = 1 \)

\[
ax + b y = g \iff \left( \frac{a}{g} \right) x + \left( \frac{b}{g} \right) y = 1
\]
therefore \( \gcd \left( x, y \right) = 1 \)

Dividing out by GCD removes all Common Factors

Suppose \( a, b \in \mathbb{ Z } \) and let \( d := \gcd \left( a, b \right) \) then
\[
\gcd \left( \frac{a}{d} , \frac{b}{d} \right) = 1
\]

We know that the gcd is a linear combination, so we get some \( x, y \in \mathbb{ Z } \) such that \( d = ax + by \) therefore
\[
1 = \left( \frac{a}{d} \right) x + \left( \frac{b}{d} \right) y
\]
therefore by the previous proposition we see that \( \gcd \left( \frac{a}{d} , \frac{b}{d} \right) = 1 \)

Rational in Lowest Terms

A rational number \( r \in \mathbb{ Q } \) written as a fraction \( r = \frac{a}{b} \) is said to be in **lowest terms** if \( \gcd \left( a, b \right) = 1 \)

Lowest Terms Rational Always Exists

For any \( r \in \mathbb{ Q } \) it can be represented in lowest terms

Suppose \( r = \frac{a}{b} \in \mathbb{ Q } \) and let \( d = \gcd \left( a, b \right) \) and consider
\[
\frac{a}{b} = \left( \frac{\frac{1}{d} }{\frac{1}{d} } \right) \left( \frac{a}{d} \right) = \frac{\frac{a}{d} }{\frac{b}{d}}
\]
and since we know that \( \gcd \left( \frac{a}{d} , \frac{b}{d} \right) = 1 \) we've proven the statement true

Non Trivial Divisors

Let \( n \in \mathbb{ Z } \) such that \( \left\lvert n \right\rvert \ge 2 \) then we define
\[
\operatorname{ ntd } \left( n \right) = \left\{ d \in \mathbb{ N } _ 2 : d \mid n \right\}
\]

Non Trivial Divisors is a Subset of 2 up to The Number

For any \( n \in \mathbb{ Z } \) such that \( \left\lvert n \right\rvert \ge 2 \) then we have
\[
\operatorname{ ntd } \left( n \right) \subseteq \left[ 2, \ldots , n \right]
\]

The Non Trivial Divisors of n Factorial Plus or Minus One

Suppose that \( n \in \mathbb{ N } _ 1 \) then
\[
\operatorname{ ntd } \left( n! + 1 \right) \subseteq \left[ n + 1, \ldots , n! + 1 \right]
\]

Let \( d \in \operatorname{ ntd } \left( n ! + 1 \right) \) then we know that \( d \in \left[ 2, \ldots , n! + 1 \right] \) but if \( d \in \left[ 2, \ldots , n \right] \) then we already know that \( d \nmid n! + 1 \) which is a contradiction, therefore we must have that \( d \in \left[ n + 1, \ldots n! + 1 \right] \) as needed.

Common Divisor Set

Suppose that \( a, b \in \mathbb{ Z } \) then we define
\[
\operatorname{ cd } \left( a, b \right) = \left\{ d \in \mathbb{ Z } : d \mid a \land d \mid b \right\}
\]

Common Divisors as the Intersection of the Non Trivial Divisors

Suppose that \( a, b \in \mathbb{ Z } \) then
\[
\operatorname{ cd } \left( a, b \right) = \operatorname{ ntd } \left( a \right) \cap \operatorname{ ntd } \left( b \right) \cup \left\{ 1 \right\}
\]

Common Divisor Set is Bounded Above

\[
\operatorname{ cd } \left( a, b \right) \le \min \left( a, b \right)
\]

Add a multiple of the other Yields Same Common Divisors

For any \( a, b, k \in \mathbb{ Z } \)
\[
\operatorname{ cd } \left( a , b \right) = \operatorname{ cd } \left( a, b + k a \right)
\]

\( \subseteq \) Suppose \( d \mid a, b \) therefore \( d \mid a + k a \) as needed. \( \supseteq \) now suppose that \( d \mid a, b + ka \) since \( d \mid a \) then \( d \mid ka \) and therefore \( d \mid \left( b + ka \right) - ka = b\) therefore \( d \in \operatorname{ cd } \left( a, b \right) \)

No Common Non Trivial Divisors Implies Relatively Prime

Suppose \( a, b \in \mathbb{ Z } \) then
\[
\operatorname{ ntd } \left( a \right) \cap \operatorname{ ntd } \left( b \right) = \emptyset \implies \gcd \left( a, b \right) = 1
\]

Superset Divisors Implies Greater GCD

For any \( a, b, p, q \in \mathbb{ Z } \)
\[
\operatorname{ cd } \left( a, b \right) \subseteq \operatorname{ cd } \left( p, q \right) \implies \gcd \left( a, b \right) \le \gcd \left( p, q \right)
\]

For any \( X \subseteq Y \subseteq \mathbb{ Z } \) then \( \max \left( X \right) \lt \max \left( Y \right) \) therefore we have
\[
\gcd \left( a, b \right) = \max \left( \operatorname{ cd } \left( a, b \right) \right) \le \max \left( \operatorname{ cd } \left( p, q \right) \right) = \gcd \left( p, q \right)
\]
so that \( \gcd \left( a, b \right) \le \gcd \left( p, q \right) \) as needed.

Same Divisors Implies same GCD

Suppose that \( a , b , p , q \in \mathbb{Z} \), then
\[
\operatorname{ cd } \left( a, b \right) = \operatorname{ cd } \left( p, q \right) \implies \gcd \left( a, b \right) = \gcd \left( p, q \right)
\]

Since \( \operatorname{ cd } \left( a, b \right) = \operatorname{ cd } \left( p, q \right) \) then we know that \( \operatorname{ cd } \left( a, b \right) \subseteq \operatorname{ cd } \left( p, q \right) \) and that \( \operatorname{ cd } \left( a, b \right) \supseteq \operatorname{ cd } \left( p, q \right) \) so that we have \( gcd \left( a, b \right) \le \gcd \left( p, q \right) \) and \( \gcd \left( a, b \right) \ge \gcd \left( a, b \right) \) so that \( \gcd \left( a, b \right) = \gcd \left( p, q \right) \) as needed.

Add a multiple of the other Yields same GCD

For any \( a, b, k \in \mathbb{ Z } \) we have
\[
\gcd \left( a, b \right) = \gcd \left( a, b + ka \right)
\]

Since the common divisors are the same, then the gcd of the two is the same

Let \( n \in \mathbb{ Z } \) then
\[
\gcd \left( n, n + 1 \right) = 1
\]

Suppose that there existed some \( d \in \mathbb{ N } _ 2 \) such that \( d \mid n \) and \( d \mid n + 1 \) then we would have \( d \mid n + 1 - n = 1\) which implies that \( d = \pm 1 \) which is a contradiction, thus the only divisor of \( n \) and \( n + 1 \) is one, so that \( \gcd \left( n, n + 1 \right) = 1 \)

Division by Individuals Implies Division by Product when GCD is one

Suppose \( \gcd \left( a, b \right) = 1 \) then
\[
\left( a \mid c \land b \mid c \right) \implies ab \mid c
\]

The gcd is a linear combintion of \( a, b \) so \( a x + by = 1 \) for some \( x, y \in \mathbb{ z } \) but then
\[
acx + bcy = c
\]
but recall that \( a \mid c \) and \( b \mid c \) so we have \( k _ a, k _ b \in \mathbb{ Z } \) such that \( c = k _ a a \) and \( c = k _ b b \) subbing each of these equations into the above equation we have
\[
a \left( b k _ b \right) x + b \left( a k _ a \right) y = c
\]
so therefore \( \left( a b \right) \left( k _ b x + k _ a y \right) = c \) so that \( ab \mid c \) as needed.

GCD of a Multiple is Greater

For any \( a, b ,k \in \mathbb{ Z } \) we have:
\[
\gcd \left( a, b \right) \le \gcd \left( k a, b \right)
\]

Recall this, therefore we can show that \( \operatorname{ cd } \left( a, b \right) \subseteq \operatorname{ cd } \left( ak , b \right) \) thus \( \gcd \left( a, b \right) \le \gcd \left( ka, b \right) \)

A Divisor of a Coprime number Is also Coprime

Suppose that \( a, b, d \in \mathbb{ Z } \) such that \( \gcd \left( a, b \right) = 1 \) and \( d \mid a \) then \( \gcd \left( d, b \right) = 1 \)

Let \( g := \gcd \left( b, d \right) \) clearly \( g \mid d \) and since \( d \mid a \) then \( g \mid a \), also we know that \( g \mid b \) and therefore \( g \) is a common divisor of \( a, b \) and therefore \( g = 1 \), as needed.

Relatively Prime Factors Implies Relatively Prime Product

Suppose that \( \gcd \left( a, b \right) = 1 \) and \( \gcd \left( a, c \right) = 1 \) then \( \gcd \left( a, bc \right) = 1 \)

We have some \( x _ 1, x _ 2, y _ 1, y _ 2 \) such that
\[
a x _ 1 + b y _ 1 = 1 = a x _ 2 + c y _ 2
\]
So then
\[
\begin{align}
1 &= \left( a x _ 1 + b y _ 1 \right) \left( a x _ 2 + c y _ 2 \right) \\
&= a ^ 2 x _ 1 x _ 2 + a x _ 1 c y _ 2 + b y _ 1 a x _ 2 + b c y _ 1 y _ 2 \\
&= a \left( a x _ 1 x _ 2 + x _ 1 b y _ 2 + b y _ 1 x _ 2 \right) + bc \left( y _ 1 y _ 2 \right)
\end{align}
\]
so therefore \( \gcd \left( a, bc \right) = 1 \)

GCD of a Factorial

Suppose that \( n \in \mathbb{ N } _ 1 \), determine
\[
\gcd \left( n! + 1 , \left( n + 1 \right)! + 1 \right)
\]

We know that
\[
\begin{align}
\gcd \left( n! + 1 , \left( n + 1 \right)! + 1 \right) &= \gcd \left( n! + 1, \left( n! + 1 \right) ! + 1 - \left( n! + 1 \right) \right) \\
&= \gcd \left( n! + 1, \left( n + 1 \right)! - n! \right) \\
&= \gcd \left( n! + 1 , n! \left( n + 1 - 1\right) \right) \\
&= \gcd \left( n! + 1 , n! n \right) \\
\end{align}
\]

Note that \[ \operatorname{ ntd } \left( n ! + 1 \right) \cap \operatorname{ ntd } \left( n \right) = \emptyset \] because \( \operatorname{ ntd } \left( n! + 1 \right) \subseteq \left[ n + 1, \ldots , n ! + 1 \right] \) and that \( \operatorname{ ntd } \left( n \right) \subseteq \left[ 2, \ldots , n \right] \), therefore \[ \gcd \left( n! + 1 , n \right) = 1 \] we also know that \( \gcd \left( n! + 1, n! \right) = 1 \) therefore \[ \gcd \left( n! + 1 , n n! \right) = 1 \]

Coprime

\( a , b \in \mathbb{Z} \) are said to be coprime if the only positive integer that divides them is \(
1 \).

Coprime GCD Characterization

\( a , b \in \mathbb{Z} \) are coprime if and only if \( \gcd{\left ( a , b \right )} = 1 \)

\( \implies \) If \( a, b \) are coprime, then \( D _ { a, b } = \left\{ 1, -1 \right\} \) and therefore \( \gcd \left( a, b \right) = 1 \) as needed. \( \impliedby \) if \( \gcd \left( a, b \right) = 1 \) then the only positive integer that divides them is \( 1 \) because if some other positive integer divided both of them then \( \gcd \left( a, b \right) \gt 1 \) which would be a contradiction.

Least Common Multiple

Suppose that \( a , b \in \mathbb{Z} \) then the least common multiple of \( a \) and \( b \) notated
as \( \operatorname{ lcm } \left ( a , b \right) \) is the smallest positive integer such that \( a, b \mid \operatorname{ lcm } \left( a, b \right) \)

Least Common Multiple Characterization

The lcm \( l := \operatorname{ lcm } \left( a, b \right) \) is the unique number satisfying

- \( a, b \mid l \)
- For every \( m \in \mathbb{ Z } ^ +, \left( a, b \mid m \right) \implies l \le m \)

Similarly we may replace \( l \le m \) with \( l \mid m \) since it implies \( l \le m \).

GCD and LCM Connection

\[
\gcd \left( a, b \right) \operatorname{ lcm } \left( a, b \right) = ab
\]

For simplicity let \( g, l \) denote the the gcd and lcm respectively, then we're trying to prove that \( l = \frac{ab}{g} \) we'll do that using the characterization, so note that \( l = a \left( \frac{b}{d} \right) = b \left( \frac{a}{d} \right) \) and that \( \frac{b}{d} , \frac{a}{d} \in \mathbb{ Z } \) since \( d \) divides both by definition, thus \( a, b \mid l \).

Now suppose that there is some \( m \in \mathbb{ Z } ^ + \) such that \( a , b \mid m \) in other words there exists some \( k _ a, k _ b \in \mathbb{ Z } \) such that \( m = a k _ a = b k _ b \) we'll show that \( l \le m \). Recall that \( d \mid a, b \) and so we get some \( \alpha , \beta \in \mathbb{ Z } \) such that \( a = \alpha d \) and \( b = \beta d \) therfore \[ m = a k _ a = b k _ b \iff \left( \alpha d \right) k _ a = \left( \beta d \right) k _ b \iff \alpha k _ a = \beta k _ b \]

The above equation shows that \( \alpha \mid \beta k _ b \) and \( \beta \mid \alpha k _ a \), but note that \( \gcd \left( \alpha , \beta \right) = \gcd \left( \frac{a}{d} , \frac{b}{d} \right) = 1 \) therefore by the previous proposition we must have that \( \alpha \mid k _ b \) and \( \beta \mid k _ a \) therefore there is some \( j \in \mathbb{ Z } \) such that \( k _ b = j \alpha \) thus finally \[ m = b k _ b = b j \alpha = b \left( \frac{a}{d} \right) j = l j \] therefore \( l \mid m \) so that \( l \le m \). Therefore \( l = \frac{ab}{g} \) and thus \( g l = ab \) as needed.

Divisor Function is a Bijection if Relatively Prime

For \( n \in \mathbb{ N } _ 1 \) let \( D _ n \) denote its set of positive divisors \( D _ n := \left\{ a \mid n: a \in \mathbb{ N } _ 1 \right\} \), prove that for any \( m, n \in \mathbb{ N } _ 1 \) that \( f: D _ n \times D _ m \to D _ { n m } \) defined as
\[
f \left( a, b \right) = ab
\]
is well defined, and is a bijection if \( \gcd \left( m, n \right) = 1 \)

Recall that a function is well defined if given two equal inputs it cannot map to a different value, this is true simply because for any \( a, b \) \( a \cdot b \) is equal to exactly one value. Additionally note that given a divisor of \( m \) and a divisor of \( n \) then their product divides \( m n \) so under the given definition it respects the functions signature.

Now suppose that \( \gcd \left( m, n \right) = 1 \) we want to prove that \( f \) is a bijection. First we show that it is injective, so suppose that \( f \left( a, b \right) = f \left( c, d \right) \) and we will prove that \( \left( a, b \right) = \left( c, d \right) \) the first equality we assumed really means that \( ab = cd \), but we also know that \( a, c \mid n \) and that \( b, d \mid m \) therefore we know that \( \gcd \left( a, d \right) = \gcd \left( b, c \right) = 1 \) but from the equation \( ab = cd \) we see that \( a \mid cd \) so that \( a \mid c \), but on the other hand \( c \mid ab \) so that \( c \mid a \) so we conclude that \( a = c \) similarly we conclude that \( b = d \) so that \( \left( a, b \right) = \left( c, d \right) \) as needed.

Now we show that it is surjective so let \( x \in D _ { m n } \) we need to find a \( \left( j, k \right) \) that gets mapped to \( x \) since \( gcd \left( m, n \right) = 1 \) then we know that since \( x \mid m, n \) then \( x = d _ n d _ m \) where \( d _ n, d _ m \) are divisors of \( n , m \) respectively, thus \( f \left( d _ n, d _ m \right) = x \)