Greatest common divisor

Note: requires knowledge of what it means for a number to be a divisor of another.

Definition

Given two positive integers, $a,b\in\mathbb{N}_+$, the greatest common divisor of $a$ and $b$ is the greatest positive integer, $d$, that divides both $a$ and $b$. We write:

• $d=\text{gcd}(a,b)$

Proper definition - UNCONFIRMED

This section is Alec's own speculation - not yet verified

Using the Well-ordered principle (given the set of divisors is a finite set, the set has a maximum element, and the maximum is the same as the $\text{Sup}$ of the set) we can state the $\text{gcd}$ as follows:

• $$\text{gcd}(a,b)=\text{sup}(\{n\in\mathbb{N}|n\text{ divides } a\}\cap\{n\in\mathbb{N}|n\text{ divides } b\})$$

End of the unconfirmed part

Terminology

Co-prime

If for $a,b\in\mathbb{N}_+$ we have $\text{gcd}(a,b)=1$ then $a$ and $b$ are said to be co-prime

Coprime

Coprime is used by some authors, co-prime by others. I prefer the hyphenated form because to be co-something implies more than one thing is involved. You cannot have "a coprime number" but you can have a pair of co-prime numbers.

See next

• Euclidean algorithm

See also

• Division algorithm
• Divisor