## Math 6 Chapter 1 Lesson 17: Greatest Common Divisor

## 1. Summary of theory Tóm

### 1.1. Common divisor

**Example 1: **We have

U(12) = {1, 2, 3, 4, 6, 12}

U(15) = {1, 3, 5, 15}

Note that the numbers 1, 3 are all divisors of 12 and 15, then we say “1 and 3 are common divisors of 12 and 15”.

From there, we have **define:**

Given two numbers a and b. If there is a number d satisfying:

\(a\, \vdots \,\,d\) and \(b\,\, \vdots \,\,d\)

then d is called a common divisor of a and b.

The set of common divisors of two numbers a and b is denoted UC(a; b).

**Attention: **We need to pay attention to:

* If \(x \in \) UCC(a, b, c,…) then \(a\,\, \vdots \,\,x,\,b\,\, \vdots \,\,x, \,\,c\,\, \vdots \,\,\,x,….\)

* If U(a, b) = 1, then a and b are said to be co-prime. Symbol (a, b) = 1

* UC(a, b) = U(a) \( \cap \) U(b).

### 1.2. Greatest common divisor

**Example 2:** We have:

UC(12; 15) = {1, 3}

then, we say 3 is the greatest common divisor of 12 and 15.

From there, we have **define**:

The greatest common divisor of a and b is the largest number in the set of common divisors of a and b. The symbol UCLN(a, b).

**Comment: **If \(a\,\, \vdots \,\,b\) then UCLN(a, b) = b

### 1.3. How to find UCL

**Problem: **CCLN (a, b, c, …)

**Solution method**

You can choose one of two ways:

**Method 1:** (Find the GCC by factoring the numbers into prime factors):

We follow these steps:

Step 1: Factor each number into prime factors.

Step 2: Pick out the common prime factors.

Step 3: Product of the common factors, each factor taken with the smallest exponent. That product is the GCLN to find.

**Method 2: **(Using Euclidean algorithm): We perform the following steps:

Step 1: Divide the large number by the small number. Suppose a = b .x + r

* If \(r \ne 0\) we perform step 2.

* If r = 0, then CCLN (a, b) = b.

Step 2: Take the divisor, divide by the remainder \(b{\rm{ }} = {\rm{ }}r{\rm{ }}.{\rm{ }}y{\rm{ }} + \ ,\,{r_1}\)

* If \({r_1} \ne 0\) we do step 3.

* If \({r_1} = 0\) then UCLN(a, b) = r.

Step 3: This process is continued until a divisibility is obtained.

### 1.4. GCC and divisibility

We have the following two observations:

1. If the number a is dead by m and n and m and n are both prime numbers, then a is divisible by the product mn

\(a\,\, \vdots \,\,m,a\,\, \vdots \,\,n\) and \((m,\,n) = 1 \Rightarrow a\,\, \vdots \,\,mn\)

2. If the product \(ab\, \vdots m\) where b and m are co-prime numbers, then a must be divisible by m.

\(ab\, \vdots m\) and \((b,m) = 1 \Rightarrow a\,\, \vdots \,\,m\)

**Example 3: **Given three numbers a = 28, b = 54, c = 96.

a. Find the set of divisors of a, b, c.

b. Find the set of common divisors of a, b, c.

c. Find the greatest common divisor of:

a and b b and c a, b and c

**Solution**

a. We have:

U(28) = {1, 2, 4, 7, 14, 28}

U(54) = {1, 2, 3, 6, 9, 18, 27, 54}

U(96) = {1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 96}

b. We have:

UC(28, 54, 96) = {1, 2}

c. We have:

\(\begin{array}{l}28 = {2^2}.7\\54 = {2.3^2}\\96 = {2^3}.3\end{array}\)

We get:

GCLN(a, b) = 2

UCLN(b,c) = \({2^2}\) =4

UCLN(a,b,c)=2.

**Example 4: **Use Euclidean algorithm to find:

a. CCC(174, 18)

b. CCC(124, 16)

**Solution**

a. We follow these steps:

* Taking 174 divided by 18, we get:

174 = 9 . 18 + 12

* Divide 18 by 12, we get:

18 = 1. 12 + 6

* Divide 12 by 6, we get:

12 = 2.6 + 0

So GCC(174.18) = 6

b. We follow these steps:

* Taking 124 divided by 16, we get:

124 = 7 . 16 + 12

* Divide 16 by 12, we get:

16 = 1 . 12 + 4

* Divide 12 by 4, we get:

12 = 3 . 4 + 0

So, GCLN(124, 16) = 4

## 2. Illustrated exercise

**Question 1: **In the year-end review, there were 135 notebooks, 80 rulers, and 169 ballpoint pens. The teacher divides the rewards into each other, each of which includes three categories. After dividing, there are 15 notebooks, 8 rulers and 1 ballpoint pen left over which are not enough to divide the prizes. How many prizes are there and how many notebooks, rulers, and ballpoint pens are there for each prize?

**Solution guide:**

Assume a is the number of rewards.

We have:

Number of books divided: 135 – 15 = 120.

Number of rulers divided: 80 – 8 = 72.

Number of ballpoint pens divided: 169 – 1 = 168.

Therefore, a = UC(72, 120, 168) and a > 15.

\( \Rightarrow a = 24.\)

So, there are 24 rewards. Each prize includes 5 notebooks, 3 rulers and 7 ballpoint pens.

**Verse 2: **Find the intersection of two sets A and B known:

a. A = {1, 4, 6} and B = {1, 2, 3, 5, 6, 7}

b. A is the set of even natural numbers and B is the set of odd natural numbers.

**Solution guide:**

a. We have:

A = {1, 4, 6} and B = {1, 2, 3, 5, 6, 7}

So \(A \cap B = {\rm{\{ }}1,6\} \)

b. We have:

A is the set of even natural numbers and B is the set of odd natural numbers.

So, \(A \cap B = \,\emptyset \)

**Question 3:** Let a and b be co-prime numbers. Prove that:

A = 8a + 3 and B = 5a + 2

are two co-prime numbers.

**Solution guide:**

Let d be a common divisor of two numbers A and B.

Therefore:

\((8a + 3b) \vdots d\) and \((5a + 2b) \vdots d \Rightarrow 5(8a + 3b) \vdots d\) and \(8(5a + 2b) \vdots d\)

\( \Rightarrow 8(5a + 2b) – 5(8a + 3b)\,\, \vdots \,\,d \Rightarrow \,b\,\, \vdots \,\,d\) (1)

Again there are:

\(2(8a + 3b) \vdots d\) and \(3(5a + 2b)\,\, \vdots \,\,d\)

\( \Rightarrow 2(8a + 3b) – 3(5a + 2b)\,\, \vdots \,\,d\, \Rightarrow a\,\, \vdots \,\,d\) (2)

From (1) and (2) it follows that:

d = UC(a, b)

Which (a,b) = 1 \( \Rightarrow \) d = 1 \( \Rightarrow \) UC(8a + 3b, 5a + 2b) = 1.

So, the two numbers A = 8a + 3b and B = 5a + 2b are co-prime

## 3. Practice

### 3.1. Essay exercises

**Question 1: **Find the greatest common divisor of

a) 60 and 80

b) 24; 60; 72

**Verse 2:** Find the greatest common divisor and then find the common divisor of 90 and 120.

**Question 3:** Find the natural number x knowing that \(126 \vdots x;\,\,\,210 \vdots x\) and \(15 < x < 30\)

### 3.2. Multiple choice exercises Bài

**Question 1: **Find the CCLN (210, 30, 1)?

A. 1

B. 30

C. 15

D. 210

**Verse 2: **Find the GCC (84, 168)

A. 12

B. 21

C. 28

D. 84

**Question 3: **Find UC(12; 30)?

A. {1; 2; 6}

B. { 3; 6}

C. {1; 2; 3; 6}

D. {0; 2; 3; 6}

**Question 4: **Find a natural number a knowing that 264 divides a remainder 24 and 363 divides a remainder 43

A. 20

B. 40

C. 60

D. 80

**Question 5: **Find the GCC (48; 168; 360)

A. 24

B. 45

C. 168

D. 40

## 4. Conclusion

Through this Greatest Common Divisor lesson, you need to accomplish some of the goals that the lesson gives, such as:

.

=============

## Leave a Reply