Dowód - liczba odwracalna modulo m

[patricia__88]

Twierdzenie. Liczba całkowita \(\displaystyle{ a}\) jest odwracalna modulo \(\displaystyle{ m}\) wtedy i tylko wtedy, gdy \(\displaystyle{ NWD(a,m)=1}\)

Można tutaj skorzystać z czegoś takiego, że:
Dla dowolnych liczb całkowitych \(\displaystyle{ a,b,x,y}\), dla których spełnione jest \(\displaystyle{ a^2+b^2 \neq 0}\), zachodzi relacja \(\displaystyle{ NWD(a,b)|ax+by}\)
Jednak nie wiem jak z kolei to udowodnić.
A może ma ktoś inny pomysł jak dowieść to twierdzenie?

[Vax]

Na początku pokażemy, że jeżeli \(\displaystyle{ (a,m)=1}\) to a jest odwracalne modulo m. Rozpatrzmy liczby \(\displaystyle{ a \ , \ 2a \ , \ 3a \ , \ ... \ , (m-1)a \ , \ ma}\) modulo m. Żadne z nich nie są równe. Istotnie, jeżeli dla pewnych \(\displaystyle{ k \neq l}\) byłoby \(\displaystyle{ ka \equiv la \pmod{m}}\), to wówczas:

\(\displaystyle{ ka \equiv la\pmod{m} \iff a(k-l) \equiv 0\pmod{m}}\), jednak \(\displaystyle{ (a,m)=1}\) czyli musiałoby być \(\displaystyle{ k \equiv l \pmod{m}}\) sprzeczność. Tak więc w \(\displaystyle{ \mathbb{Z}_n}\) \(\displaystyle{ \lbrace a \ , \ 2a \ ... \ , ma\rbrace = \lbrace 0 , 1 , 2 , ... , m-1\rbrace}\), czyli istotnie istnieje takie \(\displaystyle{ b}\), że \(\displaystyle{ ab \equiv 1\pmod{m}}\)

Teraz pokażemy, że z istnienia b spełniającego \(\displaystyle{ ab \equiv 1\pmod{m}}\) wynika \(\displaystyle{ (a,m)=1}\). Istotnie, \(\displaystyle{ ab \equiv 1\pmod{m} \iff m \mid ab-1}\), niech \(\displaystyle{ d = (a,m)}\), wówczas w szczególności \(\displaystyle{ d \mid ab-1 \Rightarrow d \mid 1 \Rightarrow d=1}\) cnd.

[patricia__88]

Dziękuję bardzo