Matematyka.pl

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}\) ?

Tak.

A mógłbym Cię prosić jeszcze o dowód tego ?

Wystarczy wziąć np. \(\displaystyle{ b= \frac{1}{a}}\)

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}}\)

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}\) ?)

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}}\)

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