Контрольные задания
Вопрос:Фото задания: 2. Повторить: алгоритмы нахождения НОД и НОК, нахождение взаимно простых чисел (через НОД) (будет самостоятельная работа).Фото задания

Ответ:

НОД — наибольший общий делитель двух чисел. Алгоритм Евклида: большее число делят на меньшее; затем делитель делят на полученный остаток. Повторяют, пока остаток не станет равен нулю. Последний ненулевой остаток — НОД.

Пример: найти НОД(48, 18).

  1. 48 = 18 · 2 + 12.

  2. 18 = 12 · 1 + 6.

  3. 12 = 6 · 2 + 0.

Значит, НОД(48, 18) = 6.

НОК — наименьшее общее кратное. Можно выписать кратные каждого числа и выбрать наименьшее общее. Удобная формула для положительных целых чисел: НОК(a, b) = a · b : НОД(a, b).

Пример: НОК(12, 18) = 12 · 18 : 6 = 36.

Взаимно простые числа — числа, НОД которых равен 1. Например, НОД(8, 15) = 1, поэтому 8 и 15 взаимно простые. Если НОД чисел больше 1, они не являются взаимно простыми.