Задача к ЕГЭ на тему «Уравнения в целых числах» №7

Докажите, что для любых натуральных чисел $n$ и $m$ существуют целые числа $p$ и $q$ , такие что НОД $(n; m ) = pn + qm$ .

Убедимся, что любой общий делитель всякой пары натуральных чисел $(n;m )$ является также и общим делителем пары $(m; n − m )$ : если уменьшаемое делится на число $k$ , то оно имеет вид $n = ak$ , если вычитаемое делится на число $k$ , то оно имеет вид $m = bk$ , тогда

n − m = ak − bk = (a − b)k,

то есть их разность также делится на число $k$ .

Аналогично доказывается, что любой общий делитель пары $(m; n − m )$ является общим делителем пары $(n;m )$ , следовательно,

Н О Д(n; m ) = Н О Д(m; n − m ).

Пусть $n > m » class=»math» width=»auto»>. Можно свести НОД<img decoding=$ к наибольшему общему делителю другой пары чисел, в которой наибольшее из чисел окажется меньше, чем $n$ , а именно: НОД $(n;m ) =$ НОД $(m; n − m )$ .

Таким образом, можно получить последовательность равенств вида $...=$ НОД $(k;0)$ или вида $...=$ НОД $(k; k)$ , но НОД $(k;k) =$ НОД $(k;0)$ .

Такую последовательность действительно можно получить, так как при $n > m » class=»math» width=»auto»> получается, что <img decoding=$ НОД $(m; n − m )$ максимум из чисел под знаком НОД в правой части с каждым таким шагом уменьшается по крайней мере на 1, но числа $n$ и $m$ – конечны, следовательно, через конечное число преобразований можно получить цепочку равенств вида $...=$ НОД $(k; 0)$ .

$∙$ Назовём выражение вида $an + bm$ , где $a,b ∈ ℤ$ линейной комбинацией над $ℤ$ чисел $n$ и $m$ . Ясно, что сумма линейных комбинаций над $ℤ$ чисел $n$ и $m$ снова линейная комбинация над $ℤ$ чисел $n$ и $m$ , разность линейных комбинаций над $ℤ$ чисел $n$ и $m$ снова линейная комбинация над $ℤ$ чисел $n$ и $m$ .

Последнее полученное равенство можно продолжить:

...= Н О Д(k; 0) = k.

При этом число $k$ получалось последовательным вычитанием из линейной комбинации над $ℤ$ чисел $n$ и $m$ линейных комбинаций над $ℤ$ чисел $n$ и $m$ , то есть $k$ есть линейная комбинация над $ℤ$ чисел $n$ и $m$ , следовательно, существуют целые числа $p$ и $q$ , такие что $k = pn + qm$ .