Bestimmen Sie ein Element z E Z63, für das z °63 47 = 1 erfüllt ist

Question

Aufgabe:

a) Verwenden Sie den euklidischen Algorithmus um den größten gemeinsamen Teiler von 63 und 47 zu bestimmen.

b) Ermitteln Sie \( x, y \in \mathbb{Z} \) mit \( 63 x+47 y=\operatorname{ggT}(63,47) \).

c) Bestimmen Sie ein Element \( z \in \mathbb{Z}_{63} \), für das \( z \bullet_{63} 47=1 \) erfüllt ist.

d) Berechuen Sie ein Element \( l \in \mathbb{Z}_{63} \), welches \( t \bullet_{63} 47=5 \) erfüllt.

Die Aufgabenteile a) & b) sind kein Problem.

Bei c) & d) weiß ich überhaupt nicht was zu tun ist. Worum geht es da und was muss man da machen?

Die Aufgabe ist vermutlich von http://reh.math.uni-duesseldorf.de/~bogopolski/pdfs/LA_I_SS_2012/LA1KlausurSoSe12.pdf

Comments

a) ist noch recht einfach

63 mod 47 = 16
47 mod 16 = 15
16 mod 15 = 1
15 mod 1 = 0

Damit ist 1 der größte gemeinsame Teiler.

---

zu c) und d) Du sollst die beiden Gleichungen lösen.

---

Ich weiß bei c) und d) aber einfach nicht wie ich da vorgehen oder anfangen soll.

---

@Anonym: Es geht offenbar um c) und d).
Ich verstehe nicht, was

z° 63 47=1  sein soll. Kannst du mal aufschreiben, wie man das vorlesen würde?

---

Übersetzungshilfe:

c) 47*z == 1 mod 63
d) 47*i == 5 mod 63

(Das dämliche l in d) habe ich vermieden!)

---

Ich kann dir leider auch nicht wirklich sagen, was das bedeutet. Unter anderem deshalb weiß ich auch nicht was zu tun ist

---

@Fragesteller: Das sind lineare Kongruenzgleichungen, dafür gibt es Rechenregeln. Unter anderem kann man Vielfache des Moduls addieren.

---

b)

63x + 47y = 1

y = (1 - 63·x)/47 = (1 - 47·x - 16·x)/47

x = 47·n + 3

y = (1 - 63·(47·n + 3))/47 = - 63·n - 4

---

@Der_Mathecoach: b) war nach Aussage des Fragestellers kein Problem. Aber wo es schon da steht, liefert die letzte Zeile fast unmittelbar die Lösung zu c)!

---

Wenn man in der Formel von Mathecoach n=1 einsetzt, kommt man auf das Resultat z=59, das auch WolframAlpha vorschlägt

https://www.wolframalpha.com/input/?i=47*z+%3D%3D+1+mod+63

Bei d) kommt WolframAlpha auf i=43

---

@Lu: Minus 1!

(Um mit zweistelligen Zahlen zu rechnen, benötigt man nicht unbedingt WolframAlpha...)

---

Ich finde es eigentlich immer bei solchen Aufgaben wichtig wenn man auch die ersten Teilaufgaben löst, weil die Anhaltspunkte auf die weiteren Aufgabenteile liefern.

es wäre schön gewesen wenn a) und b) kein Problem ist, wenn der Fragesteller die Lösungen mit dazu geschrieben hätte. Dann hätte ich mir die Arbeit erspart.

---

Danke für die Hilfe! @Der_Mathecoach: Ich merks mir :) Danke !

---

c) (47z) mod 63 = 1

z = 59

d) (47z) mod 63 = 5

z = 43

---

Vorschlag zu d) mit (ausführlicher) Rechnung (ohne WA):

47i ≡ 5

-16i ≡ 5   |   *(-4)

64i ≡ -20

i ≡ 43 (mod 63).

---

Schönerer Vorschlag für d) mit dem Ergebnis 59*47 ≡ 1 (mod 63) von c):

47i ≡ 5  ⇔  59*47i ≡ 59*5  ⇔  i ≡ -4*5 = -20 ≡ 43 (mod 63).

Answer 1

Ich fasse das ganze nochmal als gesammelte Antwort zusammen:

a) 

63 mod 47 = 16
47 mod 16 = 15
16 mod 15 = 1
15 mod 1 = 0

b)

63x + 47y = 1
y = (1 - 63·x)/47 = (1 - 47·x - 16·x)/47
x = 47·n + 3
y = (1 - 63·(47·n + 3))/47 = - 63·n - 4

c)

47z ≡ 1 mod 63
-16z ≡ 1 mod 63
z ≡ 59 mod 63

d) 

47z ≡ 5 mod 63
-16z ≡ 5 mod 63
64z ≡ -20 mod 63
z ≡ 43 mod 63
 

Comments

Hi, zu d) würde ich allerdings meine an anderer Stelle notierte, zweite
Variante bevorzugen, da die das Ergebnis von c) sinnvoll weiterverwendet.

Die Roadmap zu der gesamten Aufgabe wäre:
löse a) mit dem euklidischen Algorithmus,
löse b) mit dem Ergebnis von a) und dem erweiterten euklidischen Algorithmus,
löse c) mit dem Ergebnis von b) und
löse d) mit dem Ergebnis von c).