gcd and lcm

Greatest Common Divisor

suppose that

a, b \in ℤ

such that

(a, b) \neq (0, 0)

, then the greatest common divisor of

a

and

b

notated as

gcd (a, b)

is the largest positive integer that divides each of

a, b

Therefore $gcd : Z \times Z \to N_{1}$

GCD's Characterization

Let

a, b \in Z

, and let

g \in Z

sugh that

g ∣ a \land g ∣ b

and

\forall d \in N_{1}, (d ∣ a \land d ∣ b) ⟹ d \leq g

if and only if

g = gcd (a, b)

Note that since $d ∣ g ⟹ d \leq g$ we may use $d ∣ g$ on the right hand side of the implication

GCD is a Linear Combination

For any

a, b \in Z^{\neq 0}

, there exist integers

s, t \in Z

such that

gcd (a, b) = a s + b t

, moreover

gcd (a, b)

is the smallest such positive integer of the form

a s + b t

Define $S : = {a m + b n : m, n \in Z and a m + b n >; 0}$ , 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 $a m + b n <; 0$ , but if that's the case we can always see that $- (a m + b n) >; 0$ and note that $- (a m + b n) = a (- m) + b (- n)$ , which shows that there is an element in $S$ .

Since $S \subseteq 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 (a, b) = d$ .

By the quotient remainder theorem, we have some $q, r$ such that $a = q d + r$ where $0 \leq r <; d$ , from here we can see that $r & = a - q d & = a - q (a j + b k) & = a (1 - q j) + b (q k)$ 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 = q d$ 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 (a, b)$ 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 Z$ , such that $a = k_{a} m$ and $b = k_{b} m$ , from $d$ 's definition we see $d = a j + b k = (k_{a} m) j + (k_{b} m) k = m (k_{a} j + k_{b} k)$ , this shows that $m ∣ d$ so that $m \leq d$ showing that $d$ is the largest divisor and we conclude $d = gcd (a, b)$

Relatively Prime implies there is a Linear Combination of One

a, b

are relatively prime, then there exists

s, t \in Z

such that

1 = a s + b t

By the definition of

a, b

being reliatively prime, we know that

gcd (a, b) = 1

, then we know that there are integers

s, t

such that

gcd (a, b) = a s + b t

Factoring GCD

For any

k, a, b \in Z

such that

k \neq 0

we have

gcd (k a, k b) = | k | gcd (a, b)

Forced Division through GCD

Suppose we have

n, a, b \in ℤ

and that

gcd (a, n) = 1

, then if

n ∣ a b

then

n ∣ b

The gcd is a linear combination, and therefore

a x + n y = 1

so that

a b x + n b y = b

since

n ∣ a b

then we have some

k \in Z

such that

a b = n k

therefore

n k x + n b y = b

so that

n (k x + b y) = b

so therefore

n ∣ b

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

Let

a, b \in Z

, there exists

x, y \in Z

such that

a x + b y = 1

if and only if

gcd (a, b) = 1

⟹

Suppose we have a

d \in Z

such that

d ∣ a, b

then we know that

d ∣ a x + b y = 1

, therefore

d = \pm 1

, therefore by definition

gcd (a, b) = 1

⟸

We know this because gcd is a linear combination

Swapping Factors

Prove that for any

a \in Z

we have

gcd (5 a + 2, 7 a + 3) = 1

Observe that

(5 a + 2) (- 7) + (7 a + 3) 5 = - 35 a + 35 a - 14 + 15 = 1

and therefore

gcd (5 a + 2, 7 a + 3) = 1

as needed.

Coefficients have GCD one

Suppose that

gcd (a, b) = g

and thus we have some

x, y \in Z

such that

a x + b y = g

then

gcd (x, y) = 1

a x + b y = g ⟺ (\frac{a}{g}) x + (\frac{b}{g}) y = 1

therefore

gcd (x, y) = 1

Dividing out by GCD removes all Common Factors

Suppose

a, b \in Z

and let

d : = gcd (a, b)

then

gcd (\frac{a}{d}, \frac{b}{d}) = 1

We know that the gcd is a linear combination, so we get some

x, y \in Z

such that

d = a x + b y

therefore

1 = (\frac{a}{d}) x + (\frac{b}{d}) y

therefore by the previous proposition we see that

gcd (\frac{a}{d}, \frac{b}{d}) = 1

Rational in Lowest Terms

A rational number

r \in Q

written as a fraction

r = \frac{a}{b}

is said to be in lowest terms if

gcd (a, b) = 1

Lowest Terms Rational Always Exists

For any

r \in Q

it can be represented in lowest terms

Suppose

r = \frac{a}{b} \in Q

and let

d = gcd (a, b)

and consider

\frac{a}{b} = (\frac{\frac{1}{d}}{\frac{1}{d}}) (\frac{a}{d}) = \frac{\frac{a}{d}}{\frac{b}{d}}

and since we know that

gcd (\frac{a}{d}, \frac{b}{d}) = 1

we've proven the statement true

Non Trivial Divisors

Let

n \in Z

such that

| n | \geq 2

then we define

ntd (n) = {d \in N_{2} : d ∣ n}

Non Trivial Divisors Don't Change with the Sign Changes

For any

a \in Z

ntd (a) = ntd (- a)

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

For any

n \in Z

such that

| n | \geq 2

then we have

ntd (n) \subseteq [2, \dots, n]

The Non Trivial Divisors of n Factorial Plus or Minus One

Suppose that

n \in N_{1}

then

ntd (n! + 1) \subseteq [n + 1, \dots, n! + 1]

Let

d \in ntd (n! + 1)

then we know that

d \in [2, \dots, n! + 1]

but if

d \in [2, \dots, n]

then we already know that

d ∤ n! + 1

which is a contradiction, therefore we must have that

d \in [n + 1, \dots n! + 1]

as needed.

Common Divisor Set

Suppose that

a, b \in Z

then we define

cd (a, b) = {d \in Z : d ∣ a \land d ∣ b}

Common Divisors as the Intersection of the Non Trivial Divisors

Suppose that

a, b \in Z

then

cd (a, b) = ntd (a) \cap ntd (b) \cup {1}

Note that it follows that you can flip the sign and the common divisors don't change, this also shows that it can be done in the gcd, TODO add a proof of this.

Common Divisor Set is Bounded Above

cd (a, b) \leq min (a, b)

Add a multiple of the other Yields Same Common Divisors

For any

a, b, k \in Z

cd (a, b) = cd (a, b + k a)

$\subseteq$ Suppose $d ∣ a, b$ therefore $d ∣ a + k a$ as needed. $\supseteq$ now suppose that $d ∣ a, b + k a$ since $d ∣ a$ then $d ∣ k a$ and therefore $d ∣ (b + k a) - k a = b$ therefore $d \in cd (a, b)$

No Common Non Trivial Divisors Implies Relatively Prime

Suppose

a, b \in Z

then

ntd (a) \cap ntd (b) = \emptyset ⟹ gcd (a, b) = 1

Superset Divisors Implies Greater GCD

For any

a, b, p, q \in Z

cd (a, b) \subseteq cd (p, q) ⟹ gcd (a, b) \leq gcd (p, q)

For any

X \subseteq Y \subseteq Z

then

max (X) < max (Y)

therefore we have

gcd (a, b) = max (cd (a, b)) \leq max (cd (p, q)) = gcd (p, q)

so that

gcd (a, b) \leq gcd (p, q)

as needed.

Same Divisors Implies same GCD

Suppose that

a, b, p, q \in ℤ

, then

cd (a, b) = cd (p, q) ⟹ gcd (a, b) = gcd (p, q)

Since

cd (a, b) = cd (p, q)

then we know that

cd (a, b) \subseteq cd (p, q)

and that

cd (a, b) \supseteq cd (p, q)

so that we have

g c d (a, b) \leq gcd (p, q)

and

gcd (a, b) \geq gcd (a, b)

so that

gcd (a, b) = gcd (p, q)

as needed.

Add a multiple of the other Yields same GCD

For any

a, b, k \in Z

we have

gcd (a, b) = gcd (a, b + k a)

Let

n \in Z

then

gcd (n, n + 1) = 1

Suppose that there existed some

d \in N_{2}

such that

d ∣ n

and

d ∣ n + 1

then we would have

d ∣ 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 (n, n + 1) = 1

Division by Individuals Implies Division by Product when GCD is one

Suppose

gcd (a, b) = 1

then

(a ∣ c \land b ∣ c) ⟹ a b ∣ c

The gcd is a linear combintion of

a, b

a x + b y = 1

for some

x, y \in z

but then

a c x + b c y = c

but recall that

a ∣ c

and

b ∣ c

so we have

k_{a}, k_{b} \in Z

such that

c = k_{a} a

and

c = k_{b} b

subbing each of these equations into the above equation we have

a (b k_{b}) x + b (a k_{a}) y = c

so therefore

(a b) (k_{b} x + k_{a} y) = c

so that

a b ∣ c

as needed.

GCD of a Multiple is Greater

For any

a, b, k \in Z

we have:

gcd (a, b) \leq gcd (k a, b)

Recall this, therefore we can show that

cd (a, b) \subseteq cd (a k, b)

thus

gcd (a, b) \leq gcd (k a, b)

A Divisor of a Coprime number Is also Coprime

Suppose that

a, b, d \in Z

such that

gcd (a, b) = 1

and

d ∣ a

then

gcd (d, b) = 1

Let

g : = gcd (b, d)

clearly

g ∣ d

and since

d ∣ a

then

g ∣ a

, also we know that

g ∣ 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 (a, b) = 1

and

gcd (a, c) = 1

then

gcd (a, b c) = 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

1 & = (a x_{1} + b y_{1}) (a x_{2} + c y_{2}) & = 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 (a x_{1} x_{2} + x_{1} b y_{2} + b y_{1} x_{2}) + b c (y_{1} y_{2})

so therefore

gcd (a, b c) = 1

GCD of a Factorial

Suppose that

n \in N_{1}

, determine

gcd (n! + 1, (n + 1)! + 1)

We know that

gcd (n! + 1, (n + 1)! + 1) & = gcd (n! + 1, (n! + 1)! + 1 - (n! + 1)) & = gcd (n! + 1, (n + 1)! - n!) & = gcd (n! + 1, n! (n + 1 - 1)) & = gcd (n! + 1, n! n)

Note that $ntd (n! + 1) \cap ntd (n) = \emptyset$ because $ntd (n! + 1) \subseteq [n + 1, \dots, n! + 1]$ and that $ntd (n) \subseteq [2, \dots, n]$ , therefore $gcd (n! + 1, n) = 1$ we also know that $gcd (n! + 1, n!) = 1$ therefore $gcd (n! + 1, n n!) = 1$

Coprime

a, b \in ℤ

are said to be coprime if the only positive integer that divides them is

1

Coprime GCD Characterization

a, b \in ℤ

are coprime if and only if

gcd (a, b) = 1

⟹

a, b

are coprime, then

D_{a, b} = {1, - 1}

and therefore

gcd (a, b) = 1

as needed.

⟸

gcd (a, b) = 1

then the only positive integer that divides them is

1

because if some other positive integer divided both of them then

gcd (a, b) > 1

which would be a contradiction.

Least Common Multiple

Suppose that

a, b \in ℤ

then the least common multiple of

a

and

b

notated as

lcm (a, b)

is the smallest positive integer such that

a, b ∣ lcm (a, b)

Least Common Multiple Characterization

The lcm

l : = lcm (a, b)

is the unique number satisfying

$a, b ∣ l$
For every $m \in Z^{+}, (a, b ∣ m) ⟹ l \leq m$

Similarly we may replace $l \leq m$ with $l ∣ m$ since it implies $l \leq m$ .

GCD and LCM Connection

gcd (a, b) lcm (a, b) = a b

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

Now suppose that there is some $m \in Z^{+}$ such that $a, b ∣ m$ in other words there exists some $k_{a}, k_{b} \in Z$ such that $m = a k_{a} = b k_{b}$ we'll show that $l \leq m$ . Recall that $d ∣ a, b$ and so we get some $α, β \in Z$ such that $a = α d$ and $b = β d$ therfore $m = a k_{a} = b k_{b} ⟺ (α d) k_{a} = (β d) k_{b} ⟺ α k_{a} = β k_{b}$

The above equation shows that $α ∣ β k_{b}$ and $β ∣ α k_{a}$ , but note that $gcd (α, β) = gcd (\frac{a}{d}, \frac{b}{d}) = 1$ therefore by the previous proposition we must have that $α ∣ k_{b}$ and $β ∣ k_{a}$ therefore there is some $j \in Z$ such that $k_{b} = j α$ thus finally $m = b k_{b} = b j α = b (\frac{a}{d}) j = l j$ therefore $l ∣ m$ so that $l \leq m$ . Therefore $l = \frac{a b}{g}$ and thus $g l = a b$ as needed.

Divisor Function is a Bijection if Relatively Prime

For

n \in N_{1}

let

D_{n}

denote its set of positive divisors

D_{n} : = {a ∣ n : a \in N_{1}}

, prove that for any

m, n \in N_{1}

that

f : D_{n} \times D_{m} \to D_{n m}

defined as

f (a, b) = a b

is well defined, and is a bijection if

gcd (m, n) = 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 (m, n) = 1$ we want to prove that $f$ is a bijection. First we show that it is injective, so suppose that $f (a, b) = f (c, d)$ and we will prove that $(a, b) = (c, d)$ the first equality we assumed really means that $a b = c d$ , but we also know that $a, c ∣ n$ and that $b, d ∣ m$ therefore we know that $gcd (a, d) = gcd (b, c) = 1$ but from the equation $a b = c d$ we see that $a ∣ c d$ so that $a ∣ c$ , but on the other hand $c ∣ a b$ so that $c ∣ a$ so we conclude that $a = c$ similarly we conclude that $b = d$ so that $(a, b) = (c, d)$ as needed.

Now we show that it is surjective so let $x \in D_{m n}$ we need to find a $(j, k)$ that gets mapped to $x$ since $g c d (m, n) = 1$ then we know that since $x ∣ m, n$ then $x = d_{n} d_{m}$ where $d_{n}, d_{m}$ are divisors of $n, m$ respectively, thus $f (d_{n}, d_{m}) = x$

🏗️ ΘρϵηΠατπ🚧 (under construction)

🏗️ $Θ ρ ϵ η Π α τ π$ 🚧 (under construction)