Кольца вычетов

[MMyaf]

Доказать, что при любом $n$ элемент $[k]_n$ обратим в кольце $Z_n$ тогда и только тогда, когда $n$ и $k$ взаимно просты.

[PAV]

Для любых натуральных чисел $x$ и $y$ существуют такие целые числа $a$ и $b$, что $ax+by=\mbox{\rf НОД}(x,y)$.

Дальше подумайте.