Euklidischer Algorithmus widerlegt?

Question

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

Answer 1

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

Answer 2

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.

Comments

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.