Наибольший общий делитель

делители числа 42

1; 2; 3; 6; 7; 14; 21; 42

Красным цветом выделены числа 1; 2; 7; 14 – которые являются общими делителями чисел 28 и 42

Среди общих делителей число 14
является наибольшим

чисел, называют наибольшим общим делителем (НОД) этих чисел

НОД чисел a и b обозначают НОД (a;b )

НОД (28; 42) = 14

Легко установить, что НОД (10;25 )=5,
НОД (18;24 )=6, НОД (3;7)=1

НОД (455; 770)
455 5
91 7
13 13
1
770 2
385 5
77 7
11 11
1
НОД (455; 770) = 5 ∙ 7 = 35

840 2
420 2
210 2
105 3
35 5
7 7
1
НОД (455; 770) = 2 ∙ 2 ∙ 3 ∙ 5 = 60
180 = 2 ∙ 2 ∙ 3 ∙ 3 ∙ 5 840 = 2 ∙ 2 ∙ 2 ∙ 3 ∙ 5 ∙ 7

2
154 2
77 7
11 11
1
НОД (585; 616) = 1
585 = 3 ∙ 3 ∙ 5 ∙ 13 616 = 2 ∙ 2 ∙ 2 ∙ 7 ∙ 11

Если общий делитель двух натуральных чисел равен 1, то их называют взаимно простыми

так как число 250 – делитель 3000
НОД (250; 3000) = 250

2
90 2
45 3
15 3
5 5
1
144 2
72 2
36 2
18 2
9 3
3 3
1
132 = 2 ∙ 2 ∙ 3 ∙ 11 180 = 2 ∙ 2 ∙ 3 ∙ 3 ∙ 5 144 = 2 ∙ 2 ∙ 2 ∙ 2∙ 3 ∙ 3

НОД (132; 180; 144) = 2 ∙ 2 ∙ 3 = 12