Question

Наибольший общий делитель натуральных чисел n и m равен 1. Каково наибольшее возможное значение НОД(m+100n, n+100m)? Внимание! - ответ НЕ 101

Answer 1

Положим $a=m+100n;~ b=n+100m$, тогда НОД(a;b) = c.

Из второго равенства n = b - 100m, подставляя в первое, получим

$a=m(1-100^2)+100b~~~\Rightarrow~~~ 100b-a=(100^2-1)m$

Аналогично, выражая n из первого равенства и подставляя

во второе равенство, получим $100a-b=(100^2-1)n$. А так как

НОД(m;n) = 1, т.е. m и n - взаимно простые, то c делит (100²-1) = 9999

Ответ: 9999.

Answer 2

Наибольший общий делитель (НОД) двух чисел m и n равен 1, что означает, что эти числа взаимно просты. Мы хотим найти наибольшее возможное значение НОД(m + 100n, n + 100m).

Давайте выразим m + 100n и n + 100m как линейные комбинации m и n:

m + 100n = 100 * n + m n + 100m = m + 100 * n

Обратите внимание, что обе выражения идентичны.

Таким образом, НОД(m + 100n, n + 100m) всегда равен НОД(100 * n + m, 100 * n + m). Это просто НОД(число, то же самое число).

Наибольший общий делитель числа с самим собой всегда равен самому числу. Таким образом, НОД(m + 100n, n + 100m) равен 100n + m.

Поскольку m и n - натуральные числа, наибольшее возможное значение этого выражения будет достигаться, когда m = 1 и n = 1. Тогда НОД(m + 100n, n + 100m) = НОД(100 + 1, 100 + 1) = НОД(101, 101).

Но, как указано в вопросе, ответ НЕ 101. Так как множество натуральных чисел бесконечно, существует бесконечное количество пар натуральных чисел m и n, для которых НОД(m + 100n, n + 100m) равен разным числам. Таким образом, нет одного наибольшего возможного значения, отличного от 101, для НОД(m + 100n, n + 100m).