uogólniony alg. Euklidesa w pierścieniu

[PiTek93]

Cześć, treść zadania jest taka, Korzystając z uogólnionego algorytmu Euklidesa, znajdź element odwrotny do \(\displaystyle{ 31}\) z grupie \(\displaystyle{ Zn_{36}}\). Ile elementów ma ta grupa.

To zadanie nie jest specjalnie trudne, wymaga tylko opanowania metody.
\(\displaystyle{ 31*x + 36 * y = 1}\)

\(\displaystyle{ \begin{cases} 31 * 0 + 36 * 1 = 36\\ 31 *1 + 36 * 0 = 31\end{cases}}\)
\(\displaystyle{ \begin{cases} 31 * 1 + 36 * 0 = 31\\ 31 *(-1) + 36 * 1 = 5\end{cases}}\)
\(\displaystyle{ \begin{cases} 31 * (-1) + 36 * 1 = 5\\ 31 *7 + 36 * (-6) = 1\end{cases}}\)

\(\displaystyle{ 31 *7 + 36 * (-6) = 1}\)
Jak teraz wyznaczyć element odwrotny?
Mam wziąć \(\displaystyle{ 7 mod 36}\) czyli \(\displaystyle{ 7}\) ?

Oraz czy liczba elementów grupy, to jest ilość liczb pierwszych począwszy od 1 do 36? czyli \(\displaystyle{ 1, 3, 5, 7, 11, 13, 17, 19, 23, 27, 31}\), czyli \(\displaystyle{ 11}\)?

[MadJack]

Tak, elementem odwrotnym jest \(\displaystyle{ 7}\), bo zauważ, że to co napisałeś można przekształcić do:
\(\displaystyle{ 31 \cdot 7 - 1 \mid 36}\), więc z definicji \(\displaystyle{ 31 \cdot 7 \equiv 1 \pmod{36}}\).

Liczba elementów \(\displaystyle{ \matbb{Z}_{36}^*}\) to liczba elementów względnie pierwszych z \(\displaystyle{ 36}\) mniejszych od niej, czyli jest ich \(\displaystyle{ \varphi (36) = 12}\), więc nie wypisałeś wszystkich, a nawet wypisałeś te, które do tej grupy nie należą.

Zaznaczę, że \(\displaystyle{ 1}\) nie ejst liczbą pierwszą, za to \(\displaystyle{ 2}\) jest (ale oczywiście nie należy do tej grupy, tak samo jak \(\displaystyle{ 3}\), bo liczby te dzielą \(\displaystyle{ 36}\)), jest nią także \(\displaystyle{ 29}\)(które już do tej grupy należy).

[PiTek93]

Dziękuję za błyskawiczną odpowiedź, rozumiem już czym jest element odwrotny, a liczba elementów grupy to \(\displaystyle{ \varphi (36) = 12}\), czyli to nie mają być liczby pierwsze, tylko te, przez które nie jest podzielne \(\displaystyle{ 36}\)? chyba nie..
to może to maja być liczy pierwsze przez które nie dzieli się \(\displaystyle{ 36}\), tak?

Czy mógłbyś przypomnieć mi jak się liczy \(\displaystyle{ \varphi (x) = ?}\)

[MadJack]

Nie, elementy tej grupy to, jak pisałem, liczby względnie pierwsze z \(\displaystyle{ 36}\) (tylko te są odwracalne!), czyli:
\(\displaystyle{ 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35}\).
Na wikipedii masz podany wzór na obliczanie wartości funkcji Eulera:

Kod: Zaznacz cały

https://pl.wikipedia.org/wiki/Funkcja_%CF%86

Wystarczy zauważyć, że \(\displaystyle{ 36 = 2^2 \cdot 3^2}\).
Zauważ, że \(\displaystyle{ 2, 3}\) nie należą do grupy, bo \(\displaystyle{ \NWD (2,36)=2, \ \NWD (2,36)=3}\), należą natomiast \(\displaystyle{ 1}\) i \(\displaystyle{ 25}\), bo \(\displaystyle{ \NWD (1,36)=1, \ \NWD (25,36)=1}\).

EDIT: mariuszm zauważył mały błąd w wypisanych elementach, więc poprawiłem.

[PiTek93]

rozumiem, że muszę znaleźć iloczyn liczb, które po podniesieniu do kwadratu, dadzą mi liczbę, w tym wypadku 36, tak?
dlatego tu jest \(\displaystyle{ 36 = 2^2 \cdot 3^2}\), bo 36 to nie liczba pierwsza ?

dobra, a jeżeli wynik wyszedłby mi inny, to w tym zadaniu chodzi o policzenie ilości elementów, funkcją eulera, tak?

[MadJack]

Tak, skoro masz znaleźć liczbę elementów grupy, to wystarczy wyznaczyć wartosć funkcji Eulera (oczywiście mowa tu o grupach skończonych \(\displaystyle{ \mathbb{Z}_n^*}\) z mnożeniem). A piszę \(\displaystyle{ 36 = 2^2 \cdot 3^2}\), bo jest to rozkład na czynniki pierwsze tej liczby. Zauważ, że musisz rozłożyć liczbę na czynniki pierwsze, żeby skorzystać ze wzoru na wikipedii.

[PiTek93]

W takim razie, zadanie z identycznym poleceniem, ale dla liczb \(\displaystyle{ 23}\) z grupie \(\displaystyle{ Zn_{31}}\).

Będzie wyglądało tak:
\(\displaystyle{ \begin{cases} 31 * 1 + 0 * 23 = 31\\ 0 *31 + 1 * 23 = 23\end{cases}}\)
\(\displaystyle{ \begin{cases} 31 * 1 + 23 * (-1) = 8\\ 31 *(-2) + 23 * 3 = 7\end{cases}}\)
\(\displaystyle{ \begin{cases} 31 * (-2) + 23 * 3 = 7\\ 31 *3 + 23 * (-4) = 1\end{cases}}\)

\(\displaystyle{ 31 *3 + 23 * (-4) = 1}\)

Czyli element odwrotny to \(\displaystyle{ (-4) mod 31}\), czyli \(\displaystyle{ 27}\)
a ilość elementów to \(\displaystyle{ \varphi (31) = 31 - 1}\), czyli \(\displaystyle{ \varphi (31) = 30}\)

[MadJack]

Wyniki są ok (spójrz na prywatne wiadomości).

[a4karo]

Tylko ten gul w tytule boli

[Mariusz M]

Nie, elementy tej grupy to, jak pisałem, liczby względnie pierwsze z \(\displaystyle{ 36}\) (tylko te są odwracalne!), czyli:
\(\displaystyle{ 1, 5, 7, 11, 13, 17, 19, 23, 25, 27, 29, 31}\).

Od kiedy to \(\displaystyle{ 27}\) jest względnie pierwsze z \(\displaystyle{ 36}\)
no i gdzie jest \(\displaystyle{ 35}\)

Niech \(\displaystyle{ n=p_{1}^{k_{1}}p_{2}^{k_{2}}\cdot \cdots\cdot p_{m}^{k_{m}}}\)
wtedy \(\displaystyle{ \varphi\left( n\right)=n\left( 1- \frac{1}{p_{1}} \right)\left(1-\frac{1}{p_{2}} \right) \cdot \cdots\cdot \left( 1- \frac{1}{p_{m}} \right)}\)