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?
Dowód odwracalności elementu
-
- Użytkownik
- Posty: 3044
- Rejestracja: 25 mar 2010, o 15:34
- Płeć: Mężczyzna
- Lokalizacja: Gołąb
- Podziękował: 24 razy
- Pomógł: 513 razy
Dowód odwracalności elementu
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}\).
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}\).