Question

докажите, что для любого натурального n НОД (n;6n+1) =1​

Answer 1

Ответ и Объяснение:

Применим алгоритм Евклида с вычитанием. Суть алгоритма заключается в последовательной замене наибольшего числа из двух данных чисел, для которых вычисляется НОД, разностью этих чисел. То есть верно:

если a≥b, то НОД(a; b) = НОД(a - b; b).

Тогда

НОД (n; 6·n+1) = НОД (n; 6·n+1-n) = НОД (n; 5·n+1) = НОД (n; 5·n+1-n) =

= НОД (n; 4·n+1) = НОД (n; 4·n+1-n) = НОД (n; 3·n+1) = НОД (n; 3·n+1-n) =

= НОД (n; 2·n+1) = НОД (n; 2·n+1-n) = НОД (n; n+1) = НОД (n; n+1-n) =

= НОД (n; 1) = 1.