Числа а и m обоюдно ординарны. Обосновать, что найдется естественное k,

Представим, что a gt; m.

Тогда при разделении a на m получим остаток r:

a = m * n + r, m gt; r.

Остаток r не может быть одинаковым 0, т.к. в неприятном случае a делилось бы на m, что противоречит обоюдной простоте a и m.

Так как a и m обоюдно простые, то  m и r тоже обоюдно обыкновенные,

т.к если m = d * p и r = d * q и d gt; 1, то

a = d * p * n + d * q = d * (p * n + q). Отсюда вытекает, что a и m делится на d gt; 1, что противоречит обоюдной простоте a и m.

Аналогично можем записать:

m = r * n1 + r1, r gt; r1, r и r1 - тоже взаимно обыкновенные.

r = r1 * n2 + r2, r1 gt; r2, r1 и r2 - обоюдно обыкновенные.

Продолжим этот функцию.

Остатки r gt; r1 gt; r2 gt; ... gt; rn. Следовательно, последний остаток

rn = 1.

r(n-2) = r(n-1) * n(n) + 1.

Пусть r2 = 1. Тогда:

1 = r - r1 * n  = r - (m - r * n1) * n = r * (1 - n1 * n) - m * n =

= (a - m * n) (1 - n1 * n) - m * n =

= a * (1 - n1 * n) - m * n * (2 - n1 * n) = a * k + m * l.

Подобно, можно показать, что для любого rn = 1 имеет место представление:

a * k + m * l = 1.

А это означает, что существует такое к, что a * k при дроблении на m даёт в остатке 1.