Kryptologie/Teilbarkeit und Teilerfremdheit

Aus Wikiversity

Einleitung

Die Teilbarkeit ist eine grundlegende mathematische Beziehung zwischen zwei Zahlen, auf die sich beispielsweise die Kongruenz und viele weitere wichtige Sätze dieses Kurses stützen[1]. Dies gilt sowohl für die Lerninhalte des Caesar- als auch für die des RSA-Kryptosystems.

Teilbarkeit

Definition Teilbarkeit

Seien .

teilt genau dann, wenn es eine Zahl gibt, für die ist. Wir sagen dann „ ist Teiler von “, „ teilt “ oder „ ist teilbar durch “ und schreiben formal:

[2][3].

Für das Gegenteil, wenn es also keine Zahl gibt, für die ist, sagen wir „ ist kein Teiler von “, „ teilt nicht“ oder „ ist nicht teilbar durch “ und schreiben:

[2][3].

Beispiel

bzw. ist ein Teiler von , da .

, da und

Bemerkung: Wir zeigen nun einige wichtige Eigenschaften der Teilbarkeit, die wir später in Beweisen benötigen werden.

Lemma

Seien , dann gilt:

: [4]

: [5]

: und für beliebige [5]

: [6]

Beweis Lemma

Zu :

Teilbarkeit
Teilbarkeit
Eine ganze Zahl teilt eine ganze Zahl genau dann, wenn es eine

ganze Zahl gibt, für die ist.

Wir schreiben [2][3].

Voraussetzung

und

Zu zeigen

Beweis

Nach Voraussetzung gilt

, für ein und nach Definition Teilbarkeit

, nach Definition Teilbarkeit[7]


Zu :

Voraussetzung

und

Zu zeigen

Teilbarkeit
Teilbarkeit
Eine ganze Zahl teilt eine ganze Zahl genau dann, wenn es eine

ganze Zahl gibt, für die ist.

Wir schreiben [2][3].

Beweis

Nach Voraussetzung gilt:

, da nach Definition Teilbarkeit für ein

Gesucht sind nun , für gilt.

Dies sind genau [5]

Zu :

Voraussetzung

, und

Zu zeigen

Teilbarkeit
Teilbarkeit
Eine ganze Zahl teilt eine ganze Zahl genau dann, wenn es eine

ganze Zahl gibt, für die ist.

Wir schreiben [2][3].

und für beliebige

Beweis

Aus der Definition der Teilbarkeit folgt für bzw.

für

bzw.

für .

Wir können die beiden Gleichungen jeweils mit einer beliebigen ganzen Zahl bzw. multiplizieren und erhalten

bzw.

Wir addieren in der Gleichung und erhalten

, da

Da eine ganze Zahl ist, gilt nach Definition der Teilbarkeit

[5]

Zu :

Siehe Lernaufgabe.

Teilerfremdheit

Definition Teilerfremdheit

Seien .

und , wobei mindestens oder ungleich Null, heißen teilerfremd, wenn es keine Zahlen außer gibt, die beide Zahlen teilt. Wir sagen dann „ und sind teilerfremd".

Betrachten wir mehr als zwei Zahlen, dann nennen wir diese paarweise teilerfremd, wenn je zwei beliebige von diesen Zahlen zueinander teilerfremd sind[8][9].

Größte gemeinsame Teiler
Größte gemeinsame Teiler
Seien , wobei mindestens eine der beiden Zahlen ungleich Null.

Wir bezeichnen mit als den größten gemeinsamen

Teiler der Zahlen und , falls gilt:

: und

und

: Für alle mit und gilt [10].

Alternative

Ist der größte gemeinsame Teiler bekannt, so kann man die Definition auch anders formulieren:

Seien .

und , wobei mindestens einer der beiden Zahlen ungleich Null ist, heißen teilerfremd, wenn [9].

Bemerkung: Besonders die alternative Definition wird uns in anderen Lerneinheiten von großem Nutzen sein.

Lernaufgabe

Aufgabe

Optionaler Hinweis
Nutzen Sie das Lemma zur Teilbarkeit:
Seien , dann gilt: [4]

Seien und .

Beweisen Sie, dass gilt: .

Lösung
Voraussetzung

und

Zu zeigen

Beweis

Nach Voraussetzung gilt

, für mit

, nach des Lemmas der Teilbarkeit

, nach

Lernempfehlung

Kursübersicht
Übergeordnete Lerneinheit
4: Caesar-Verschlüsselungsverfahren
Vorherige Lerneinheit Aktuelle Lerneinheit Empfohlene Lerneinheit
4: Caesar-Verschlüsselungsverfahren 4.1: Teilbarkeit und Teilerfremdheit 4.2: Größte gemeinsame Teiler

Literatur

  1. Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Berlin, Heidelberg: Springer. S. 37.
  2. 2,0 2,1 2,2 2,3 2,4 Seite „Teilbarkeit“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 25. November 2019, 15:44 UTC. URL: https://de.wikipedia.org/w/index.php?title=Teilbarkeit&oldid=194364839 (Abgerufen: 12. Dezember 2019, 14:43 UTC; Formulierung verändert)
  3. 3,0 3,1 3,2 3,3 3,4 Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Heldermann Verlag. S. 22f.
  4. 4,0 4,1 Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Heldermann Verlag. S. 29.
  5. 5,0 5,1 5,2 5,3 Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Lemgo: Heldermann Verlag. S. 23.
  6. Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Berlin, Heidelberg: Springer. S. 38.
  7. Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Heldermann Verlag. S. 472.
  8. Seite „Teilerfremdheit“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 26. September 2019, 13:33 UTC. URL: https://de.wikipedia.org/w/index.php?title=Teilerfremdheit&oldid=192615323 (Abgerufen: 10. Januar 2020, 13:56 UTC; Formulierung verändert)
  9. 9,0 9,1 Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Lemgo: Heldermann Verlag. S. 26.
  10. Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Lemgo: Heldermann Verlag. S. 24.