The properties of the GCD of two natural numbers

For all $ (a, b) \in \hspace{0.05em}\mathbb{N}^2, \enspace a > b $, we notice:

$ \delta = a \wedge b = GCD(a, b) $;

$ GCD(a, b) $ is the greatest common divisor of $ a $ and $ b $.

It is the last non-zero remainder $ R_n $ of the Euclidian division of $ a $ by $ b $ in the Euclid's algorithm.

$ \mathcal{D}(a, b)$ the set of common divisors of $ a $ and $ b $;
$ \mathcal{D}(\delta)$ the set of all divisors of $ GCD(a, b) $.

Equality between the divisors of a and b and the divisors of thier GCD

$$ \forall (a, b) \in \hspace{0.05em}\mathbb{N}^2, \enspace a > b, $$

$$ \mathcal{D}(a, b) = \mathcal{D}( GCD(a, b) ) $$

The set of common divisors of $ a $ and $ b $ is the set of divisors of $ GCD(a, b) $.

Equality between the successives GCD of the Euclid's algorithm

$$ \forall (a, b, q) \in (\mathbb{N})^3, \enspace a > b, \enspace \forall R \in \mathbb{N^*}, \enspace 0 < R < b, $$

$$ a = bq + R \Longrightarrow GCD(a, b) = GCD(b, R) $$

Breakdown in prime factors

$$ \forall (a, b) \in \hspace{0.05em}\mathbb{N}^2, \enspace a > b,$$

Let be the breakdown of $a $ and $b $ in prime factors:

$$ \forall n \in \mathbb{N}, \enspace \forall p_n \in \mathbb{P}, \enspace \exists (\alpha_n, \beta_n) \in \hspace{0.05em}\mathbb{N}^2, \enspace \Biggl \{ \begin{gather*} a = p_1^{\alpha_1}p_2^{\alpha_2}...p_n^{\alpha_n} \\ b = p_1^{\beta_1}p_2^{\beta_2}...p_n^{\beta_n} \end{gather*} $$

So,

$$ GCD(a, b) = p_1^{min \{ \alpha_1, \beta_1\}} \times p_2^{min\{\alpha_2, \beta_2\}} \hspace{0.2em} \times \hspace{0.2em} ... \hspace{0.2em} \times \hspace{0.2em} p_n^{min \{ \alpha_n, \beta_n\}} $$

The Bézout's identity

$$ \forall (a, b) \in \hspace{0.05em}\mathbb{N}^2, \enspace a > b, $$

$$ \delta = a \wedge b \hspace{0.2em} \Longrightarrow \hspace{0.2em} \exists (u, v) \in \hspace{0.05em}\mathbb{Z}^2, \enspace au + bv = \delta \qquad (Bézout's \ identity)$$

Breakdown of two numbers in relation to their GCD

$$ \forall (a, b) \in \hspace{0.05em}\mathbb{N}^2, $$

$$ \delta = a \wedge b \hspace{0.2em} \Longrightarrow \hspace{0.2em} \exists (a', b') \in \mathbb{N}, \enspace \Biggl \{ \begin{gather*} a = \delta a' \\ b = \delta b'\end{gather*} \enspace \enspace (with \enspace a' \wedge b' = 1)$$

Linearity

$$ \forall (a, b) \in \hspace{0.05em}\mathbb{N}^2, \enspace a > b, \enspace \forall k \in \mathbb{Z},$$

$$ GCD(ka, kb) = k.GCD(a, b) $$

Link between GCD and LCM

$$ \forall (a, b) \in \hspace{0.05em}\mathbb{N}^2, \enspace a > b,$$

$$ GCD(a, b) \times LCM(a, b) = ab $$

Recap table of the $GCD(A,B)$

Demonstration

Equality between the divisors of a and b and the divisors of thier GCD

Let be $(a, b) \in \hspace{0.05em}\mathbb{N}^2$ and $ \delta = GCD(a, b) $.

As $ \delta $ is the greatest common divisor of $ a $ and $ b $, so:

$$ \Biggl \{ \begin{gather*} \delta / a \Longrightarrow a = k\delta \\ \delta / b \Longrightarrow b = k'\delta \end {gather*} \qquad (1) $$

Let suppose it exists $ d \ ( d \in \mathbb{N}) $, a commun divisor of $ a $ and $ b $, such as $ d < \delta $, and which does not divide $ \delta $.

So, we would have:

$$ \Biggl \{ \begin{gather*} d / a \Longrightarrow a = qd \\ d / b \Longrightarrow b = q'd \\ d \nmid \delta \Longrightarrow \delta = Qd + R \end {gather*} \qquad (2) $$

As a result, both expressions $ (1) $ et $ (2) $ combined give:

$$ \Biggl \{ \begin{gather*} a = k\delta = qd \Longrightarrow k ( Qd + R ) = qd \\ b = k'\delta = q'd \Longrightarrow k' ( Qd + R ) = q'd \end {gather*} $$

$$ \Biggl \{ \begin{gather*} a = kQd + k R = qd \\ b = k'Qd + k' R = q'd \end {gather*} \qquad (3) $$

The only way for $ (3) $ to make sense would be that:

$$ \Biggl \{ \begin{gather*} k = d \\ k' = d \end {gather*} \enspace \Longrightarrow \enspace k = k' = d $$

But, $ k \neq k' $ since $ a \neq b $ and $ \delta $ is unique, that does not make sense.

We then clearly see that any number $ d $, common divisor of $ a $ and $ b $ also divides their $GCD$.

So that the set all of common divisors of $ a $ and $ b $ is also the set of the divisors of $ GCD(a, b) $.

$$ \forall (a, b) \in \hspace{0.05em}\mathbb{N}^2, \enspace a > b, $$

$$ \mathcal{D}(a, b) = \mathcal{D}( GCD(a, b) ) $$

We can find all this divisors by the breakdown in prime factors of $ GCD(a, b) $.

Equality between the successives GCD of the Euclid's algorithm

Let $(a, b) \in \hspace{0.05em}\mathbb{N}^2$ two natural numbers.

If $b$ does not divide $a$, we know that:

$$ \exists q_0 \in (\mathbb{N}), \enspace \exists R_0 \in \mathbb{N^*}, \enspace 0 < R_0 < b, \enspace a = bq_0 + R_0 $$

Likewise, if $R_0$ does not divide $b$:

$$ \exists q_1 \in (\mathbb{N}), \enspace \exists R_1 \in \mathbb{N^*}, \enspace 0 < R_1 < R_0 , \enspace b = R_0 q_1 + R_1 $$

And so on...

However, we know from the Euclid's algorithm that:

$ \forall (k,n) \in \hspace{0.05em}\mathbb{N}^2$, for $ k $ from $ 0 $ to $ n $, as long as $R_{k} $ does not divide $R_{k -1 } $, that is to say $R_{k} \neq 0$:

$$ GCD(a, b) = GCD(b, R_0) = GCD(R_0, R_1) = \enspace ... \enspace = GCD(R_{n - 1}, R_n) = R_n \neq 0$$

And finally:

$$ \forall (a, b, q) \in (\mathbb{N})^3, \enspace a > b, \enspace \forall R \in \mathbb{N^*}, \enspace 0 < R < b, $$

$$ a = bq + R \Longrightarrow GCD(a, b)= GCD(b, R) $$

Breakdown in prime factors

Let $ (a, b) \in \hspace{0.05em}\mathbb{N}^2 $ be two natural numbers with $a > b $.

Let be the breakdown of $a $ and $b $ in prime factors:

We know that $ GCD(a, b) $ is the greatest common divisor of $a $ and $ b $.

The greatest common divisor of two numbers $ A = p^{\alpha} $ and $ B = p^{\beta} $ is:

$$ D= p^{min \{ \alpha, \beta\}} $$

we have

So, by applying this reasoning to the primary breakdown of $a $ and $ b $, we do have this:

$$ GCD(a, b) = p_1^{min \{ \alpha_1, \beta_1\}} \times p_2^{min\{\alpha_2, \beta_2\}} \hspace{0.2em} \times \hspace{0.2em} ... \hspace{0.2em} \times \hspace{0.2em} p_n^{min \{ \alpha_n, \beta_n\}} $$

The Bézout's identity

Let $(a, b) \in \hspace{0.05em}\mathbb{Z}^2$ be two integers with $a > b $.

Let us start from the hypothesis that $ \delta = a \wedge b $.

Two scenarios then arise: $ b / a $ or $ b \nmid a $.

If $ b $ divides $ a $

If $ b $ divides $ a $, then $\exists q \in \mathbb{N}$, such as $ q < a$,

$$ a = bq \Longrightarrow a \wedge b = b $$

We then notice that $ \delta = b $ and it can be written:

$$ \delta = au + bv, \enspace with \enspace \Biggl \{ \begin{gather*} u = 0\\ v = 1 \end{gather*} $$

If $ b $ does not divide $ a $

In this case, $ \exists q_0 \in \mathbb{Z}, \enspace \exists R_0 \in \mathbb{N}, \enspace 0 < R_0 < b$,

$$ a = bq_0 + R_0 $$

But, we know by the property seen above that:

$$ \forall (a, b, q) \in (\mathbb{N})^3, \enspace \forall R \in \mathbb{N^*}, $$

$$ a = bq + R \Longrightarrow GCD(a, b) = GCD(b, R) $$

So in our case:

$$ a = bq_0 + R_0 \Longrightarrow a \wedge b = b \wedge R_0 $$

- If $ R_0 $ divide $ b $

So, $ \delta = R_0 $ because $ R_0 $ is the last non-zero remainder of the Euclid's algorithm, and:

$$ \delta = R_0 = a - bq_0 $$

$$ \delta = au + bv, \enspace with \enspace \Biggl \{ \begin{gather*} u = 1\\ v = -q_0 \end{gather*} $$

- If $ R_0 $ does not divide $ b $

So, $ \exists q_1 \in \mathbb{Z}, \enspace \exists R_1 \in \mathbb{N}, \enspace 0 < R_1 < R_0 $,

$$ b = R_0q_1 + R_1 \Longrightarrow a \wedge b = b \wedge R_0 = R_0 \wedge R_1 $$

- If $ R_1 $ divides $ R_0 $

So, $ \delta = R_1 $ and:

$$ \delta = R_1 = b - R_0q_1 $$

$$ \delta = R_1 = b - (a - bq_0)q_1 $$

$$\delta = R_1 = -q_1 a + b(1 + q_0 q_1)$$

$$ \delta = au + bv \enspace with \enspace \Biggl \{ \begin{gather*} u = -q_1 \\ v = -1 + q_0 q_1 \end{gather*} $$

- If $ R_1 $ does not divide $ R_0 $

We continue the Euclid's algorithm until the last non-zero remainder is $ GCD $.

Thus, in any case:

$$ \forall (a, b) \in \hspace{0.05em}\mathbb{N}^2, \enspace a > b, $$

$$ \delta = a \wedge b \hspace{0.2em} \Longrightarrow \hspace{0.2em} \exists (u, v) \in \hspace{0.05em}\mathbb{Z}^2, \enspace au + bv = \delta \qquad (Bézout's \ identity) $$

This property is known as The Bézout's identity.

Breakdown of two numbers in relation to their GCD

Let $(a, b) \in \hspace{0.05em}\mathbb{Z}^2$ be two integers.

If $ \delta = a \wedge b$, then $ \delta / a $ and $ \delta / b $, so:

$$ \Biggl \{ \begin{gather*} a = \delta a' \\ b = \delta b' \end{gather*} $$

If $ a' $ and $ b' $ were not coprime, we would have then the existence of a divisor $ d $, other than $ 1 $, and such as:

$$ \Biggl \{ \begin{gather*} a' = d a'' \\ b' = d b'' \end{gather*} $$

Which would mean that it exists a common divisor $ d $ greater than $ \delta $.

Which is absurd, so $ a' $ and $ b' $ are necessarily coprime.

We then imperatively have $a' \wedge b' = 1$.

$$ \forall (a, b) \in \hspace{0.05em}\mathbb{N}^2, \enspace a > b, $$

$$ \delta = a \wedge b \hspace{0.2em} \Longleftrightarrow \hspace{0.2em} \exists (a', b') \in \mathbb{N}, \enspace \Biggl \{ \begin{gather*} a = \delta a' \\ b = \delta b'\end{gather*} \enspace \enspace (with \enspace a' \wedge b' = 1)$$

And finally,

Linearity

Let $(a, b) \in \hspace{0.05em}\mathbb{Z}^2$ be two integers with $a > b $, and also $k \in \mathbb{Z}$.

Let us note $ \delta = GCD(a, b)$ and $ \Delta = GCD(ka, kb) $.

We know from the property of common divisors of two numbers and their $GCD$ that:

The set of common divisors of $ a $ and $ b $ is the set of divisors of $ GCD(a, b) $.

So,

$$ \Biggl \{ \begin{gather*} k / ka \\ k / kb \end{gather*} \Longrightarrow k/\Delta $$

If $ k/\Delta $, this also mean that:

$$ \exists c \in \mathbb{Z}, \enspace \Delta = kc $$

Likewise, as $ \Delta = GCD(ka, kb) $, so:

$$ \Biggl \{ \begin{gather*} \Delta / ka \\ \Delta / kb \end{gather*} $$

But $ \Delta = kc $, and with the simplification property of divisibility:

$$ \Biggl \{ \begin{gather*} kc / ka \Longrightarrow c / a \\ kc / kb \Longrightarrow c / b \end{gather*} $$

And again with the property of common divisors of two numbers and their $GCD$:

$$ \Biggl \{ \begin{gather*} c / a \\ c / b \end{gather*} \Longrightarrow c/\delta $$

Well,

$$ c / \delta \Longrightarrow kc/k \delta \Longrightarrow \Delta/k \delta \qquad (1) $$

Moreover,

$$ \Biggl \{ \begin{gather*} \delta / a \Longrightarrow k\delta / ka \\ \delta / a \Longrightarrow k\delta / kb \end{gather*} \Longrightarrow k\delta/\Delta \qquad (2) $$

Both assertions $(1)$ et $(2)$ show that:

$$ \Biggl \{ \begin{gather*} \Delta/k \delta \qquad (1) \\ k\delta/\Delta \qquad (2) \end{gather*} \Longrightarrow \Delta = k\delta $$

And finally,

$$ \forall (a, b) \in \hspace{0.05em}\mathbb{N}^2, \enspace a > b, \enspace \forall k \in \mathbb{Z},$$

$$ GCD(ka, kb) = k.GCD(a, b) $$

Link between GCD and LCM

Let be the breakdown of $a $ and $b $ in prime factors:

We saw above that $GCD(a,b)$ can be written:

$$ GCD(a, b) = p_1^{min \{ \alpha_1, \beta_1\}} \times p_2^{min\{\alpha_2, \beta_2\}} \hspace{0.2em} \times \hspace{0.2em} ... \hspace{0.2em} \times \hspace{0.2em} p_n^{min \{ \alpha_n, \beta_n\}} $$

Furthermore, the $LCM(a,b)$ can be written:

$$ LCM(a, b) = p_1^{max \{ \alpha_1, \beta_1\}} \times p_2^{max\{\alpha_2, \beta_2\}} \hspace{0.2em} \times \hspace{0.2em} ... \hspace{0.2em} \times \hspace{0.2em} p_n^{max \{ \alpha_n, \beta_n\}} $$

By performing the product of $GCD(a,b) \times LCM(a,b)$:

$$ GCD(a, b) \times LCM(a, b) = p_1^{min \{ \alpha_1, \beta_1\}} \times p_1^{max \{ \alpha_1, \beta_1\}} \times p_2^{min \{ \alpha_2, \beta_2\}} \times p_2^{max\{\alpha_2, \beta_2\}} \hspace{0.2em} \times \hspace{0.2em} ... \hspace{0.2em} \times \hspace{0.2em} p_n^{min \{ \alpha_n, \beta_n\}} \times p_n^{max \{ \alpha_n, \beta_n\}} $$

$$ GCD(a, b) \times LCM(a, b) = p_1^{min \{ \alpha_1, \beta_1\} + max \{ \alpha_1, \beta_1\}} \times p_2^{min \{ \alpha_2, \beta_2\} + max\{\alpha_2, \beta_2\}} \hspace{0.2em} \times \hspace{0.2em} ... \hspace{0.2em} \times \hspace{0.2em} p_n^{min \{ \alpha_n, \beta_n\} + max \{ \alpha_n, \beta_n\}} $$

$$ GCD(a, b) \times LCM(a, b) = p_1^{\alpha_1 + \beta_1} \times p_2^{\alpha_2+ \beta_2} \hspace{0.2em} \times \hspace{0.2em} ... \hspace{0.2em} \times \hspace{0.2em} p_n^{ \alpha_n+ \beta_n} $$

$$ GCD(a, b) \times LCM(a, b) = p_1^{\alpha_1}p_1^{\beta_1} \times p_2^{\alpha_2} p_2^{\beta} \hspace{0.2em} \times \hspace{0.2em} ... \hspace{0.2em} \times \hspace{0.2em} p_n^{ \alpha_n}p_n^{ \beta} $$

However, this product is equivalent to $(ab)$:

$$ ab = p_1^{\alpha_1}p_1^{\beta_1} \times p_2^{\alpha_2} p_2^{\beta} \hspace{0.2em} \times \hspace{0.2em} ... \hspace{0.2em} \times \hspace{0.2em} p_n^{ \alpha_n}p_n^{ \beta} $$

And finally,

$$ \forall (a, b) \in \hspace{0.05em}\mathbb{N}^2, \enspace a > b,$$

$$ GCD(a, b) \times LCM(a, b) = ab $$

Recap table of the $GCD(A,B)$