Cách tìm mong chung mập nhấtNhững lưu ý khi tìm ước chung mập nhấtCác thuật toán tìm mong chung mập nhất

Ước chung lớn số 1 là gì?

Ước chung lớn số 1 (ƯCLN) của hai hay nhiều số là số lớn số 1 trong tập hợp các ước chung của các số đó.

Bạn đang xem: Tìm ước chung lớn nhất

Trong tiếng Anh, mong chung lớn nhất gọi là greatest common factor (GCF).

Ký hiệu mong chung lớn nhất của a và b là ƯCLN(a,b).

Ví dụ: kiếm tìm Ư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 mong chung khủng nhất

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

Để tìm cầu chung lớn nhất của các số, ta tìm kiếm tập hợp các ước của từng số đó. Sau đó chọn ước chung bự nhất.

Ví dụ: tìm kiếm Ước chung lớn số 1 của nhì số tự nhiên và thoải mái 16 và 30.

Đầu tiên ta search 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: so sánh mỗi số ra vượt 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 những tích quá số sẽ chọn, từng thừa số rước với số mũ bé dại nhất của nó.

Tích đó là ƯCLN bắt buộc tìm.

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

12 = 2 x 2 x 3

30 = 2 x 3 x 5

Ta có: các thừa số nguyên tố bình thường là 2 và 3.

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

Cách 3: kiếm tìm ƯCLN bởi bội chung bé 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 phương pháp lấy tích của a với b phân chia cho bội chung bé dại nhất (BCNN) của a và 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 mong chung phệ nhất

Nếu trong số số sẽ cho có một số bằng 1 thì cầu chung to nhất của những số đó bằng 1.

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

Nếu những số đã mang đến mà không có thừa số nguyên tố chung thì ước chung lớn số 1 của số sẽ là 1.

Ví dụ: Số 5 với 8 không tồn tại thừa số yếu tắc chung đề xuất ƯCLN(5,8) = 1

Hai hay những số gồm ước chung lớn nhất bằng 1 được điện thoại tư vấn là đa số số nguyên tố thuộc nhau.

Ví dụ: ƯCLN (6,35) = 1 bắt buộc 6 với 35 là hai số nguyên tố thuộc nhau.

Trong những số đã cho, nếu gồm số bé dại nhất là ước của những số sót lại thì ước chung mập nhất của các số đang cho chính là số nhỏ tuổi nhất ấy.

Ví dụ: 5 hồ hết là ước của 5 và 15 bắt buộc ƯCLN(5,15) = 5

Tìm ƯỚC tầm thường và ƯỚC chung LỚN NHẤT phụ thuộc đị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 những ước chung của a, b, c được cam kết hiệu là:

ƯC(a, b, c)

Câu hỏi 1:

a) tra cứu Ư(12).

b) search Ư(30).

c) tra cứu Ư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 bộ phận chung của Ư(12) với Ư(30) là: 1; 2; 3; 6.

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

Cách tra cứu ƯC(a, b) – tập hợp những ước chung của a cùng b:

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

Câu hỏi 2:

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

b) tìm kiếm Ư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 phần tử 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 phần tử chung của tất cả ba tập Ư(18), Ư(36) và Ư(45) là: 1; 3 với 9.

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

Ước chung khủng nhất của a cùng b là số lớn số 1 trong tập hợp những ước phổ biến của a với b.

Ước chung lớn số 1 của a với b được cam kết hiệu là:

ƯCLN(a, b)

Câu hỏi 3:

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

b) 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 số 1 trong tập hợp ƯC(24, 30) vừa kiếm được là số 6.

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

Cách kiếm tìm ƯCLN(a, b):

Tìm ƯC(a, b);Tìm số lớn nhất trong tập hợp ƯC(a, b). Đó đó là ƯCLN(a, b)

Câu hỏi 4: tra cứu Ư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à 1 trong những tập hợp, còn ƯCLN(a, b) là một 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ố đã cho, giả dụ số bé dại nhất là ước của những số còn lại thì cầu chung béo nhất của các số đang cho đó là số nhỏ dại nhất ấy.

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

Câu hỏi 5:

a) tra cứu ƯCLN(199, 1);

b) search ƯCLN(6, 18).

Giải

a) ƯCLN(199, 1) = 1

b) vày 18 ⋮ 6 phải ƯCLN(6, 18) = 6.

Tìm ƯỚC phổ biến LỚN NHẤT bằng cách phân tích những số ra quá số nguyên tố

Sau đây là một cách khác nhằm tìm ước chung lớn nhất, vô cùng đắc dụng khi gặp các số a cùng b quá to hoặc có rất nhiều ước:

✨ mong tìm ước chung lớn nhất (ƯCLN) của nhì hay các số to hơn 1, ta tiến hành ba cách sau:

Bước 1: phân tích mỗi số ra quá số nguyên tố.Bước 2: lựa chọn ra những thừa số nguyên tố chung.Bước 3: Lập tích các thừa số vẫn chọn, từng thừa số mang với số mũ nhỏ duy nhất của nó. Tích chính là ƯCLN phải tìm.

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

Giải

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

45 = 32 . 5150 = 2 . 3 . 52

Bước 2: chọn ra các thừa số thành phần chung, đó là: 3 và 5.

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

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

Câu hỏi 7: tìm ƯCLN(56, 140, 168)

Giải

Bước 1: phân tích 56; 140 và 168 ra thừa số nguyên tố.

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

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

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

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

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

Câu hỏi 8: kiếm tìm ƯCLN(24, 25)

Giải

Phân tích 24 cùng 25 ra thừa số nguyên tố:

24 = 23 . 325 = 52

Vậy 24 cùng 25 không có thừa số thành phần 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 nhì hay các số phần đông là ước của ƯCLN của các số đó. Vậy ta bao gồm cách tra cứu ƯC dựa vào ƯCLN như sau:

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

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

Câu hỏi 9:

a) search ƯCLN(24, 72)

b) dựa vào câu a, hãy search ƯC(24, 72).

Giải

a) vày 72 ⋮ 24 yêu cầu Ư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: tìm Ư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 bác học:

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

Cách 1: tra cứu 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 số 1 ƯCLN(a, b):

Cách 1: tra cứu số lớn số 1 trong tập vừa lòng ước tầm thường ƯC(a, b).

Xem thêm: Mô Phỏng Lái Xe Lửa Thành Phố, Top 17 Tải Game Lái Tàu Hỏa Hay Nhất 2022

Cách 2: đối chiếu a và b ra vượt 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ề cầu chung phệ nhất

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

Dạng này bí quyết làm khá solo giản. Học tập sinh chỉ cần áp dụng 3 cách của cách tìm mong chung lớn nhất là rất có thể giải một biện pháp dễ dàng.

Ví dụ 1:Tìm mong chung lớn số 1 của (12, 30)

Ta có: 12 = 2×2 x 3

30 = 2 x 3 x 5

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

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

Ví dụ 2: kiếm tìm 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

*** bí quyết tìm cầu chung

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

Ví dụ: tra cứu ƯCLN rồi tìm những ước tầm thường của :

a) 16 và 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 chung của 16 cùng 24 chính là các cầu của 8. Đó là một trong ; 2 ; 4 cùng 8.

Đáp số :

ƯCLN(180 , 234) = 18. Những ước chung là một , 2 , 3 , 6 , 9 , 18.

ƯCLN(60 , 90 , 135) = 15. Những ước phổ biến là : 1 , 3 , 5 , 15.

Dạng 2: vấn đề đư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 viên cần phân tích đề bài, suy luận để đưa về việc tìm ƯCLN của nhì hay nhiều số.

Ví dụ:

Tìm số tự nhiên và thoải mái a lớn số 1 biết rằng 420 phân chia hết cho a với 700 phân chia hết cho a.

Giải

Theo đề bài bác a buộc phải là ƯCLN của 420 với 700.

ƯCLN(420, 700) = 140.

Vậy a = 140.

Dạng 3: Tìm những ước tầm thường của hai hay nhiều 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ố đến trước ;

– Tìm những ước của ƯCLN này ;

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

Ví dụ:

Mai với Lan mỗi người mua mang đến tổ mình một trong những hộp bút chì màu. Mai mua 28 bút, Lan sở hữu 36

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

a) gọi số bút trong những hộp là a. Tìm tình dục 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 bao nhiêu hộp bút chì màu sắc ? Lan mua từng nào hộp cây viết chì màu ?

Trả lời

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

b) a ∈ ƯC(28 , 36) với a > 2. Tự đó tìm kiếm được a = 4.0

c) Mai tải 7 hộp bút, Lan sở hữu 9 hộp bút.

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

Bài 1: Tìm những ước chung béo hon đôi mươi của 144 và 192 .

Giải

ƯCLN (144 ,192) = 48.

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

Các mong của 48 to hơn 20 là 24 và 48.

Vậy những ước chung khủng hon đôi mươi của 144 và 192 là 24 và 48.

Bài 2:.

Tìm số tự nhiên x, biết rằng 112 phân chia hết mang đến x , 140 phân chia hết mang đến x và 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ố thoải mái và tự nhiên a lớn nhất biết rằng 420 phân tách hết đến a với 700 phân tách hết mang đến a.

Giải

Theo đề bài a buộc 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 người vợ về một huyện nhằm biểu diễn. Mong mỏi phục vụ

đồng thời tại nhiều địa điểm, đội dự định tạo thành các tổ tất cả cả nam và nữ, số nam

được chia rất nhiều vào những tổ, số người vợ 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ổ bao gồm bao nhiêu nam, bao nhiêu cô gái ?

Đáp số

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

Bài 9:Tìm a, b biết a + b = 42 và = 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, giả sử a ≤ b => m ≤ n.

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

= mnd = 72 (2)

=> d là ước tầm thường của 42 với 72 => d ở trong 1; 2; 3; 6.

Lần lượt thay những giá trị của d vào (1) cùng (2) nhằm tính m, n ta thấy chỉ tất cả trường phù hợp d = 6 => m + n = 7 với mn = 12 => m = 3 cùng n = 4. (thỏa mãn các điều khiếu nại của m, n). Vậy d = 6 và 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: call d = (a, b) => a = md; b = nd cùng với m, n 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 thuộc 1; 7.

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

d = 7 => m – n = 1 với mn = đôi mươi => m = 5, n = 4

Vậy d = 7 cùng a = 5.7 = 35 ; b = 4.7 = 28 .

Các Dạng Toán:Dạng 1: tìm kiếm Ước chung to nhất của các số cho trước:Phương pháp: triển khai quy tắc ba bước đề tìm UCLN của nhị hay các số.Ví dụ 1: tì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ố thông thường là 2^4 = 16 Đây là UCLN của 3 số đang cho.b) 18 = 2.3^230 = 2.3.577 = 11.7Thừa số chung là 1 –> Đây cũng là UCLN bắt buộc tìm.Ví dụ 2: kiếm tìm UCLN rồi tìm những ước thông thường của:a) 16 với 24b) 180 với 234c) 60, 90 cùng 135Giải:a) 16 = 2^424 = 3.2^3–> UCLN(16,24) = 2^3 = 8.Các ước tầm thường của 16 cùng 24 chính là các ước của 8. Đó là: 1; 2; 4; 8.Phần b cùng c cô giáo môn toán lớp 6 chỉ gửi ra đáp án còn giải pháp giải ví dụ các em hãy tự có tác dụng và đọc thêm hướng dẫn của những gia sư nhé.b) UCLN(180,234). Những ước tầm thường là: 1; 2; 3; 6; 9; 18.c) UCLN(60, 90, 135). Những ước chung là: 1; 3; 5; 15.

Dạng 2: việc đưa về việc tìm và đào bới UCLN của nhị 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 các số.Ví dụ: tra cứu số thoải mái và tự nhiên a lớn số 1 biết rằng 420 | a với 700 | a.Giải:Theo đề bài bác a cần là UCLN(420,700) nhưng UCLN(420, 700) = 140. Vậy a = 140.Dạng 3: Tìm những ước chung của nhì hay những số vừa lòng điều kiện mang đến trước:Phương pháp:

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

Ví dụ: Tìm những ước chung lớn hơn 20 của 144 với 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 cùng 192 là 24 và 48.

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

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

Ước chung lớn nhất (GCD – Greatest Common Divisor) của 2 số nguyênavàblà số nguyên phệ nhấtdthỏa mãn đặc điểm cả a với b hầu như chia hết cho d.

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

Dưới đấy là một số biện pháp thường được áp dụng để giải quyết bài toán tìm mong chung lớn nhất của nhì số.

Cách 1. Tra cứu UCLN sử dụng phép trừ

Đây là sơ trang bị của thuật toán này

*
Thuật toán tìm cầu chung lớn số 1 sử dụng phép trừ

Code minh họa

*

Giải thích:

*

Cách 2. Tìm UCLN thực hiện phép phân chia dư

Sơ đồ vật thuật toán tựa như như cách 1. Chỉ biến hóa phép trừ lịch sự phép chia dư.

Code minh họa

*

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

Cho a, b là nhì số nguyên (giả sử a ≥ b), nhằm tìm cầu chung lớn nhất của nhị số a cùng b ta cần thực hiện chia a mang lại b được yêu quý q và số dư r (r ≥ 0) có nghĩa là a = b*q + r, lúc ấy ta có:

*
*

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

Để hoàn toàn có thể sử cần sử dụng hàm kiếm tìm ucln trong C++ ta đề xuất thêm thư việnalgorithm.