Кестені толтыр. T
31
32
у
4,04
х+ у
731
531
Т – у
у
х: у
у
у
у
—​

16|2                                       36|2                                 630|2
  8|2                                       18|2                                 315|3
  4|2                                         9|3                                 105|3
  2|2                                         3|3                                   35|5
  1|                                           1|                                       7|7
16=2*2*2*2                            36=2*2*3*3                         1|
                                                                                       630=2*3*3*5*7
48|2                                        63|3
24|2                                        21|3
12|2                                          7|7
  6|2                                          1|
  3|3                                         63=3*3*7
  1
48=2*2*2*2*3

90|2                                          990|2
45|3                                          495|3
15|3                                          165|3
  5|5                                            55|5
  1|                                              11|11
90=2*3*3*5                                  1|
                                                  990=2*3*3*5

Примеры:
а) найти НОД (6600; 6300):
6600 = 2 • 2 • 2 • 3 • 5 • 5 • 11,
6300 = 2 • 2 • 3 • 3 • 5 • 5 • 7,
НОД (6600; 6300) = 2 • 2 • 3 • 5 • 5 = 300;
б) найти НОД (34 398; 1260; 6552):
34 398 - 2 • 3 • 3 • 3 • 7 • 7 • 13,
1260 = 2 • 2 • 3 • 3 • 5 • 7,
6562 = 2 • 2 • 2 • 3 • 3 • 7 • 13,
НОД (34 398; 1260; 6652) = 2 • 3 • 3 • 7 = 126.
При нахождении наибольшего общего делителя двух чисел полезно знать еще одно правило, называемое «алгоритмом Евклида» .
Пример. Найти НОД (270; 186). Разделим 270 на 186 с остатком:
270 : 186 = 1 (ост. 84). Далее разделим делитель на остаток и т. д. : 186 : 84 = 2 (ост. 18), 84 : 18 = 4 (ост. 12), 18 : 12 = 1 (ост. 6), 12 : 6 = 2 (ост. 0).
Наибольшим общим делителем чисел 270 и 186 является последний ненулевой остаток, т. е. число 6.
Пример. Найти НОД (234; 180).
1)234 : 180 = 1 (ост. 54),
2)180: 54 = 3 (ост. 18),
3)54 : 18 = 3 (ост. 0). Следовательно, НОД (234; 180) = 18.
Натуральные числа называют взаимно простыми, если их наибольший общий делитель равен единице.
Примеры:
а) 75 и 14 — взаимно простые числа, так как НОД (75; 14)= 1;
б) 20, 9 и 77 взаимно простые числа, так как НОД (20; 9; 77) =