\(\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.
Podzielność elementu odwrotnego w Z_n
-
czlowiek_widmo
- Użytkownik
- Posty: 161
- Rejestracja: 24 wrz 2009, o 18:42
- Płeć: Mężczyzna
- Lokalizacja: na albatrosie, albatrosie
- Podziękował: 9 razy
- Pomógł: 9 razy
-
BettyBoo
- Użytkownik
- Posty: 5354
- Rejestracja: 10 kwie 2009, o 10:22
- Płeć: Kobieta
- Lokalizacja: Gliwice
- Pomógł: 1381 razy
Podzielność elementu odwrotnego w Z_n
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.
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.