№2 - Утверждение об обратимых элементах кольца ℤn

Предположение. Элемент $a \in Z_{n}$, $a≠0$ обратим $\iff \text{НОД }(a,n) = 1$

Доказательство: ???

Если бы $a,n$ делилились на число $d>1$, тогда $ab$ делится на $d,nk$ делится на $d$, поэтому $1$ делится $(1=an-nk)$ на $d>1$. Следовательно, получено противоречие.

<= Воспользуемся общим алгоритмом Евклида*

Алгоритм Евклида — эффективный алгоритм для нахождения наибольшего общего делителя двух целых чисел (или общей меры двух отрезков).

Пусть требуется найти $d=\text{НОД }(k,n)$ Для этого начинаем деление с остатком до тех пор, пока этот остаток не станет нулём

$n = kt1 + r1  r1<k$
$k = r1t2+r2r2<r1$
$r1 = r2t3 + r3 r3<r1$
...
$rs-1= rsts+1 + rs+1(1)$
$rs = rs+1ts+2 + 0$
Значит, $d = rs+1$

Найдём теперь
$l,t \in Zn : rs = rs-2-rs-1ts (2)$
$Kl + nt = d$

Алгоритм Евклида + нахождение $l,t$ называется обобщением алгоритмом Евклида.

В ф-ме 1 движемся в обратном направлении, начиная с предпоследнего р-ва:
$d = r_{s-1} - r_{s}t_{s+1}$
Подставляя значения предыдущих остатков получим:

Множество идеалов является моноидом по сложению с нейтральным элеметом $\{0\}$.