Euler's Eyes
2022-07-10
Greatest Common Divisor
Check out the discovery
The last non-zero remainder was 6, which is the GCD. A square with sides 6 also allows you to cover a rectangle with sides 24 and 18 without excess.
In the prime numbers post, we talked about divisor sets. For example, given a natural number $a$, the set of divisors of natural numbers is given by:
$$\mathcal{D}(a) $$for any non-zero number $a$. Also, we saw that 1 always belongs to the set $\mathcal{D}(a)$, and $a$ too.
Finding the divisors of a natural number
Therefore, the set of divisors of a number $a$ is finite. In other words, we have:
$$1\in \mathcal{D}(a) = \\{1,\dots, a\\}$$$$a\in \mathcal{D}(a) = \\{1,\dots, a\\}$$
In this way, the intersection of the divisors between any two natural numbers $a$ and $b$ has a maximum element, that is:
$$\mathcal{D}(a)\cap \mathcal{D}(b)\quad \Rightarrow \quad \text{tem um elemento máximo, para a e b natural.}$$Speaking of maximum, today’s tribute goes to Atobe Keigo from Princípe do Tennis. Below we look at a ebay figure, the credits for the Atobe figure are fansub site.
| Atobe Keigo | I am the Maximum |
|---|---|
|
|
Definition of greatest common divisor
If the meeting (intersection) between the divisors of any (non-zero) natural numbers has a maximum. Then we can define:
Definition:
Given natural numbers $a$ and $b$ any non-null (non-zero). The sets of the intersection (“meeting”) of the divisors of $a$ and $b$
$$\mathcal{D}(a)\cap \mathcal{D}(b)$$has a maximum element, which we call the greatest common divisor of $a$ and $b$.
$$mdc(a, b) = \max \\{\mathcal{D}(a)\cap \mathcal{D}(b) \\}$$
Example of greatest common divisor
Given natural numbers 12 and 18, what is the greatest common divisor of 12 and 18?
$$mdc(12,18) = ?$$| Natural number $(n)$ | $\mathcal{D}(n)$ | Dividers |
|---|---|---|
| 12 | $\mathcal{D}(12)$ | $ \\{ 1,2, 3, 4, 6, 12 \\} $ |
| 18 | $\mathcal{D}(18)$ | $ \\{ 1,2, 3, 6, 9, 18 \\} $ |
The next step is to check the intersection between the divisors of $12$ and $18$. From this, we get:
| $\mathcal{D}(12) \cap \mathcal{D}(18)$ | $mdc(12,18)$ |
|---|---|
| $ \\{ 1,2, 3, 6 \\} $ | $ \max \\{ 1,2, 3, 6 \\} = 6 $ |
Therefore, the greatest common divisor of $12$ and $18$ is $6$.
$$mdc(12, 18) = 6$$Greatest Common Divisor Properties
Below we present the properties of greatest common divisor:
- For any two non-zero natural numbers $a$ and $b$, it is valid: $$mdc(a,b) = mdc(b,a)$$
For example, for $a = 12$ and $b = 18$
$$mdc(12,18) = mdc(18,12)=6$$| $mdc(12,18)$ | $mdc(18,12)$ |
|---|---|
|
|
|
- For a non-zero natural number $a$ $(a\neq 0)$ divisor of $b$, then $mdc(a,b)=a$
For example, for $a = 6$ and $b = 18,$ we note that 6 is a divisor of 18. Like this:
$$mdc(6,18) = 6$$
- For any two non-zero natural numbers $a$ and $b$, if
So $a$ and $b$ are prime numbers.
For example, for $a = 2$ and $b = 3$ we have:
$$mdc(2,3) = 1$$Therefore, 2 and 3 are primes.
Geometric example of greatest common divisor
To show the greatest common divisor method, we use Euclid’s method. Let $a$ and $b$ be non-zero natural numbers. Suppose $a=77$ and $b=21$.
The method is based on covering the rectangular region with squares, where the sides are natural numbers. This way, we just need to calculate $mdc(77,21) = 7$
The greatest common divisor between 77 and 21 obtained by the geometric method is given by:
IMPA and the MDC
- Impa Portal: Greatest Common Divisor
- Impa Portal: Properties of the Greatest Common Divisor
This is a short summary of greatest common divisor (gcd). In the next post we will present the least common multiple.