0 Daumen
134 Aufrufe


Aufgabe:

Berechne mit Hilfe des euklidischen Algorithmus das Inverse von e = 12 in der mutliplikativen Gruppe (ℤ*119, *119). (Erinnerung: Es ist a *119 b = Rest (a * b, 119) für zwei Zahlen a, b ∈ ℤ)


Problem/Ansatz:

Ich habe es kaum für möglich gehalten, aber ich habe tatsächtlich nach 2319 Jahren seit dessen Existenz, geschafft den euklidischen Algorithmus zu widerlegen. Es gibt zwei Möglichkeiten: Entweder werde ich diesen Beitrag ganz schnell wieder löschen und mich beim Nobelpreis-Komittee anmelden, bevor das jemand anders sieht und mir zu vorkommt, oder ich hab ganz einfach Kakolores gerechnet.

j
kj
rj
0
-
119
1
\( \frac{119}{12} \) = 9, Rest 11
12
2
\( \frac{12}{11} \) = 1, Rest 1
\( \frac{119}{12} \) = 9, Rest 11
=> r2 = 11
3
\( \frac{11}{1} \) = 11, Rest 0
\( \frac{12}{11} \) = 1, Rest 1
=> r3 = 11


Der euklidische Algorithmus terminiert bei kj = 11. 11 teilt aber weder die 12, noch 119. Der Euklidische Algorithmus fällt hier also in sich zusammen. Reeductio ad absurdum

von

2 Antworten

+1 Daumen

Das Inverse von e = 12 in der mutliplikativen Gruppe (ℤ*119, *119) ist 10, denn 12·10≡1 mod 119.

von 84 k 🚀
+1 Daumen
11 teilt aber weder die 12, noch 119.

Der ggT von 119 und 12 ist 1 (letzter Rest im Euklidschen Algorithmus). Der ggT bestimmt sich über den letzten Rest den man hatte und nicht über die letzte Zahl die du im Algorithmus teils.

12·x ≡ 1 mod 119

119 : 12 = 9 R 11 → 11 = 119 - 9·12
12 : 11 = 1 R 1 → 1 = 12 - 1·11
11 : 1 = 11 R 0

1 = 12 - 1·11
1 = 12 - 1·(119 - 9·12) = 10·12 - 1·119

x = 10 ist also das multiplikativ inverse zu 12.

von 346 k 🚀

Aber beim ggT (15,109) ist es z.B. auch so, dass sich der euklidische Algorithmus über die letzte Zahl bestimmt, die man im Algorithmus teilt und nicht über den Rest


j
kj
rj
sj
tj
0
-
109
1
0
1
\( \frac{109}{15} \) = 7, Rest 4
15
0
1
2
\( \frac{15}{4} \) = 3 Rest 3
\( \frac{109}{15} \) = 7 Rest 4
=> r2 = 4
1 - 7 * 0 = 1
0 - 7 * 1 = -7
3
\( \frac{4}{3} \) = 1 Rest 1
\( \frac{4}{3} \) = 1 Rest 1
=> r3 = 3
0  - 3* 1 = 3
1 - 3* (-7) = 22
4
\( \frac{3}{1} \) = 1 Rest 0
\( \frac{3}{1} \) = 1 Rest 1
=> r4 = 1
1 - 1 * -3 = 4
(-7) - 1 * 22  = -29

Der Euklidische Algorithmus determiniert hier an der Stelle, wo der Rest gleich 0 ist, nämlich bei j = 4. Warum wird hier der Algorithmus über den Rest terminiert, und bei der Aufgabe oben +ber de letzte Zahl, die man teilt.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community