📂Number Theory

Greatest Common Divisor and Coprime

Definition ¹

1. For two integers $n$ and $m \ne 0$, if there exists an integer $k$ that satisfies the following, $n$ is divisible by $m$. $$n = mk$$ In this case, $n$ is called a Multiple of $m$, and $m$ is called a Divisor of $n$, as indicated below. $$m \mid n$$ If $m$ cannot divide $n$, it is denoted by striking through as $m \nmid n$.
2. Let’s assume two non-$0$ integers $a$, $b$ are given. The largest common divisor that divides both is called the Greatest Common Divisor of $a$ and $b$, denoted as $\gcd (a,b)$.
3. If $\gcd (a,b) = 1$, then $a$ and $b$ are said to be Relatively Prime.

Explanation

The concepts of Greatest Common Divisor and Relatively Prime are something most people have seen from their elementary school days.

As can be seen from the English expression Relatively Prime, contrary to many people’s language habits (even in the title of this post, where it’s written without a space, as if it’s a single word), Relatively Prime literally means relatively prime. Although Mutually might seem a more fitting word to express ’each other’ in English, Mutually has its own significant meaning across mathematics, hence Relatively is used. Here, ‘relatively’ means that the two numbers $a$ and $b$ do not share any divisor other than $1$, making them essentially prime to each other. They may not be absolutely prime, but for each other, they can be considered as prime.

See Also

Algebraic Generalization

Generalized in Unique Factorization Domain.