Задача следующая. Доказать алгоритм Евликида. m = qn+r, где q - некоторое число; m - Первое число; n - Второе число; r - Остаток от деления m на n.
Если r = 0, то m кратно n, получается n - это НОД. (Это понятно)
Если r != 0, то любой делитель обоих чисел m и n должен быть делителем m - qn = r, и любой делитель n и r также делителем qn + r = m. Таким образом множество делителей числе {m, n} совпадает с множеством делителей {n, r}. Следовательно, пары чисел {m, n} и {n, r} имеют один и тот же НОД.
Вопрос такой, что значит "некоторое число 'q', ведь его нет в алгоритме? И как вообще происходит это доказательство?
Перебирал реальные числа, но нет уверенности в правильном ли направлении мыслю.
