Числа а и m взаимно просты. Доказать, что найдется натуральное k, для которого число ka при делении на m дает остаток 1.

Предположим, что a > m.

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

a = m * n + r, m > r.

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

Так как a и m взаимно простые, то m и r тоже взаимно простые,

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

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

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

m = r * n1 + r1, r > r1, r и r1 - тоже взаимно простые.

r = r1 * n2 + r2, r1 > r2, r1 и r2 - взаимно простые.

Продолжим этот процедуру.

Остатки r > r1 > r2 > ... > 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.