Matematyka.pl

\(\displaystyle{ a \in \mathbb{Z}_n}\)
\(\displaystyle{ nwd(a,n)=1}\)

Pokazać, że \(\displaystyle{ nwd((a^{-1})_n ,n) =1}\).

Próbuje nie wprost ale nie moge dojść do sprzeczności.

Pierwsze założenie potrzebne jest do istnienia elementu odwrotnego.

Definicja elementu odwrotnego: \(\displaystyle{ aa^{-1}_n\equiv 1\mod n\ \Leftrightarrow \ \exists k\in\mathbb{Z}\quad a(a^{-1}_n)+nk=1}\)

Z powyższej równości wynika, że istnieją takie całkowite u,v, iż \(\displaystyle{ a^{-1}_nu+nv=1}\) (są to konkretnie \(\displaystyle{ u=a,\ v=k}\))
A to oznacza (z tw o kombinacji liniowej), że \(\displaystyle{ NWD(a^{-1}_n,n)|1}\), co dalej oznacza, że \(\displaystyle{ NWD(a^{-1}_n,n)=1}\)

Pozdrawiam.