Введение в теорию делимости

Пусть $a$ и $b$ - натуральные числа. Говорят, что $b$ делит $a$ (обозначается $b|a$), если существует натуральное число $c$ такое, что $a=b\cdot c$. В этом случае число $b$ называется делителем числа $a$.

Общим делителем чисел $a$ и $b$ называется такое число, которое делит и $a$, и $b$.

Наибольшим общим делителем чисел $a$ и $b$ называется наибольший из их общих делителей. Он существует, поскольку у каждого числа не может быть больше делителей, чем величина самого этого числа, а значит общих делителей у двух чисел не больше, чем величина меньшего из этих двух чисел.

Теорема. Пусть $d$ - наибольший общий делитель чисел $a$ и $b$. Тогда существуют целые числа $x$ и $y$ такие, что $d=a\cdot x+b\cdot y$.

Доказательство. Если $a=b$, то наибольший общий делитель чисел $a$ и $b$ равен $a$, и он представим в требуемом виде: $a=a\cdot 1+b\cdot 0$. Так что в этом случае утверждение теоремы выполняется.

Докажем теорему в общем случае методом математической индукции по величине $a+b$. При $a=b=1$ уже всё доказано, поэтому при $a+b=2$ утверждение теоремы верно.

Пусть $a+b>2$. Можно считать, что $a\neq b$, так как иначе всё уже доказано. Тогда можно считать, что $a>b\geqslant 1$. Рассмотрим пару натуральных чисел $a-b$ и $b$. Их сумма равна $a$, что меньше, чем $a+b$, но больше либо равно $2$, поэтому к этой паре чисел можно применить предположение индукции. Пусть $d$ - наибольший общий делитель чисел $a-b$ и $b$. Тогда найдутся целые числа $x$ и $y$ такие, что $d=(a-b)\cdot x+b\cdot y=a\cdot x+b\cdot (y-x)$. Осталось заметить, что наибольший общий делитель чисел $a-b$ и $b$ является одновременно наибольшим общим делителем чисел $a$ и $b$. Это следует из того, что общий делитель двух чисел делит также их сумму и разность. Так как $d$ уже представлено в требуемом виде, то индукционный переход совершён и теорема доказана.