Odwrotonść modulo - potwierdzenie
-
- Użytkownik
- Posty: 117
- Rejestracja: 26 gru 2012, o 16:36
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 54 razy
- Pomógł: 10 razy
Odwrotonść modulo - potwierdzenie
Proszę o potwierdzenie czy prawdą jest, iż jeśli \(\displaystyle{ \NWD(a,n)=1}\) to istnieje takie \(\displaystyle{ b}\) że \(\displaystyle{ ab\equiv 1\mod n}\) ?
Ostatnio zmieniony 1 mar 2014, o 10:53 przez lukasz1804, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości (\NWD, \mod).
Powód: Poprawa wiadomości (\NWD, \mod).
-
- Użytkownik
- Posty: 117
- Rejestracja: 26 gru 2012, o 16:36
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 54 razy
- Pomógł: 10 razy
- Vax
- Użytkownik
- Posty: 2913
- Rejestracja: 27 kwie 2010, o 22:07
- Płeć: Mężczyzna
- Lokalizacja: Biała Podlaska / Warszawa
- Podziękował: 4 razy
- Pomógł: 612 razy
Odwrotonść modulo - potwierdzenie
Wystarczy zauważyć, że wszystkie liczby \(\displaystyle{ a,2a,3a,...,(n-1)a \pmod{n}}\) są parami różne. Istotnie, jakby istniały takie różne \(\displaystyle{ k,l \in [1;n-1]}\), że \(\displaystyle{ ka \equiv la\pmod{n} \iff a(k-l) \equiv 0\pmod{n} \iff k \equiv l\pmod{n}}\) sprzeczność, bo \(\displaystyle{ |k-l| < n}\) oraz \(\displaystyle{ k-l \neq 0}\). Czyli mamy \(\displaystyle{ n-1}\) różnych niezerowych wartości, skąd w szczególności istnieje takie \(\displaystyle{ b}\), że \(\displaystyle{ ab \equiv 1\pmod{n}}\)
-
- Użytkownik
- Posty: 117
- Rejestracja: 26 gru 2012, o 16:36
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 54 razy
- Pomógł: 10 razy
Odwrotonść modulo - potwierdzenie
Dziękuje. A teraz mi przyszło jeszcze do głowy, żeby wykazać samo istnienie wystarczy np. przyjąć \(\displaystyle{ b=\phi(n)-1}\) ?
(Nie trzeba się bawić z przypadkami gdy \(\displaystyle{ \phi(n)=1}\) ?)
(Nie trzeba się bawić z przypadkami gdy \(\displaystyle{ \phi(n)=1}\) ?)
- Vax
- Użytkownik
- Posty: 2913
- Rejestracja: 27 kwie 2010, o 22:07
- Płeć: Mężczyzna
- Lokalizacja: Biała Podlaska / Warszawa
- Podziękował: 4 razy
- Pomógł: 612 razy
Odwrotonść modulo - potwierdzenie
Ale takie \(\displaystyle{ b}\) nie będzie spełniać tezy, przyjmij np \(\displaystyle{ a=2 , n = 11}\) czyli \(\displaystyle{ b=9}\), a wówczas \(\displaystyle{ ab \equiv 7 \pmod{11}}\)
-
- Użytkownik
- Posty: 117
- Rejestracja: 26 gru 2012, o 16:36
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 54 razy
- Pomógł: 10 razy
Odwrotonść modulo - potwierdzenie
aaaah sorki skrót myślowy, miałem na myśli \(\displaystyle{ b= a^{\phi(n)-1}}\) i potem z twierdzenie Eulera