Cách tìm mong chung to nhấtNhững xem xét khi tìm mong chung bự nhấtCác thuật toán tìm mong chung khủng nhất

Ước chung lớn nhất là gì?

Ước chung lớn số 1 (ƯCLN) của nhì hay các số là số lớn số 1 trong tập hợp những ước chung của các số đó.

Bạn đang xem: Cách tính ước chung lớn nhất

Trong tiếng Anh, mong chung lớn số 1 gọi là greatest common factor (GCF).

Ký hiệu mong chung lớn số 1 của a với b là ƯCLN(a,b).

Ví dụ: search ƯCLN(24, 16, 32)

Ư(24) = 1, 2, 3, 4, 6, 8, 12, 24

Ư(16) = 1, 2, 4, 8, 16

Ư(32) = 1, 2, 4, 8, 16, 32

Vậy ƯCLN(24, 16, 32) = 8

Cách tìm cầu chung mập nhất

Cách 1: Liệt kê những ước chung của các số rồi chọn ra ƯCLN

Để tìm ước chung lớn nhất của những số, ta kiếm tìm tập hợp các ước của từng số đó. Tiếp nối chọn ước chung phệ nhất.

Ví dụ: tra cứu Ước chung lớn nhất của nhị số tự nhiên và thoải mái 16 và 30.

Đầu tiên ta tra cứu tập hợp những ước của 16 và 30.

Ư(15) = 1, 2, 4 , 8, 16

Ư(30) = 1 , 2 , 3 , 5 , 6 , 10 , 15 , 30

Vậy ƯCLN (16,30) = 2

Cách 2: Phân tích các số ra thừa số nguyên tố

Bước 1: phân tích mỗi số ra thừa số nguyên tố.

Bước 2: lựa chọn ra những thừa số yếu tố chung.

Bước 3: Lập tích các tích quá số sẽ chọn, từng thừa số mang với số mũ bé dại nhất của nó.

Tích sẽ là ƯCLN buộc phải tìm.

Ví dụ: search ƯCLN(12, 30)

12 = 2 x 2 x 3

30 = 2 x 3 x 5

Ta có: những thừa số nguyên tố tầm thường là 2 cùng 3.

Vậy ƯCLN(12, 30) = 2 x 3 = 6

Cách 3: search ƯCLN bằng bội chung nhỏ dại nhất (BCNN) (điều kiện a, b không giống 0)

Ước chung lớn số 1 của a với b rất có thể tính bằng cách lấy tích của a và b phân chia cho bội chung nhỏ nhất (BCNN) của a cùng b.

Ví dụ: kiếm tìm ƯCLN(12, 30)

B(12) = 0, 12, 24, 36, 48, 60,…

B(30) = 0, 30, 60,…

Ta có: BCNN(12,30) = 60

Vậy ƯCLN(12,30) = 12.30:60 = 6

Những để ý khi tìm cầu chung phệ nhất

Nếu trong những số sẽ cho có một số bởi 1 thì mong chung béo nhất của các số đó bởi 1.

Ví dụ: ƯCLN(1, 55, 95) = 1

Nếu những số đã cho mà không tồn tại thừa số nguyên tố tầm thường thì mong chung lớn nhất của số chính là 1.

Ví dụ: Số 5 và 8 không có thừa số yếu tố chung đề nghị ƯCLN(5,8) = 1

Hai hay nhiều số có ước chung lớn nhất bằng 1 được gọi là đầy đủ số nguyên tố thuộc nhau.

Ví dụ: ƯCLN (6,35) = 1 yêu cầu 6 và 35 là hai số nguyên tố thuộc nhau.

Trong những số đang cho, nếu bao gồm số bé dại nhất là ước của các số sót lại thì mong chung béo nhất của các số vẫn cho đó là số bé dại nhất ấy.

Ví dụ: 5 phần nhiều là ước của 5 với 15 đề nghị ƯCLN(5,15) = 5

Tìm ƯỚC phổ biến và ƯỚC chung LỚN NHẤT phụ thuộc vào định nghĩa

Tập hợp các ước chung của hai số a cùng b được ký kết hiệu là:

ƯC(a, b)

✨ Tương tự, tập hợp các ước chung của a, b, c được cam kết hiệu là:

ƯC(a, b, c)

Câu hỏi 1:

a) tìm Ư(12).

b) tìm kiếm Ư(30).

c) search ƯC(12, 30).

Giải

a) Ư(12) = 1; 2; 3; 4; 6; 12

b) Ư(30) = 1; 2; 3; 5; 6; 10; 15; 30

c) Các thành phần chung của Ư(12) và Ư(30) là: 1; 2; 3; 6.

Vậy ƯC(12, 30) = 1; 2; 3; 6

Cách tìm ƯC(a, b) – tập hợp các ước tầm thường của a cùng b:

Viết tập hợp những ước của a và ước của b: Ư(a), Ư(b);Tìm những phần tử chung của Ư(a) với Ư(b). Đây cũng chính là những phần tử của ƯC(a, b).

Câu hỏi 2:

a) kiếm tìm ƯC(30, 45).

b) search ƯC(18, 36, 45).

Giải

a) Ta có:

Ư(30) = 1; 2; 3; 5; 6; 10; 15; 30

Ư(45) = 1; 3; 5; 9; 15; 45

Các thành phần chung của Ư(30) cùng Ư(45) là: 1; 3; 5; 15.

Vậy: ƯC(30, 45) = 1; 3; 5; 15

b) Ta có:

Ư(18) = 1; 2; 3; 6; 9; 18

Ư(36) = 1; 2; 3; 4; 6; 9; 12; 18; 36

Ư(45) = 1; 3; 5; 9; 15; 45

Các thành phần chung của tất cả ba tập Ư(18), Ư(36) cùng Ư(45) là: 1; 3 với 9.

Vậy: ƯC(18, 36, 45) = 1; 3; 9

Ước chung mập nhất của ab là số lớn số 1 trong tập hợp những ước bình thường của a với b.

Ước chung lớn số 1 của ab được ký hiệu là:

ƯCLN(a, b)

Câu hỏi 3:

a) kiếm tìm ƯC(24, 30).

b) kiếm tìm ƯCLN(24, 30).

Giải

a) Ta có:

Ư(24) = 1; 2; 3; 4; 6; 8; 12; 24

Ư(30) = 1; 2; 3; 5; 6; 10; 15; 30

Do đó:

ƯC(24, 30) = 1; 2; 3; 6

b) Số lớn nhất trong tập thích hợp ƯC(24, 30) vừa kiếm được là số 6.

Vậy ƯCLN(24, 30) = 6.

Cách search ƯCLN(a, b):

Tìm ƯC(a, b);Tìm số lớn số 1 trong tập đúng theo ƯC(a, b). Đó đó là ƯCLN(a, b)

Câu hỏi 4: search ƯCLN(18, 30).

Giải

Ta có:

Ư(18) = 1; 2; 3; 6; 9; 18

Ư(30) = 1; 2; 3; 5; 6; 10; 15; 30

Do đó:

ƯC(18, 30) = 1; 2; 3; 6

Số lớn số 1 trong tập ƯC(18, 30) là 6.

Vậy ƯCLN(18, 30) = 6.

✨ ƯC(a, b) là một trong những tập hợp, còn ƯCLN(a, b) là 1 trong con số.

✨ với đa số số tự nhiên a và b, ta có:

ƯCLN(a, 1) = 1;

ƯCLN(a, b, 1) = 1

✨ trong các số đang cho, ví như số nhỏ tuổi nhất là ước của những số còn lại thì cầu chung mập nhất của những số vẫn cho đó là số nhỏ tuổi nhất ấy.

Nếu a ⋮ b thì ƯCLN(a, b) = b.

Câu hỏi 5:

a) search ƯCLN(199, 1);

b) tìm ƯCLN(6, 18).

Giải

a) ƯCLN(199, 1) = 1

b) vì chưng 18 ⋮ 6 nên ƯCLN(6, 18) = 6.

Tìm ƯỚC bình thường LỚN NHẤT bằng cách phân tích các số ra thừa số nguyên tố

Sau đây là một phương pháp khác để tìm ước chung béo nhất, rất đắc dụng khi chạm chán các số a cùng b quá rộng hoặc có vô số ước:

✨ mong muốn tìm ước chung khủng nhất (ƯCLN) của hai hay nhiều số to hơn 1, ta thực hiện ba cách sau:

Bước 1: phân tích mỗi số ra vượt số nguyên tố.Bước 2: chọn ra các thừa số yếu tắc chung.Bước 3: Lập tích những thừa số đã chọn, từng thừa số rước với số mũ nhỏ độc nhất của nó. Tích đó là ƯCLN cần tìm.

Câu hỏi 6: kiếm tìm ƯCLN(45, 150)

Giải

Bước 1: so với 45 cùng 150 ra quá số nguyên tố.

45 = 32 . 5150 = 2 . 3 . 52

Bước 2: chọn ra những thừa số nhân tố chung, đó là: 3 với 5.

Bước 3: Số mũ bé dại nhất của 3 là 1. Số mũ bé dại nhất của 5 là 1.

Vậy: ƯCLN(45, 150) = 3 . 5 = 15

Câu hỏi 7: tra cứu ƯCLN(56, 140, 168)

Giải

Bước 1: phân tích 56; 140 cùng 168 ra quá số nguyên tố.

56 = 23 . 7140 = 22 . 5 . 7168 = 23 . 3 . 7

Bước 2: lựa chọn ra những thừa số nguyên tố chung, kia là: 2 với 7.

Bước 3: Số mũ nhỏ tuổi nhất của 2 là 2. Số mũ nhỏ dại nhất của 7 là 1.

Vậy: ƯCLN(56, 140, 168) = 22 . 7 = 28

✨ sau khi phân tích những số ra quá số nguyên tố, nếu bọn chúng không tất cả thừa số yếu tắc chung thì ƯCLN của chúng bởi 1.

Câu hỏi 8: tra cứu ƯCLN(24, 25)

Giải

Phân tích 24 với 25 ra vượt số nguyên tố:

24 = 23 . 325 = 52

Vậy 24 và 25 không có thừa số nhân tố chung.

Do đó, ƯCLN(24, 25) = 1

Tìm ƯỚC CHUNG dựa vào ƯỚC tầm thường LỚN NHẤT

Tất cả các ước bình thường (ƯC) của hai hay những số phần đa là cầu của ƯCLN của những số đó. Vậy ta bao gồm cách tìm kiếm ƯC phụ thuộc vào ƯCLN như sau:

✨ mong muốn tìm ƯC của nhị hay những số lớn hơn 1, ta làm cho hai bước sau:

Bước 1: kiếm tìm ƯCLN của những số đó.Bước 2: kiếm tìm tập hợp các ước của ƯCLN đó. Đây cũng đó là tập hợp đề xuất tìm.

Câu hỏi 9:

a) tra cứu ƯCLN(24, 72)

b) phụ thuộc câu a, hãy tra cứu ƯC(24, 72).

Giải

a) vì chưng 72 ⋮ 24 bắt buộc ƯCLN(24, 72) = 24.

b) Ước bình thường của 24 cùng 72 là ước của ƯCLN(24, 72).

Vậy: ƯC(24, 72) = Ư(24) = 1; 2; 3; 4; 6; 8; 12; 24

Câu hỏi 10: search ƯC(72, 180)

Giải

Ta có:

72 = 23 . 32180 = 22 . 32 . 5

Do đó:

ƯCLN(72, 180) = 22 . 32 = 36

Vậy:

ƯC(72, 180) = Ư(36) = 1; 2; 3; 4; 6; 9; 12; 18; 36

Tóm lược bài học:

Cách search ước tầm thường ƯC(a, b):

Cách 1: search các thành phần chung của Ư(a) và Ư(b).Cách 2: Tìm những ước của ƯCLN(a, b).

Cách tìm ước chung lớn nhất ƯCLN(a, b):

Cách 1: search số lớn số 1 trong tập vừa lòng ước tầm thường ƯC(a, b).Cách 2: phân tích a cùng b ra quá số nguyên tố.

Bài tập áp dụng

Bài tập 1: Tìm:

a) ƯCLN(1, 49);

b) ƯCLN(15, 30);

c) ƯCLN(27, 35);

d) ƯCLN(84, 156).

Bài tập 2: Tìm:

a) ƯC(28, 42);

b) ƯC(180, 234).

*
*
*
*
*

Các dạng toán về mong chung to nhất

Dạng 1: Tìm ước chung khủng nhất của các số đến trước

Dạng này cách làm khá đối chọi giản. Học sinh chỉ việc áp dụng 3 cách của biện pháp tìm ước chung lớn nhất là có thể giải một biện pháp dễ dàng.

Ví dụ 1:Tìm ước chung lớn nhất của (12, 30)

Ta có: 12 = 2×2 x 3

30 = 2 x 3 x 5

Ta có những thừa sừa số nguyên tố phổ biến là 2 cùng 3

=> Ước chung lớn số 1 (UCLN) (12, 30) = 2 x 3 = 6

Ví dụ 2: search UCLN (8, 9); UCLN (8, 12, 15); UCLN (24, 16, 8)

UCLN (8, 9) = 1

UCLN (8, 12, 15) = 1

UCLN (24, 16, 8) = 8

*** phương pháp tìm mong chung

Muốn tìm mong chung của các số đã cho ta rất có thể tìm các ước của ƯCLN của các số đó.Như vậy, tập hợp các ước chung của những số đã cho rằng tập hợp những ước của ƯCLN của các số đó.

Ví dụ: tìm ƯCLN rồi tìm các ước thông thường của :

a) 16 cùng 24 ; b) 180 với 234 ; c) 60, 90 cùng 135.

Giải

16 = 24; 24 = 23.3 ;

ƯCLN(16,24) = 23= 8.

Các ước bình thường của 16 với 24 đó là các mong của 8. Đó là 1 ; 2 ; 4 và 8.

Đáp số :

ƯCLN(180 , 234) = 18. Các ước chung là 1 trong , 2 , 3 , 6 , 9 , 18.

ƯCLN(60 , 90 , 135) = 15. Những ước thông thường là : 1 , 3 , 5 , 15.

Dạng 2: câu hỏi đưa về việc tìm và đào bới ước chung lớn nhất của nhị số

Ở dạng này, học sinh cần đối chiếu đề bài, suy luận để lấy về việc đào bới tìm kiếm ƯCLN của nhị hay các số.

Ví dụ:

Tìm số tự nhiên a lớn nhất biết rằng 420 phân chia hết mang lại a cùng 700 phân chia hết cho a.

Giải

Theo đề bài bác a yêu cầu là ƯCLN của 420 với 700.

ƯCLN(420, 700) = 140.

Vậy a = 140.

Dạng 3: Tìm các ước chung của hai hay các số vừa lòng điều kiện cho trước

Phương pháp giải

– tra cứu ƯCLN của hai hay nhiều số cho trước ;

– Tìm các ước của ƯCLN này ;

– Chọn trong các đó những ước thỏa mãn điều kiện đang cho.

Ví dụ:

Mai với Lan mọi cá nhân mua mang đến tổ mình một số hộp cây bút chì màu. Mai cài 28 bút, Lan download 36

bút. Số bút trong số hộp cây viết đều đều nhau và số bút trong mỗi hộp to hơn 2.

a) hotline số bút trong những hộp là a. Tìm quan hệ giữa số a với mỗi số 28, 36, 2.

b) tra cứu số a nói trên.

c) Hỏi Mai mua từng nào hộp bút chì màu ? Lan mua bao nhiêu hộp cây bút chì color ?

Trả lời

a) a là ước của 28, a là ước của 36, a > 2.

b) a ∈ ƯC(28 , 36) cùng a > 2. Tự đó tìm được a = 4.0

c) Mai download 7 hộp bút, Lan tải 9 vỏ hộp bút.

Bài tập vận dụng

Bài 1: Tìm những ước chung mập hon 20 của 144 và 192 .

Giải

ƯCLN (144 ,192) = 48.

Ư(48) = 1 ; 2 ; 3 ; 4 ; 6 ; 8 ; 12 ; 16 ; 24 ; 48.

Các cầu của 48 to hơn 20 là 24 với 48.

Vậy các ước chung mập hon 20 của 144 với 192 là 24 cùng 48.

Bài 2:.

Tìm số tự nhiên x, hiểu được 112 phân tách hết mang lại x , 140 phân tách hết cho x với 10 3.7 ; 140 =22.5.7.

ƯCLN(56,140) = 22.7 = 28 .

Đáp số : b) 12 ; c) 60 ; d) 1.

Bài 6:

Tìm ƯCLN của :

a) 16, 80, 176; b) 18, 30, 77.

Đáp số

a) 16 ; b) 1

Bài 7:

Tìm số tự nhiên và thoải mái a lớn nhất biết rằng 420 phân chia hết mang đến a cùng 700 chia hết mang đến a.

Giải

Theo đề bài bác a phải là ƯCLN của 420 cùng 700.

ƯCLN(420, 700) = 140.

Vậy a = 140.

Bài 8:

Đội âm nhạc của một trường gồm 48 nam với 72 bạn nữ về một huyện nhằm biểu diễn. Ao ước phục vụ

đồng thời tại nhiều địa điểm, nhóm dự định chia thành các tổ gồm cả nam cùng nữ, số nam

được chia đông đảo vào những tổ, số nàng cũng vậy.

Có thể chia được rất nhiều nhất thành bao nhiêu tổ ?

Khi kia mỗi tổ có bao nhiêu nam, bao nhiêu nữ ?

Đáp số

Số tổ những nhất là ƯCLN (48,72) = 24. Lúc ấy mỗi tổ bao gồm 2 năm, 3nữ.

Bài 9:Tìm a, b biết a + b = 42 với = 72.

Lời giải:Gọi d = (a, b) => a = md; b = nd cùng với m, n nằm trong Z+; (m, n) = 1.

Không mất tính tổng quát, mang sử a ≤ b => m ≤ n.

Do đó: a + b = d(m + n) = 42 (1)

= mnd = 72 (2)

=> d là ước bình thường của 42 cùng 72 => d thuộc 1; 2; 3; 6.

Lần lượt thay các giá trị của d vào (1) và (2) nhằm tính m, n ta thấy chỉ gồm trường phù hợp d = 6 => m + n = 7 với mn = 12 => m = 3 cùng n = 4. (thỏa mãn những điều khiếu nại của m, n). Vậy d = 6 với a = 3.6 = 18 , b = 4.6 = 24

Bài 10:Tìm a, b biết a – b = 7, = 140.

Lời giải: gọi d = (a, b) => a = md; b = nd với m, n trực thuộc Z+; (m, n) = 1.

Do đó: a – b = d(m – n) = 7 (1’)

= mnd = 140 (2’)

=> d là ước bình thường của 7 và 140 => d ở trong 1; 7.

Thay lần lượt các giá trị của d vào (1’) với (2’) nhằm tính m, n ta được công dụng duy nhất:

d = 7 => m – n = 1 với mn = 20 => m = 5, n = 4

Vậy d = 7 với a = 5.7 = 35 ; b = 4.7 = 28 .

Các Dạng Toán:Dạng 1: search Ước chung to nhất của những số đến trước:Phương pháp: thực hiện quy tắc tía bước đề tra cứu UCLN của nhì hay các số.Ví dụ 1: tìm kiếm UCLN của:a) 16, 80, 176b) 18, 30, 77.Giải:a) 16 = 2^480 = 5.2^4176 = 11.2^4Thừa số bình thường là 2^4 = 16 Đây là UCLN của 3 số đã cho.b) 18 = 2.3^230 = 2.3.577 = 11.7Thừa số chung là 1 trong –> Đây cũng chính là UCLN nên tìm.Ví dụ 2: tra cứu UCLN rồi tìm những ước phổ biến của:a) 16 và 24b) 180 với 234c) 60, 90 với 135Giải:a) 16 = 2^424 = 3.2^3–> UCLN(16,24) = 2^3 = 8.Các ước chung của 16 cùng 24 đó là các mong của 8. Đó là: 1; 2; 4; 8.Phần b cùng c thầy giáo môn toán lớp 6 chỉ chuyển ra giải đáp còn bí quyết giải cụ thể các em hãy tự có tác dụng và tham khảo thêm hướng dẫn của những gia sư nhé.b) UCLN(180,234). Các ước tầm thường là: 1; 2; 3; 6; 9; 18.c) UCLN(60, 90, 135). Các ước thông thường là: 1; 3; 5; 15.

Dạng 2: bài toán đưa về việc tìm UCLN của hai hay những số.Phương pháp:Phân tích đề bài, suy luận để mang về việc tìm và đào bới UCLN của nhì hay nhiều số.Ví dụ: tìm số thoải mái và tự nhiên a lớn số 1 biết rằng 420 | a và 700 | a.Giải:Theo đề bài xích a yêu cầu là UCLN(420,700) nhưng mà UCLN(420, 700) = 140. Vậy a = 140.Dạng 3: Tìm những ước bình thường của nhì hay nhiều số thỏa mãn điều kiện đến trước:Phương pháp:

Tìm UCLN của hai hay nhiều số mang đến trước;Tìm những ước của UCLN này;Chọn trong đó các ước thỏa mãn điều kiện sẽ cho.

Ví dụ: Tìm các ước chung to hơn 20 của 144 và 192.Hướng dẫn giải:UCLN(144, 192) = 48.Ước của 48 = 1; 2; 3; 4; 6; 8; 12; 24; 48Các mong của 48 to hơn 20 là 24 cùng 48.Vậy các ước chung to hơn 20 của 144 và 192 là 24 với 48.

Thuật toán tìm mong chung lớn số 1 trong C/C++

Định nghĩa mong chung mập nhất

Ước chung lớn số 1 (GCD – Greatest Common Divisor) của 2 số nguyênavàblà số nguyên phệ nhấtdthỏa mãn tính chất cả a cùng b đông đảo chia hết cho d.

Các thuật toán tìm mong chung to nhất

Dưới đó là một số giải pháp thường được sử dụng để xử lý bài toán tìm mong chung lớn nhất của hai số.

Cách 1. Search UCLN áp dụng phép trừ

Đây là sơ đồ của thuật toán này

*
Thuật toán tìm mong chung lớn nhất sử dụng phép trừ

Code minh họa

*

Giải thích:

*

Cách 2. Tra cứu UCLN thực hiện phép chia dư

Sơ đồ thuật toán tương tự như phương pháp 1. Chỉ đổi khác phép trừ sang trọng phép phân chia dư.

Xem thêm: Đề Thi Học Kì 2 Môn Toán Lớp 4 Có Lời Giải, Đề Thi Toán Lớp 4 Học Kì 2 Năm 2021

Code minh họa

*

Cách 3. Kiếm tìm UCLN sử dụng lời giải Euclid

Cho a, b là hai số nguyên (giả sử a ≥ b), nhằm tìm mong chung lớn số 1 của nhì số a với b ta cần triển khai chia a cho b được thương q cùng số dư r (r ≥ 0) tức là a = b*q + r, lúc đó ta có:

*
*

Cách 4. Search UCLN áp dụng hàm gồm sẵn của C++

Để rất có thể sử cần sử dụng hàm tra cứu ucln trong C++ ta đề nghị thêm thư việnalgorithm.