Multiplikativ invertierbare Elemente von Z_{36} bestimmen

28.08.2020, 13:40

msaedicn3123

Multiplikativ invertierbare Elemente von Z_{36} bestimmen

Meine Frage:
Ich soll folgende Übungsaufgabe lösen und benötige Hilfe:

Bestimmen Sie die multiplikativ invertierbaren Elemente von Z_{36}.

Ich verstehe zwar, dass ich das inverse Element von einer Zahl in Z_{36} bzgl. der Multiplikation über den euklidischen Algorithmus bestimmen, aber nicht, wie ich von den Restklassen alle angeben bzw. wie ich diese bestimme.

Kann mir bei dieser Aufgabe jemand weiterhelfen?

Meine Ideen:
-Restklassen von Z_{36} = {[0],...,[35]}
-Euklidischer Algorithmus für eine multiplikativ Inverse verwenden

28.08.2020, 14:03

Elvis

Auf diesen Beitrag antworten »

In $\begin{eqnarray*} \mathbb Z_m \end{eqnarray*}$ sind alle Restklassen invertierbar, die zu $\begin{eqnarray*} m \end{eqnarray*}$ teilerfremd sind und alle Restklassen nicht invertierbar, die zu $\begin{eqnarray*} m \end{eqnarray*}$ nicht teilerfremd sind. Wäre z.B. $\begin{eqnarray*} 2 \end{eqnarray*}$ invertierbar und $\begin{eqnarray*} a \end{eqnarray*}$ das inverse zu $\begin{eqnarray*} 2 \end{eqnarray*}$ , dann wäre $\begin{eqnarray*} 0=0*a=(18*2)*a=18*(2*a)=18*1=18 \end{eqnarray*}$ ein offensichtlicher Widerspruch in $\begin{eqnarray*} \mathbb Z_{36} \end{eqnarray*}$ .

28.08.2020, 14:57

msaedicn3123

Auf diesen Beitrag antworten »

und wie werden diese berechnet?
Wenn diese teilerfremd sind, muss der ggT(a,36)=1.
Wie finde ich das für die jeweiligen Restklassen heraus?Nehme ich mir beliebige Restklasse und probiere anhand des euklidischen Algorithmus durch?

28.08.2020, 15:44

Elvis

Auf diesen Beitrag antworten »

1*1=1
5*7=35=-1, also 5*(-7)=1, also 5*29=1
7 analog
11 ?
13 ?
17 ?
19 ?
23 ?
25 ?
29 (siehe 5)
31 (siehe 7)

Die Fragezeichen darfst du bearbeiten, da werden sich noch 3 Pärchen finden. Ohne Fleiß kein Preis. Es muss doch nicht immer der euklidische Algorithmus sein, warum denn kompliziert, wenn es auch einfach geht.

28.08.2020, 17:14

Leopold

Auf diesen Beitrag antworten »

Kleine Spielerei.
Gehen wir mal gruppentheoretisch an die Sache ran.

$\begin{align*} G = {\mathbb{Z}_{36}}^{*} = \left\{ 1,5,7,11,13,17,19,23,25,29,31,35 \right\} \end{align*}$

Die Gruppe $\begin{align*} G \end{align*}$ hat

$\begin{align*} \varphi(36) = 36 \cdot \left( 1 - \frac{1}{2} \right) \cdot \left( 1 - \frac{1}{3} \right) = 12 \end{align*}$

Elemente. Sie ist abelsch und nichtzyklisch (Theorie der primen Restklassengruppe), nach dem Hauptsatz der abelschen Gruppen also isomorph zum direkten Produkt $\begin{align*} \mathfrak{Z}_2 \times \mathfrak{Z}_2 \times \mathfrak{Z}_3 \end{align*}$ zyklischer Gruppen. In $\begin{align*} G \end{align*}$ suchen wir daher zwei Elemente der Ordnung 2 und eines der Ordnung 3. Man findet

$\begin{align*} 17^2 = 19^2 = 1, \ 13^3 = 1 \end{align*}$

Somit erzeugen $\begin{align*} 13,17,19 \end{align*}$ die Gruppe: $\begin{align*} G = \left \langle 13,17,19 \right \rangle \end{align*}$

Basteln wir Beispiele:

$\begin{align*} 17 \cdot 13^2 = 29 \end{align*}$

Invers dazu: $\begin{align*} 17 \cdot 13 = 5 \end{align*}$ . Probe: $\begin{align*} 29 \cdot 5 = 1 \end{align*}$

$\begin{align*} 17 \cdot 19 \cdot 13 = 23 \end{align*}$

Invers dazu: $\begin{align*} 17 \cdot 19 \cdot 13^2 = 11 \end{align*}$ . Probe: $\begin{align*} 23 \cdot 11 = 1 \end{align*}$

Wie gesagt, nur eine Spielerei. Keine Empfehlung als Lösung.

28.08.2020, 18:30

Finn_

Auf diesen Beitrag antworten »

Lass auch nebenbei den Computer rechnen.

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:

# Testet, ob a aus Z/mZ invertierbar ist.
def is_inv(a,m):
    return any((a*b)%m==1 for b in range(m))

# Einheitengruppe des Restklassenrings Z/mZ.
def units(m):
    return [a for a in range(m) if is_inv(a,m)]

print(units(36))

28.08.2020, 21:10

msaedicn3123

Auf diesen Beitrag antworten »

Mein errechneten multiplikativen Inversen sind:

$\begin{eqnarray*} \left[5\right] \cdot \left[29\right] \left[7\right] \cdot \left[31\right] \left[11\right] \cdot \left[23\right] \left[13\right] \cdot \left[25\right] \left[17\right] \cdot \left[17\right] \left[19\right] \cdot \left[19\right] \left[35\right] \cdot \left[-1\right] \end{eqnarray*}$

ich habe sie allerdings alle mit dem euklidischen Algorithmus errechnet, da diese bis auf die ersten nicht so einfach zu finden waren.

Ist das in eurem Sinne oder habe ich etwas nicht verstanden?

28.08.2020, 22:23

Finn_

Auf diesen Beitrag antworten »

Vom Ergebnis her ist das ok. Das Paar $\begin{eqnarray*} [1]\cdot [1] \end{eqnarray*}$ gehört in dieser Auflistung allerdings streng genommen auch dazu.

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:

def is_inv(a,m):
    return any((a*b)%m==1 for b in range(m))

def units(m):
    return [a for a in range(m) if is_inv(a,m)]

# Bestimmt das Inverse zu a (mod m).
def inv(a,m):
    return [b for b in range(m) if (a*b)%m==1][0]

# Paare (a,b), deren Elemente invers zueinander sind.
def pairs(m):
    return [(a,inv(a,m)) for a in units(m)]

def unique_pairs(m):
    return sorted(set(tuple(sorted(t)) for t in pairs(m)))

for t in unique_pairs(36):
    print("[{:2}] * [{:2}]".format(*t))

28.08.2020, 22:38

Elvis

Auf diesen Beitrag antworten »

13,17,19 hatte Leopold spielerisch erledigt, -1=35, damit blieb nur noch 11*23=1 übrig. Klar darf man auch beliebig mühsam rechnen, muss man aber nicht. Mir ist nicht ganz klar, was du mit dem euklidischen Algorithmus meinst. Ich rechne ganz einfach wie in der Grundschule 11*23=253, 253-108=145, 145-108=37, 37-36=1.

29.08.2020, 11:13

msaedicn3123

Auf diesen Beitrag antworten »

Die "spielerische" Methode verstehe ich nicht wirklich!?

im euklidischen Algorithmus wäre es folgende Rechnung für bspw. das Paar [17]=[17]:
36 = 2 * 17 +2
17 = 8 * 2 +1
2 = 2 * 1 +0
dann weiter mit dem erweiterten euklidischen Algorithmus:
1 = 17 - 8 * 2
= 17 - 8 * (36 - 2 * 17)
= (-8) * 36 + 17 * 17
wäre in Restklassen:
[1]=[-8] * [36] + [17] * [17]
[1]=[-8] * [0] + [17] * [17]
[1]=[17] * [17]

Das ist meine Rechnung, die ich für jedes der Paare durchführe. Dauert sehr lange und ist etwas fehleranfällig.

@Elvis: ich würde also die Restklassen von vorne beginnend durchprobieren?
Es tatsächlich sehr viel schneller, als in meiner Variante.
____
Zum Verständnis:
(1) Muss jede teilerfremde Restklasse eine multiplikative Inverse haben?
(2) Ist die multiplikative Inverse [1] = [1] * [1] von vornherein für jede Inverse festgelegt?
(3) Ist es bei den additiv Inversen die [0] als neutrales Restklassen-Element?

Danke für eure Hilfe!!

29.08.2020, 11:25

Elvis

Auf diesen Beitrag antworten »

Der erweiterte euklidische Algorithmus ist bestens geeignet, wenn man z.B. den ggT von zwei Elementen berechnen möchte. Hier scheint er mir ein bißchen zu dick aufgetragen, aber theoretisch ist er immerhin geeignet, zu beweisen, dass jede prime Restklasse mod m eine inverse prime Restklasse hat.

(1) Jede invertierbare Restklasse hat genau ein inverses. Das ist eine Gruppeneigenschaft, und die primen Restklassen mod m sind eine multiplikative Gruppe. Ebenso bilden die Restklassen mod m eine additive Gruppe.
(2) 1*1=1 ist eindeutig. 1 ist das neutrale Element der primen Restklassengruppe mod m.
(3) 0+0=0 ist eindeutig. 0 ist das neutrale Element der Restklassengruppe mod m.

Nachtrag: Man kann auch schnell mal (mit Excel) die Reste mod 36 der Potenzen der primen Elemente mod 36 berechnen. Das inverse Element tritt genau dann auf, wenn die nächste Potenz 1 ergibt. Man muss offensichtlich nicht alle primen Elemente berücksichtigen. Übrigens beweist auch diese Methode, dass jede prime Restklasse genau eine prime Restklasse als inverses Element hat, denn jedes Gruppenelement einer endlichen Gruppe hat endliche Ordnung.

29.08.2020, 20:23

msaedicn3123

Auf diesen Beitrag antworten »

Ok check, das kann ich nachvollziehen. Danke.

30.08.2020, 09:01

Leopold

Auf diesen Beitrag antworten »

RE: Multiplikativ invertierbare Elemente von Z_{36} bestimmen
Wenn das die Aufgabenstellung ist:

Zitat:

Original von msaedicn3123
Bestimmen Sie die multiplikativ invertierbaren Elemente von Z_{36}.

dann wäre die Frage, ob es des ganzen Aufwandes überhaupt bedarf. Hier steht ja nichts davon, daß man die Inversen der invertierbaren Elemente bestimmen soll. (Nun gut, schaden tut es auch nichts, wenn man den Euklidischen Algorithmus übt oder sich mit Potenzen in $\begin{align*} {\mathbb{Z}_{36}}^{*} \end{align*}$ beschäftigt.)

Neue Frage »

Antworten »

Multiplikativ invertierbare Elemente von Z_{36} bestimmen

Verwandte Themen