Obliczenia modulo

[Piter9414]

Witam.

Nie za bardzo wiem jak poradzić sobie z takim zadaniem:

\(\displaystyle{ 6 ^{-1}mod12}\)

Nie wiem czy moge zastosować rozszerzony algorytm Euklidesa i wyznaczyć z niego element odwrotny do 6 w pierścieniu mod12, gdyż nie wiem czy tak sie robi gdy NWD
eq 1.

Pozdrawiam
Piter9414

[Medea 2]

Cóż, ten element nie istnieje. Jeśli bowiem dwanaście dzieli \(\displaystyle{ 6k-1}\), to szóstka też dzieli tę różnicę, ale nie dzieli jedynki.

[Piter9414]

Dziękuję za odpowiedź, jednakże nie szukałem tylko rozwiązania tego zadania raczej chciałem wiedzieć jak to się robi, a w tym co napisałaś nie bardzo wiem o co chodzi. Gdybyś może mogła to jakoś rozpisać żeby metoda była bardziej uniwersalna żebym inne zadania mógł też rozwiązać.

[Medea 2]

Czy moja metoda jest uniwersalna? Sama nie wiem. Po prostu w niektórych pierścieniach (masz dwadzieścia trzy lata, więc chyba wiesz już, co to jest) nie każdy element się odwraca. Prawdę mówiąc, to w większości pierścieni tak jest.

I tak na przykład w pierścieniu \(\displaystyle{ \ZZ_{n}}\) (dla \(\displaystyle{ n = 12}\)) odwracalne są \(\displaystyle{ 1,5,7,11}\). Wynika to z prostej równoważności (szukamy \(\displaystyle{ a}\), odwrotnego do \(\displaystyle{ x}\)): \(\displaystyle{ ax = 1}\), wtedy i tylko wtedy gdy \(\displaystyle{ ax + bn = 1}\), a to równanie ma rozwiązanie w liczbach całkowitych dokładnie dla względnie pierwszych \(\displaystyle{ x, n}\). Niestety, sześć i dwanaście nie są względnie pierwsze, więc rozwiązania nie ma.

A ogólna metoda to rozszerzony algorytm Euklidesa, jest o tym wuchta artykułów w internecie. Poszukaj, to nie boli.

[Piter9414]

o i tyle mi jak najbardziej wystarczy bo chodziło mi o to czy zawsze da sie wykonać takie działania. Ale skoro juz wiem że jak nie ma elementu odwrorotnego do liczby to nie da sie wykonać działania.

Dziękuje bardzo