The properties of the GCD of two natural numbers

For all $ (a, b) \in \hspace{0.04em}\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 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) $$

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

$$ \exists! n \in \mathbb{N}^*, \enspace \exists! (p_1 < p_2 < ... < p_r) \in \mathbb{P}^r, \enspace \exists (\alpha_1, \alpha_2, ..., \alpha_r) \in \mathbb{N}^r, \enspace \exists (\beta_1, \beta_2, ..., \beta_r) \in \mathbb{N}^r, $$

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

The Bézout's identity

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

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

Breakdown of two numbers in relation to their GCD

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

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

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

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

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

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

Linearity

$$ \forall (a, b) \in \hspace{0.04em}\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.04em}\mathbb{N}^2, \enspace a > b,$$

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

Recap table of the GCD properties

Proofs

Equality between the successives GCD of the Euclid's algorithm

Let $(a, b) \in \hspace{0.04em}\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.04em}\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.04em}\mathbb{N}^2 $ be two natural integers with $a > b $.

Let the prime factorization of $a $ and $b $ be:

$$ \begin{cases} a = p_1^{\alpha_1}p_2^{\alpha_2}\dots p_r^{\alpha_r} \\ b = p_1^{\beta_1}p_2^{\beta_2}\dots p_r^{\beta_r} \end{cases}$$

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

The greatest common divisor $D$ of two prime powers of the same prime base $ A = p^{\alpha} $ and $ B = p^{\beta} $ is given by the lower of these two powers:

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

Generalization by independence of prime factors

Any common divisor $ d $ of $ a $ and $ b $ can only be composed of the same prime factors $ p_i $. Furthermore, due to the uniqueness of prime factorization, the choice of the maximum exponent for a given prime factor $ p_i $ does not influence the choice of exponents for other distinct prime factors.

Thus, maximizing the common divisor $ d $ is equivalent to simultaneously and independently maximizing the exponent of each prime number $ p_i $, which requires taking the minimum of the exponents $ \min\{\alpha_i, \beta_i\} $ separately for each primary component.

Then, by applying this reasoning to all the prime factors in the factorization of $ a $ and $ b $, we obtain by multiplication:

$$ PGCD(a, b) = p_1^{\min \{ \alpha_1, \beta_1\}} \times p_2^{\min\{\alpha_2, \beta_2\}} \times \dots \times p_r^{\min \{ \alpha_r, \beta_r\}} $$

The Bézout's identity

Let $(a, b) \in \hspace{0.04em}\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 \mid 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, \text{ with } \begin{cases} u = 0\\ v = 1 \end{cases}$$
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 $$
1. 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, \text{ with } \begin{cases} u = 1\\ v = -q_0 \end{cases}$$
2. 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 $$
  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 \text{ with } \begin{cases} u = -q_1 \\ v = -1 + q_0 q_1 \end{cases}$$
  2. if $ R_1 $ does not divide $ R_0 $
    
    We continue the Euclid's algorithm until the last non-zero remainder is the GCD .

Thus, in any case:

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

$$ \delta = a \wedge b \hspace{0.2em} \Longrightarrow \hspace{0.2em} \exists (u, v) \in \hspace{0.04em}\mathbb{Z}^2, \enspace au + bv = \delta \qquad (\text{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.04em}\mathbb{Z}^2$ be two integers.

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

$$ \begin{cases} a = \delta a' \\ b = \delta b' \end{cases}$$

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

$$ \begin{cases} a' = d a'' \\ b' = d b'' \end{cases}$$

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.04em}\mathbb{N}^2, \enspace a > b, $$

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

And finally,

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

Let $ (a,b) \in (\mathbb{N}^*)^2 $ be two natural integers not both zero, and let us denote $ \delta = a \wedge b $ their GCD.

We want to prove that the set of common divisors of $ a $ and $ b $ is exactly the set of divisors of $ \delta $.

Forward direction: If $ d $ divides $ a $ and $ b $, then $ d $ divides $ \delta $

Suppose there exists a natural integer $ d $ that is a common divisor of $ a $ and $ b $. We therefore have:

$$ \begin{cases} d \mid a \\ d \mid b \end{cases} $$

According to Bézout's identity proved above, there exists a pair of integers $ (u, v) \in \mathbb{Z}^2 $ such that:

$$ \delta = au + bv $$

Since $ d $ divides $ a $ and $ d $ divides $ b $, it follows that:

$$ \exists(k, k') \in \mathbb{Z}^2, \ \begin{cases} d \mid a \implies a = kd \\ d \mid b \implies b = k'd \end{cases} $$

Substituting these expressions into Bézout's identity, we obtain:

$$ \delta = (kd)u + (k'd)v = d(ku + k'v) $$

Since $ (ku + k'v) $ is an integer, this equality immediately shows that $ d $ divides $ \delta $.

$$ \forall (a,b) \in (\mathbb{N}^*)^2, \enspace \delta = a \wedge b, $$

$$ (d \mid a) \land (d \mid b) \implies d \mid \delta $$
Converse direction: If $ d $ divides $ \delta $, then $ d $ divides $ a $ and $ b $

Conversely, suppose that $ d $ is a natural integer that divides $ \delta $. By definition of the GCD, $ \delta $ is a common divisor of $ a $ and $ b $, which can be written as:

$$ d \mid \delta \implies \begin{cases} \delta \mid a \\ \delta \mid b \end{cases} $$

By the transitivity property of divisibility, we know that:

$$ \forall (a, b) \in (\mathbb{Z}^*)^2, \enspace \forall c \in \mathbb{Z}, $$

$$ (a \mid b) \text{ and } (b \mid c) \hspace{0.2em} \Longrightarrow \hspace{0.2em} a \mid c $$

In our case,

$$ \begin{cases} (d \mid \delta) \text{ and } (\delta \mid a) \hspace{0.2em} \Longrightarrow \hspace{0.2em} d \mid a \\ (d \mid \delta) \text{ and } (\delta \mid b) \hspace{0.2em} \Longrightarrow \hspace{0.2em} d \mid b \end{cases} $$

$$ \forall (a,b) \in (\mathbb{N}^*)^2, \enspace \delta = a \wedge b, $$

$$ d \mid \delta \implies (d \mid a) \land (d \mid b) $$

Thus, the number $ d $ is indeed a common divisor of $ a $ and $ b $.
Conclusion

Both implications form an equivalence:

$$ (d \mid a) \land (d \mid b) \Longleftrightarrow d \mid \delta $$

An integer $ d $ divides $ a $ and $ b $ if and only if it divides their GCD $ \delta $.

Therefore, we have finally proved that:

$$ \forall (a,b) \in (\mathbb{N}^*)^2, $$

$$ \mathcal{D}(a, b) = \mathcal{D}\bigl( PGCD(a, b) \bigr) $$

All these divisors can be found by prime factorization of the $ PGCD(a, b) $ .

Linearity

Let $(a, b) \in \hspace{0.04em}\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,

$$ \begin{cases} k \mid ka \\ k \mid kb \end{cases}\Longrightarrow k \mid \Delta $$

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

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

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

$$ \begin{cases} \Delta \mid ka \\ \Delta \mid kb \end{cases}$$

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

$$ \begin{cases} kc \mid ka \Longrightarrow c \mid a \\ kc \mid kb \Longrightarrow c \mid b \end{cases}$$

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

$$ \begin{cases} c \mid a \\ c \mid b \end{cases}\Longrightarrow c \mid \delta $$

Well,

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

Moreover,

$$ \begin{cases} \delta \mid a \Longrightarrow k\delta \mid ka \\ \delta \mid a \Longrightarrow k\delta \mid kb \end{cases}\Longrightarrow k\delta \mid \Delta \qquad (2) $$

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

$$ \begin{cases} \Delta \mid k \delta \qquad (1) \\ k\delta \mid \Delta \qquad (2) \end{cases}\Longrightarrow \Delta = k\delta $$

And finally,

$$ \forall (a, b) \in \hspace{0.04em}\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 following, the breakdown of $a $ and $b $ in prime factors :

$$ \forall n \in \mathbb{N}, \enspace n \geqslant 2, \enspace \exists! r \in \mathbb{N}^*, \enspace \exists! (p_1 < p_2 < ... < p_r) \in \mathbb{P}^r, \enspace \exists! (\alpha_1, \alpha_2, ..., \alpha_r) \in (\mathbb{N}^*)^r, \enspace \exists! (\beta_1, \beta_2, ..., \beta_r) \in (\mathbb{N}^*)^r, $$

$$ \begin{cases} a = p_1^{\alpha_1}p_2^{\alpha_2}...p_r^{\alpha_r} \\ b = p_1^{\beta_1}p_2^{\beta_2}...p_r^{\beta_r} \end{cases} $$

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 \ ... \ \times \hspace{0.2em} p_r^{min \{ \alpha_r, \beta_r\}} $$

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 \ ... \ \times \hspace{0.2em} p_r^{max \{ \alpha_r, \beta_r\}} $$

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 \ ... \ \times \hspace{0.2em} p_n^{min \{ \alpha_n, \beta_n\}} \times p_r^{max \{ \alpha_r, \beta_r\}} $$

$$ 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 \ ... \ \times \hspace{0.2em} p_r^{min \{ \alpha_r, \beta_r\} + max \{ \alpha_r, \beta_r\}} $$

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

$$ GCD(a, b) \times LCM(a, b) = p_1^{\alpha_1}p_1^{\beta_1} \times p_2^{\alpha_2} p_2^{\beta_2} \hspace{0.2em} \times \ ... \ \times \hspace{0.2em} p_r^{ \alpha_r}p_r^{ \beta_r} $$

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

$$ ab = p_1^{\alpha_1}p_1^{\beta_1} \times p_2^{\alpha_2} p_2^{\beta_2} \hspace{0.2em} \times \ ... \ \times \hspace{0.2em} p_r^{ \alpha_r}p_r^{ \beta_r} $$

And finally,

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

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

The properties of the GCD of two natural numbers

Equality between the successives GCD of the Euclid's algorithm

Breakdown in prime factors

Generalization by independence of prime factors

The Bézout's identity

if \( b \) divides \( a \)

if \( b \) does not divide \( a \)

if \( R_0 \) divide \( b \)

if \( R_0 \) does not divide \( b \)

if \( R_1 \) divides \( R_0 \)

if \( R_1 \) does not divide \( R_0 \)

Breakdown of two numbers in relation to their GCD

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

Forward direction: If \( d \) divides \( a \) and \( b \), then \( d \) divides \( \delta \)

Converse direction: If \( d \) divides \( \delta \), then \( d \) divides \( a \) and \( b \)

Conclusion

Linearity

Link between GCD and LCM

Recap table of the GCD properties