Алгоритм Евклида можно использовать для нахождения наибольшего
общего делителя (НОД) двух чисел. Ниже приведен пример его
применения:
Найдите Нод чисел 546 и 117:
(рисунок 1)
Д
НОд из 546 и 117 равен 39. у Бауыржана есть 391 шт. iPhone 13, 221 шт.
консолей Xbox Series X и 187 шт. консолей Playstation 5. Он упаковывает их
в наименьшее возможное количество коробок, причем каждая коробка
содержит столько же iPhone, Xbox и Playstation, сколько и другие коробки.
(рисунок 2)
Сколько консолей Playstation 5 находится в каждой коробке?
*

Ответ:

В каждой коробке находится по 11 штук Playstation 5

Объяснение:

Нужно знать: НОД(a; b; c) = НОД(НОД(a; b); c).

Решение. Сначала определим количество коробок. Для этого нужно найти НОД(391; 221; 187).

По алгоритму Евклида находим НОД(391; 221):

1) 391 = 1·221 + 170

2) 221 = 1·170 + 51

3) 170 = 3·51 + 17

4) 51 = 3·17 + 0.

Значит: НОД(391; 221) = 17.

Так как НОД(391; 221; 187) = НОД(НОД(391; 221); 187) = НОД(17; 187), то по алгоритму Евклида находим НОД(17; 187):

1) 187 = 11·17+0,

то есть НОД(17; 187) = 17 - наименьшее возможное количество коробок.

Так как 187 = 11·17 означает, что в каждой коробке находится по 11 штук Playstation 5.

#SPJ1