Тема занятия кружка «Юный математик»
Наибольший общий делитель НОД.
Наибольшее натуральное число, на которое делятся без остатка числа a и b, называются общим делителем этих чисел.
Чтобы найти НОД нескольких натуральных чисел надо:
1. Разложить их на простые множители
2. Выписать множители, входящие в разложение всех чисел
3. Найти их произведение
Алгоритм Евклида
НОД(391;299)=23 | Чтобы найти НОД, надо: Большее число разделить на меньшее. Если остаток не равен 0, то меньшее число делят на первый остаток. Если второй остаток не равен 0, то первый остаток разделим на второй. Второй на третий и т. д., пока не получим остаток равный нулю. Последний остаток, отличный от 0, равен НОД данных чисел. |
Натуральные числа называются взаимно простыми, если их НОД равен 1.
