Как найти наибольший общий делитель двух чисел
Автор Аронов Владислав задал вопрос в разделе Школы
Подскажите как найти наибольший общий делитель нескольких натуральных чисел ((6 класс)) и получил лучший ответ
Ответ от Анатолий Бежин[активный]
чтобы найти наибольший общий делитель нескольких натуральных чисел, надо:
1)разложить их на простые множители;
2)выписать те множители, которые входят в разложение каждого из чисел;
3)найти произведение этих множителей.
Примеры:
а) найти НОД (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) = 1.
Источник: http://shpargalka.kz/matematika/naibolshii-obshii-delitel
Наибольшим общим делителем (НОД) для двух целых чисел m и n называется наибольший из их общих делителей. Пример: для чисел 70 и 105 наибольший общий делитель равен 35.
Наибольший общий делитель существует и однозначно определён, если хотя бы одно из чисел m или n не ноль.
Возможные обозначения наибольшего общего делителя чисел m и n:
НОД (m, n)
(m, n)
gcd(m, n) (от англ. Greatest Common Divisor)
hcf(m, n) (от брит. англ. Highest Common Factor)
Эффективными способами вычисления НОД двух чисел являются алгоритм Евклида и бинарный алгоритм.
Кроме того, значение НОД (m,n) можно легко вычислить, если известно каноническое разложение чисел m, n на простые множители:
n=p_1^{d_1}cdotdotscdot p_k^{d_k},
m=p_1^{e_1}cdot dots cdot p_k^{e_k},
где p_1,dots,p_k — различные простые числа, а d_1,dots,d_k и e_1,dots,e_k — неотрицательные целые числа (они могут быть нулями, если соответствующее простое отсутствует в разложении). Тогда НОД (m,n) и НОК (m,n) выражаются формулами:
(n,m)=p_1^{min(d_1,e_1)}cdotdotscdot p_k^{min(d_k,e_k)},
[n,m]=p_1^{max(d_1,e_1)}cdotdotscdot p_k^{max(d_k,e_k)}.
Если чисел более двух: a_1, a_2,dots a_n, их НОД находится по следующему алгоритму:
d_2=(a_1, a_2)
d_3=(d_2, a_3)
………
d_n=(d_{n-1}, a_n) — это и есть искомый НОД.
чтобы найти наибольший общий делитель нескольких натуральных чисел, надо:
1)разложить их на простые множители;
2)выписать те множители, которые входят в разложение каждого из чисел;
3)найти произведение этих множителей.
Примеры:
а) найти НОД (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) = 1.
Примеры:
а) найти НОД (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) = 1.
Вычислите наибольший общий делитель чисел 77164189341682084692124351766096496451364840671846455244761 и
46668734283684548617206823665104829826096872771679324943689.
разложить на простые множители
чтобы найти наибольший общий делитель нескольких натуральных чисел, надо:
1)разложить их на простые множители;
2)выписать те множители, которые входят в разложение каждого из чисел;
3)найти произведение этих множителей.
Примеры:
а) найти НОД (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) = 1.
...
ххх