Dowód odwracalności elementu

[dawcza3]

Udowodnij, że element a \(\displaystyle{ \in}\) \(\displaystyle{ Z_{m}}\) jest odwracalny wtedy i tylko wtedy gdy
\(\displaystyle{ NWD(a, m) = 1}\)

Z definicji wiemy że \(\displaystyle{ [a]}\) \(\displaystyle{ \in}\) \(\displaystyle{ Z_{m}}\) jest odwracalny jak istnieje jakiś \(\displaystyle{ }\) \(\displaystyle{ \in}\) \(\displaystyle{ Z_{m}}\) do niego odwrotny taki że \(\displaystyle{ a \cdot b (mod m) =1}\)

No i wiem że \(\displaystyle{ NWD(a,m)=1}\) więc \(\displaystyle{ xa+ym=1}\)

No i właśnie tu moje pomysły się kończą, ktoś może mi pomóc jak dalej ruszyć ten dowód?

[bakala12]

Załóżmy, że \(\displaystyle{ NWD\left( a,m\right)=d}\) i niech istnieje \(\displaystyle{ b}\) takie, że \(\displaystyle{ a \cdot b \equiv 1 \pmod{m}}\). Niech \(\displaystyle{ m=k \cdot d}\), więc mamy \(\displaystyle{ ab=l \cdot m+1=\left( kl\right)d+1}\). Stąd \(\displaystyle{ a \cdot b \equiv 1 \pomd{d}}\), a ponieważ \(\displaystyle{ d|a}\), to musi być również \(\displaystyle{ a \cdot b \equiv 0 \pmod{d}}\), co oznacza, że \(\displaystyle{ 0 \equiv 1 \pmod{d}}\) co oznacza \(\displaystyle{ d=1}\).
W druga stronę, jeśli \(\displaystyle{ a \neq 0}\) i \(\displaystyle{ NWD\left( a,m\right)=1}\), to na mocy rozszerzonego algorytmu Euklidesa istnieją \(\displaystyle{ x,y \in \mathbb{Z}}\), że \(\displaystyle{ xa+ym=1 \Rightarrow xa=1-ym \equiv 1 \pmod{m}}\). Stąd \(\displaystyle{ x}\) jest elementem odwrotnym do \(\displaystyle{ a}\).