Odwrotonść modulo - potwierdzenie

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
realityoppa
Użytkownik
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

Post autor: realityoppa »

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).
Awatar użytkownika
Vax
Użytkownik
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

Post autor: Vax »

Tak.
realityoppa
Użytkownik
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

Post autor: realityoppa »

A mógłbym Cię prosić jeszcze o dowód tego ?
Awatar użytkownika
kropka+
Użytkownik
Użytkownik
Posty: 4389
Rejestracja: 16 wrz 2010, o 14:54
Płeć: Kobieta
Lokalizacja: Łódź
Podziękował: 1 raz
Pomógł: 787 razy

Odwrotonść modulo - potwierdzenie

Post autor: kropka+ »

Wystarczy wziąć np. \(\displaystyle{ b= \frac{1}{a}}\)
Awatar użytkownika
Vax
Użytkownik
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

Post autor: Vax »

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}}\)
realityoppa
Użytkownik
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

Post autor: realityoppa »

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}\) ?)
Awatar użytkownika
Vax
Użytkownik
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

Post autor: Vax »

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}}\)
realityoppa
Użytkownik
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

Post autor: realityoppa »

aaaah sorki skrót myślowy, miałem na myśli \(\displaystyle{ b= a^{\phi(n)-1}}\) i potem z twierdzenie Eulera
ODPOWIEDZ