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

Ответ:

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

Объяснение:

Для решения задачи сначала нужно определить количество коробок. Так как число iPhone 13, консолей Xbox Series X и  консолей Playstation 5 в каждую коробку распределили равномерно, то количество коробок равно НОД(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.

Применим свойство: НОД(n; m; k) = НОД(НОД(n; m) ; k):

НОД(391; 221; 187) = НОД(НОД(391; 221); 187) = НОД(17; 187).

Теперь, как и выше, применим алгоритм Евклида для нахождения НОД(17; 187):

1) 187 = 11·17+0,

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

Далее, количество консолей Playstation 5 всего 187 штук, то их количество в каждой коробке 187 : 17 = 11 штук.

#SPJ1