Задача 60491

Темы:    [ НОД и НОК. Взаимная простота ] [ Алгоритм Евклида ]

Сложность: 3+ Классы: 8,9,10

Условие

Найдите    ( , ).

Решение

  Если  m > n  и  m = nq + r,  где  r < n,  то один шаг алгоритма Евклида приводит к равенству  (,  ) = (, ).
  Поэтому, в конце концов, получится число, состоящее из  (m, n) единиц.

Ответ

Источники и прецеденты использования

книга
Автор	Алфутова Н.Б., Устинов А.В.
Год издания	2002
Название	Алгебра и теория чисел
Издательство	МЦНМО
Издание	1
глава
Номер	3
Название	Алгоритм Евклида и основная теорема арифметики
Тема	Алгебра и арифметика
параграф
Номер	2
Название	Алгоритм Евклида
Тема	Алгоритм Евклида
задача
Номер	03.039