374. Найдите: а) НОД(420, 1400); б) НОД(2079, 1089); в) НОД(312, 468); г) НОД(2695, 4235).

Решение:

Для нахождения наибольшего общего делителя (НОД) воспользуемся алгоритмом Евклида или разложением на простые множители.

а) НОД(420, 1400)

Разложим числа на простые множители:

420 = 2^2 * 3 * 5 * 7

1400 = 2^3 * 5^2 * 7

Общие множители: 2^2, 5, 7.

НОД(420, 1400) = 2^2 * 5 * 7 = 4 * 5 * 7 = 140.

б) НОД(2079, 1089)

Используем алгоритм Евклида:

2079 = 1 * 1089 + 990

1089 = 1 * 990 + 99

990 = 10 * 99 + 0

НОД(2079, 1089) = 99.

в) НОД(312, 468)

Разложим числа на простые множители:

312 = 2^3 * 3 * 13

468 = 2^2 * 3^2 * 13

Общие множители: 2^2, 3, 13.

НОД(312, 468) = 2^2 * 3 * 13 = 4 * 3 * 13 = 156.

г) НОД(2695, 4235)

Используем алгоритм Евклида:

4235 = 1 * 2695 + 1540

2695 = 1 * 1540 + 1155

1540 = 1 * 1155 + 385

1155 = 3 * 385 + 0

НОД(2695, 4235) = 385.

Ответ: а) 140; б) 99; в) 156; г) 385.