Mam problem z takim oto zadaniem:
Pokaż, że jeżeli \(\displaystyle{ m}\) nie jest liczbą pierwszą to wtedy co najmniej \(\displaystyle{ \sqrt{m}}\) elementów \(\displaystyle{ Z_{m}}\) nie ma multiplikatywnej odwrotności.
Proszę o jakieś wskazówki i ew. rozwiązanie, gdyż totalnie nie wiem jak je ugryźć, a znalezione przeze mnie materiały nie pomagają.
Kryptografia - odwrotnośc multiplikatywna
Kryptografia - odwrotnośc multiplikatywna
Ostatnio zmieniony 2 sty 2013, o 14:00 przez Qń, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości. Nie używaj tagów [b]...[/b] do wyrażeń matematycznych.
Powód: Poprawa wiadomości. Nie używaj tagów [b]...[/b] do wyrażeń matematycznych.
-
Qń
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
Kryptografia - odwrotnośc multiplikatywna
Niech \(\displaystyle{ m=kl}\), gdzie \(\displaystyle{ 1<k<l}\).
Element \(\displaystyle{ n\in\mathbb{Z}_m}\) jest nieodwracalny wtedy i tylko wtedy gdy \(\displaystyle{ NWD(n,m)>1}\). Łatwo widać, że liczby \(\displaystyle{ 0,k,2k, \ldots , (l-1)k\in \mathbb{Z}_m}\) nie są względnie pierwsze z \(\displaystyle{ m}\) i jest ich \(\displaystyle{ l}\). A oczywiście:
\(\displaystyle{ l=\sqrt{l^2}>\sqrt{kl}=\sqrt{m}}\)
Q.
Element \(\displaystyle{ n\in\mathbb{Z}_m}\) jest nieodwracalny wtedy i tylko wtedy gdy \(\displaystyle{ NWD(n,m)>1}\). Łatwo widać, że liczby \(\displaystyle{ 0,k,2k, \ldots , (l-1)k\in \mathbb{Z}_m}\) nie są względnie pierwsze z \(\displaystyle{ m}\) i jest ich \(\displaystyle{ l}\). A oczywiście:
\(\displaystyle{ l=\sqrt{l^2}>\sqrt{kl}=\sqrt{m}}\)
Q.