Rechnen mit Restklassen: Teilbarkeitsregeln

Die Addition und die Multiplikation sind invariant gegenüber der Restklassenbildung. Aus dieser Tatsache lassen sich leicht die Teilbarkeitsregeln herleiten, mit denen man schnell entschieden kann, ob eine Zahl z durch eine andere Zahl k geteilt werden kann oder welcher Rest bei der Division bleibt.

walter
QuersummenregelRestklasseGanzzahl-DivisionEndstellenregelKongruenzMultiplikationstabellemoduloTeilbarkeitsregel
Inhaltsverzeichnis

Einordnung des Artikels

Einführung

Die bisherigen Untersuchungen zu Äquivalenzrelationen und Äquivalenzklassen wirkten sehr abstrakt. In diesem Kapitel wird als Anwendung gezeigt, wie man Teilbarkeitsregeln herleiten kann. In den R-Skripten wird dann gezeigt, wie man sich zu einem beliebigen Teiler die Teilbarkeitsregel berechnen lassen kann.

Voraussetzung zum Verständnis dieses Kapitels sind nur elementare Kenntnisse über Multiplikation und Division, konsequent eingesetzt werden aber die Bezeichnungen aus Ganzzahl-Division: Kongruenzen und Restklassen als Beispiele für Äquivalenzrelationen und Äquivalenzklassen.

Rechnen mit Restklassen

Beispiel zur Einführung: Rechnen in den Restklassen modulo 4 beziehungsweise modulo 2

In Ganzzahl-Division: Kongruenzen und Restklassen als Beispiele für Äquivalenzrelationen und Äquivalenzklassen wurde mehrfach die Abbildung erläutert, die unten als Abbildung 1 nochmals wiedergegeben ist.

Abbildung 1: Kongruenz zwischen Zahlen, die bei Division durch 4 den gleichen Rest besitzenAbbildung 1: Kongruenz zwischen Zahlen, die bei Division durch 4 den gleichen Rest besitzen

Insbesondere wurde argumentiert, dass man den Kreis unten als die Zerlegung der ganzen Zahlen in vier Restklassen interpretieren kann. Das heißt jeder Viertelkreis steht für unendlich viele ganze Zahlen, die bei Division durch 4 entweder den Rest 0, den Rest 1, den Rest 2 oder den Rest 3 ergeben.

Diese Überlegung soll jetzt noch weitergeführt werden: Da die Elemente der Restklasse alle gleichberechtigt sind, aber schon die Auswahl eines Repräsentanten die gesamte Restklasse festlegt, kann man auch einen bevorzugten Repräsentanten wählen. Dafür bietet sich der Rest r an, der bei Division durch 4 die Werte

r = 0, 1, 2, 3

annehmen kann. In dieser Interpretation von Abbildung 4 unten, stellt der Kreis diese vier ausgezeichneten Repräsentanten dar (wobei jederzeit aus dem Repräsentanten die komplette Restklasse rekonstruiert werden kann).

Was ist damit gewonnen? Man ist nicht mehr genötigt mit den Restklassen, also mit unendlichen Mengen, zu hantieren, sondern kann mit 4 Zahlen rechnen; im allgemeinen Fall der Restklassen zum Teiler k sind es k Zahlen – also eine endliche Menge. Und wie noch gezeigt wird, kann man mit den ausgezeichneten Repräsentanten – sinnvoll – rechnen.

Addiert man zwei der möglichen Reste 0, 1, 2, 3 und bildet vom Ergebnis wieder den Rest modulo 4, so hat man eine neue "Addition" auf der Menge {0, 1, 2, 3} definiert. Um sie von der üblichen Addition zu unterscheiden, wird sie mit ⊕ bezeichnet. Es gilt zum Beispiel:

1 ⊕ 1 = 2, 1 ⊕ 2 = 3, 2 ⊕ 2 = 0, 2 ⊕ 3 = 1 und so weiter.

Alle möglichen Additionen innerhalb der Menge {0, 1, 2, 3} sind in der Additionstabelle in Abbildung 2 oben dargestellt.

Man beachte, dass man eigentlich auch die Zahlen 0, 1, 2, 3 mit eigenen Symbolen bezeichnen sollte, da sie für den ausgezeichneten Repräsentanten der Restklasse und nicht für eine ganze Zahl stehen. Im Folgenden wird daher die Konvention verwendet, dass mit der Addition ⊕ stets die ausgezeichneten Repräsentanten verknüpft werden.

Wie mit der Addition kann man auch mit der Multiplikation auf {0, 1, 2, 3} verfahren, die jetzt mit dem Symbol ⊗ bezeichnet wird. Die entsprechende Multiplikationstabelle ist in Abbildung 2 unten dargestellt.

Abbildung 2: Additions- und Multiplikationstabelle für die Restklassen modulo 4.Abbildung 2: Additions- und Multiplikationstabelle für die Restklassen modulo 4.

Noch einfacher sind die Additions- und Multiplikationstabelle für die Restklassen modulo 2. Jetzt besteht die relevante Menge, auf der die Addition und die Multiplikation definiert sind, aus zwei Elementen: {0, 1}.

Abbildung 3: Additions- und Multiplikationstabelle für die Restklassen modulo 2.Abbildung 3: Additions- und Multiplikationstabelle für die Restklassen modulo 2.

Man fragt sich natürlich, welche Bedeutung diese Tabellen haben. Gerade für den Teiler 2 ist die Antwort sehr einfach: Die Restklassen bestehen aus den geraden beziehungsweise ungeraden Zahlen. Die ausgezeichneten Repräsentanten 0 und 1 sind somit die einfachsten Vertreter einer geraden und einer ungeraden Zahl. Und die Tabellen geben gerade die bekannten Rechenregeln wieder:

Addiert man zwei gerade Zahlen oder zwei ungerade Zahlen, ergibt sich eine gerade Zahl.

Addiert man eine gerade und eine ungerade Zahl, ergibt sich eine ungerade Zahl.

Ist ein Faktor bei einer Multiplikation gerade, so ist das Ergebnis gerade.

Sind beide Faktoren ungerade, ist das Produkt ungerade.

Da in den Restklassen modulo 2 von allen anderen Eigenschaften der Zahlen abstrahiert wurde, können die Tabellen nur noch diese Rechenregeln wiedergeben.

Entsprechend kann man aus den Tabellen für die Addition und Multiplikation in den Restklassen modulo 4 die analogen Regeln ablesen. Das folgende Beispiel zeigt, dass wir mit derartigen Regeln nicht so vertraut sind wie mit denen für die Restklassen modulo 2:

Besitzt ein Produkt a · b den Rest 3 bei Division durch 4, so muss ein Faktor den Rest 1 und ein Faktor den Rest 3 besitzen.

Wie man an der Multiplikationstabelle sieht, gibt es keine andere Kombination, die zu einem Produkt in R[3] führt.

Ausblick: In den folgenden Abschnitten wird gezeigt, wie man von den Restklassen zu den ausgezeichneten Repräsentanten übergehen kann und welche mathematischen Begriffsbildungen dazu notwendig sind. Dies Überlegungen werden sehr abstrakt wirken – es muss wieder mit Eigenschaften von Relationen argumentiert werden –, aber sie werden die Grundlage für wertvolle Anwendungen liefern: Die Teilbarkeitsregeln können aus den Rechenregeln für die "ausgezeichneten Repräsentanten" hergeleitet werden.

Invarianz einer Abbildung gegenüber einer Äquivalenzrelation

In Ganzzahl-Division: Kongruenzen und Restklassen als Beispiele für Äquivalenzrelationen und Äquivalenzklassen wurde gezeigt, wie eine Äquivalenzrelation ≡ auf einer Menge M Äquivalenzklassen R[x] induziert und dass die Menge der Äquivalenzklassen eine Zerlegung bilden (sie sind disjunkt und ihre Vereinigung liefert die Menge M). Ferner kann jede Äquivalenzklasse eindeutig bestimmt werden, wenn ein Repräsentant daraus bekannt ist.

Für die weiteren Überlegungen wird eine beliebige Abbildung V auf M × M mit Werten in M betrachtet:

V: M × M → M, (x, y) → V (x, y), mit x, y ∈ M.

Die folgende Definition wird in ihrer allgemeinen Form angegeben, sie wird aber später nur für zwei Spezialfälle verwendet:

  1. Die Abbildung V ist die Addition auf den ganzen Zahlen Z: V(x, y) = x + y.
  2. Die Abbildung V ist die Multiplikation auf den ganzen Zahlen Z: V(x, y) = x · y.

Definition: Es sei ≡ eine Äquivalenzrelation auf einer Menge M. Eine Abbildung V: M × M → M heißt invariant gegenüber den Äquivalenzklassen von ≡, wenn für alle x, y ∈ M gilt:

Sind x', y' ∈ M und ist x' ≡ x und y' ≡ y, dann ist

V(x, y) ≡ V(x', y').

♦ ♦ ♦ ♦ ♦ ♦

Salopp formuliert bedeutet diese Invarianz folgendes: Verknüpft man zwei Elemente x und y mit V oder zwei dazu äquivalente Elemente x' und y', so sind die Ergebnisse wiederum äquivalent.

Dass diese Invarianz keine Selbstverständlichkeit ist, soll das folgende Gegenbeispiel zeigen.

Gegenbeispiel: Auf der Menge der ganzen Zahlen werde als Äquivalenzrelation die Kongruenz modulo 4 betrachtet. Die Abbildung V sei das Maximum zweier Zahlen:

V(x, y) = max(x, y), x, y ∈ Z.

Wählt man zum Beispiel x = 3 und y = 2, so ist max(x, y) = 3.

Die Zahlen x' = 3 und y' = 6 sind äquivalent zu x und y. Verknüpft man sie mit V, erhält man

max(x', y') = max(3, 6) = 6.

Aber die beiden Ergebnisse 3 beziehungsweise 6 sind modulo 4 nicht kongruent, daher ist V nicht invariant gegenüber den Restklassen modulo 4.

Invarianz der Addition und der Multiplikation gegenüber der Kongruenz modulo k

Der folgende Satz beschreibt das zentrale Ergebnis dieses Kapitels, aus dem dann die Teilbarkeitsregeln hergeleitet werden.

Satz (Invarianz von Addition und Multiplikation gegenüber den Restklassen modulo k): Ist k > 1 eine natürliche Zahl, dann sind die Addition und die Multiplikation invariant gegenüber den Restklassen modulo k.

Beweis:

1. Addition:

Sind x und y zwei ganze Zahlen, sowie x' und y' zwei weitere ganze Zahlen, die zu x beziehungsweise y kongruent modulo k sind, so ist zu zeigen, dass x + y kongruent ist zu x' + y' modulo k.

Nach Voraussetzung gibt es ganze Zahlen n und m, so dass

x' - x = n · k und y' - y = m · k.

Addiert man die beiden Gleichungen, so erhält man:

x' + y' - (x + y) = (n + m) · k.

Da aber n + m wiederum eine ganze Zahl ist, besagt diese Gleichheit gerade, dass x' + y' und x + y kongruent sind modulo k.

2. Multiplikation:

Man verwendet die Bezeichnungen wie unter Addition und muss zeigen, dass x' · y' kongruent ist zu x · y modulo k.

Löst man zum Beispiel obige Gleichungen, die n und m einführen nach x' und y' auf und multipliziert die beiden Gleichungen miteinander, erhält man:

x' = n · k + x, y' = m · k + y ⇒

x' · y' = (n · k + x) · (m · k + y) = k · (nmk + ny + nx) + x · y.

Nach den Voraussetzungen ist der Faktor bei k eine ganze Zahl und somit sind x' · y' und x · y kongruent modulo k.

Einfache Anwendungsbeispiele:

Nach dem Satz spielt es kein Rolle, ob man bei einer Addition beziehungsweise Multiplikation zweier Zahlen

In beiden Fällen erhält man das identische Ergebnis, nämlich eine Zahl, die zur Summe beziehungsweise zum Produkt kongruent ist. Klar ist, dass die erste Variante weniger Rechenaufwand beinhaltet.

Sucht man etwa eine Zahl, die zu

237 + 683 kongruent ist modulo 10, so kann man rechnen:

237 ≡ 7 (mod 10), 683 ≡ 3 (mod 10) ⇒ 237 + 683 ≡ 7 + 3 (mod 10) ≡ 0 (mod 10).

Oder man kann rechnen:

237 + 683 = 920 ≡ 0 (mod 10)

Überzeugender ist vielleicht die Multiplikation:

237 · 683 ≡ 7 · 3 (mod 10) ≡ 21 (mod 10) ≡ 1 (mod 10)

237 · 683 = 161871 ≡ 1 (mod 10).

Die erste Berechnung kann man ohne Taschenrechner durchführen, die zweite Rechnung nur etwas mühsam.

Vollständiges Restsystem

Der zuletzt bewiesene Satz bildet die Grundlage für alle nun folgenden Überlegungen. Um die Schreibweisen zu vereinfachen, wird noch ein weiterer Begriff eingeführt, der konkretisiert, was in der Einführung mit den "ausgezeichneten Repräsentanten einer Restklasse" gemeint war.

Denn auch die einfachen Anwendungsbeispiele oben haben schon ein Problem angedeutet: Bei einer Kongruenz wie in 237 ≡ 7 (mod 10) ist nicht klar, welchen Repräsentanten der Restklasse man auf der rechten Seite angeben soll. Die Äquivalenzklassen wurden ja gerade eingeführt, um Berechnungen von der Auswahl des Repräsentanten unabhängig zu machen. Man kann also genau so gut schreiben 237 ≡ 348527 (mod 10). Aber damit werden die Berechnungen nicht einfacher. Sinnvoll erscheint es daher – wie es in den Beispielen ohne ausdrückliche Erwähnung gemacht wurde – immer möglichst einfache Repräsentanten anzugeben. Und dafür bieten sich natürlich die Reste 0, 1, 2, ..., k - 1 an. Ein Blick auf die Additions- und Multiplikationstabellen in Abbildung 2 und 3 zeigt genau diese Vorgehensweise. Es soll aber ausdrücklich betont werden, dass dies eigentlich der Absicht widerspricht, mit der die Äquivalenzklassen eingeführt wurden: sie sollten gerade die Äquivalenz aller Repräsentanten einer Klasse ausdrücken.

Definition:

Unter einem vollständigen Restsystem zu den Restklassen modulo k, mit k > 1, versteht man eine Menge von k Zahlen, wobei jede Zahl einer anderen Restklasse R[0], R[1], ..., R[k - 1] angehört.

Beispiele:

Naheliegend ist es, für das vollständige Restsystem die Reste selbst zu wählen. Für k = 10 erhält man

{0, 1, 2, ..., 9}.

Gleichwertig ist aber das vollständige Restsystem

{-4, -3, -2, -1, 0, 1, 2, 3, 4, 5}.

Dieses vollständige Restsystem hat den Vorteil, dass der Betrag der enthaltenen Zahlen möglichst klein ist.

Man kann auch exotische vollständige Restsysteme wählen, wie

{0, 11, 22, 33, ..., 99}.

Multiplikationstabellen mit einem vollständigen Restsystem

Der Begriff des vollständigen Restsystems gibt ein besseres Verständnis für die Additions- und Multiplikationstabelle etwa in Abbildung 2; man kann diese Tabellen und die Addition ⊕ beziehungsweise die Multiplikation ⊗ auf zwei Arten interpretieren:

  1. Die Elemente x und y, die in den Tabellen verknüpft werden, sind Repräsentanten einer Restklasse. Somit stehen sie für unendlich viele kongruente Zahlen und das Restsystem legt fest, welcher Repräsentant aus der Restklasse ausgewählt wird. Die Ergebnisse der Verknüpfung werden dann ebenfalls mit diesem Repräsentanten angegeben. Die Operationen ⊕ und ⊗ sind in dieser Interpretation Verknüpfungen auf den Restklassen.
  2. Die Operationen ⊕ und ⊗ werden auf einer neuen Menge definiert, nämlich dem vollständigen Restsystem. Und die Tabellen geben die Definition dieser beiden Operationen bei Verknüpfung zweier Elemente an. In dieser Interpretation stehen also x und y nicht mehr für die komplette Restklasse, sondern nur noch für die durch das vollständige Restsystem ausgewählten Repräsentanten.

Nach der zweiten Interpretation wird man das vollständige Restsystem mit einem eigenen Namen bezeichnen, etwa Zk, und die Addition ⊕ beziehungsweise die Multiplikation ⊗ als Abbildung auf Zk × Zk definieren:

⊕ : Zk × Zk → Zk

⊗ : Zk × Zk → Zk

Man kann natürlich ein beliebiges vollständiges Restsystem auswählen und damit die Additions- und Multiplikationstabelle bilden. Abbildung 4 zeigt diese Tabellen "modulo 4" mit dem vollständigen Restsystem Z4 = {-1, 0, 1, 2}.

Abbildung 4: Additions- und Multiplikationstabelle für die Restklassen modulo 4 mit dem vollständigen Restsystem {-1, 0, 1, 2}.Abbildung 4: Additions- und Multiplikationstabelle für die Restklassen modulo 4 mit dem vollständigen Restsystem {-1, 0, 1, 2}.

In Die Komponenten des von Neumann Rechners: elektrotechnische Grundlagen wurde erklärt, wie man einen Zähler als elektrische Schaltung realisiert; in Stellenwertsysteme und Umrechnung zwischen den wichtigsten Zahlensystemen: Dezimalsystem, Hexadezimalsystem, Dualsystem wurde der entsprechende mechanische Zähler vorgestellt, der mit Walzen arbeitet. Die Diskussion des vollständigen Restsystems und die Additionstabellen ⊕ auf Zk liefern den theoretischen Hintergrund zu diesen Anwendungen.

Aufgabe:

Berechnen Sie die Additions- und Multiplikationstabelle "modulo 5" zu den vollständigen Restsystemen {0, 1, 2, 3, 4} beziehungsweise {-2, -1, 0, 1, 2}.

Nullteiler

In den ganzen Zahlen Z gilt folgende Rechenregel:

Ist ein Produkt a · b = 0, so muss mindestens eine der beiden Zahlen a, b gleich null sein.

Die Multiplikationstabelle "modulo 4" zeigt, dass das Ergebnis einer Multiplikation gleich null sein kann, obwohl keiner der Faktoren gleich null ist:

2 ⊗ 2 = 0.

Eine Zahl wie 2 ∈ Z4 wird als Nullteiler bezeichnet.

Aufgaben:

  1. Gibt es in der Multiplikationstabelle "modulo 5" Nullteiler?
  2. Versuchen Sie eine Erklärung zu geben, wann Nullteiler in einer Menge Zk auftreten.

Anwendungen

Teilbarkeitsregeln

Die Problemstellungen

Die Einfachen Anwendungsbeispiele von oben mögen wenig überzeugend wirken: wann benötigt man schon derartige Rechnungen? Die folgende Aufgabe zeigt, welch weitreichende Folgerungen aus dem Satz über die Invarianz von Addition und Multiplikation gegenüber den Restklassen modulo k gezogen werden können.

Aufgabe:

In der Schule haben Sie sicher Teilbarkeitsregeln kennengelernt:

  1. Versuchen Sie möglichst viele davon zu formulieren!
  2. Haben Sie eine Begründung kennengelernt, warum diese Regeln gelten? Versuchen Sie selbst eine Begründung zu geben!
  3. Versuchen Sie einen Zusammenhang zwischen den Teilbarkeitsregeln und den Begriffen Restklasse, Invarianz der Addition und Multiplikation gegenüber Restklassen herzustellen.
  4. Versuchen Sie eine Regel herzuleiten, wann eine Zahl durch 7 teilbar ist.
  5. Versuchen Sie zu formulieren, wie man eine Teilbarkeitsregel für einen beliebigen Teiler herleiten kann.
  6. Die Teilbarkeitsregeln werden meist so formuliert, dass man aus ihnen ablesen kann, ob eine Zahl durch einen Teiler k teilbar ist oder nicht. Kann man derartige Regeln auch dafür einsetzen, um den Rest bei einer Division durch k zu bestimmen?

Bestandteil der Schulmathematik ist üblicherweise Aufgabe 1: Meist werden die Teilbarkeitsregeln für 2, 3, 4, 5, 6, 8, 9, 10 formuliert, an mehreren Beispielen überprüft und dann nur noch angewendet – aber nur selten begründet oder die allgemeine Vorgehensweise zu ihrer Herleitung skizziert.

Die Lösungen zu den Aufgaben 2 bis 6 werden im Folgenden geliefert. Die Herleitung der Teilbarkeitsregeln wird zeigen, dass ihre "Form" davon abhängt, ob der Teiler k

Dabei wird sich zeigen, dass es zwei Arten von Teilbarkeitsregeln gibt:

Diese Bezeichnungen mögen jetzt noch nichtssagend sein, werden aber sofort verständlich, wenn die entsprechenden Regeln auftreten.

Bezeichnungen

In den folgenden Unterabschnitten sollen Regeln formuliert werden, die angeben, ob eine gegebene Zahl z durch k teilbar ist oder nicht. Zusätzlich soll entschieden werden, welcher Rest bei der Division z ÷ k entsteht.

Die Zahl z soll n Stellen besitzen und ihre Ziffern werden mit dn - 1, ..., d1, d0 bezeichnet, es gilt also:

z = dn - 1 · 10n - 1 + ... + d1 · 101 + d0 · 100.

(Siehe auch: Stellenwertsysteme und Umrechnung zwischen den wichtigsten Zahlensystemen: Dezimalsystem, Hexadezimalsystem, Dualsystem, Abbildung 2)

Teilbarkeit durch 3

Es soll eine Regel formuliert werden, die angibt, ob eine gegebene Zahl z durch 3 teilbar ist oder nicht. Zusätzlich soll entschieden werden, welcher Rest bei der Division z ÷ 3 entsteht.

Der entscheidende Rechenschritt ist nun, dass die Gleichung, die z mit Hilfe der Ziffern ausdrückt (siehe Bezeichnungen oben), "modulo 3" gelesen wird. Dabei stehen auf der rechten Seite Summen von Produkten, auf die der Satz über die Invarianz der Addition und Multiplikation gegenüber den Restklassen angewendet werden kann.

Hilfreich ist dabei:

10 ≡ 1 (mod 3), 100 = 10 · 10 ≡ 1 (mod 3), ..., 10i ≡ 1 (mod 3).

Wendet man dies auf obige Darstellung von z an erhält man:

z ≡ dn - 1 + ... + d1 + d0 (mod 3).

Auf der rechten Seite steht somit die Quersumme der Zahl z, wobei alle Ziffern, die durch 3 teilbar sind aus der Quersumme entfernt werden können, da sie kongruent sind zu 0 (mod 3).

Aber das ist bereits die gesuchte Regel:

Eine Zahl ist durch 3 teilbar, wenn ihre Quersumme durch 3 teilbar ist.

Und es gilt sogar:

Der Rest bei Division einer Zahl z durch 3 stimmt mit dem Rest der Quersumme bei Division durch 3 überein.

Beispiel:

Für z = 38 975 472 und z + 1 soll der Rest bei Division durch 3 bestimmt werden. Es gilt 3 · 12 991 824 = 38975472, also ist der Rest gleich 0.

Die Anwendung obiger Regel liefert:

Quersumme (wobei durch 3 teilbare Ziffern bereits weggelassen werden): 8 + 7 + 5 + 4 + 7 + 2 = 33 ≡ 0 (mod 3).

z + 1 = 38 975 473 hat die Quersumme:

8 + 7 + 5 + 4 + 7 = 31 ≡ 1 (mod 3).

Teilbarkeit durch 9

Die Vorgehensweise zur Formulierung der Teilbarkeitsregel für den Teiler 3 lässt sich sofort auf den Teiler 9 übertragen – und liefert die nahezu identische Regel. Denn es gilt (mit den Bezeichnungen von oben):

10 ≡ 1 (mod 9) ⇒

100 = 10 · 10 ≡ 1 · 1 (mod 9) ≡ 1 (mod 9) ⇒

10n ≡ 1 (mod 9) für alle n = 1, 2, 3, ...

Und dadurch entsteht wieder die Quersumme, wenn man eine Zahl z untersucht:

z ≡ dn - 1 + ... + d1 + d0 (mod 9).

Eine Zahl ist durch 9 teilbar, wenn ihre Quersumme durch 3 teilbar ist.

Und es gilt sogar:

Der Rest bei Division einer Zahl z durch 9 stimmt mit dem Rest der Quersumme bei Division durch 9 überein.

Beispiel:

Für z = 38 975 472 und z + 1 soll der Rest bei Division durch 9 bestimmt werden.

In der Berechnung der Quersumme können Ziffern weggelassen werden, die gleich 9 sind:

Quersumme von z: 3 + 8 + 7 + 5 + 4 + 7 + 2 = 36 ≡ 0 (mod 9)

Quersumme von z + 1: 3 + 8 + 7 + 5 + 4 + 7 + 3 = 37 ≡ 1 (mod 9)

Test: 38 975 472 ÷ 9 = 4 330 608.

Die Teilbarkeitsregeln für 3 und 9 erklären sofort, warum oben von Quersummenregeln gesprochen wurde. Bei der Teilbarkeit durch 4 wird sich eine Endstellenregel ergeben.

Teilbarkeit durch 4

Eine Zahl ist durch 2 teilbar, wenn die letzte Ziffer gerade ist, andernfalls ist sie nicht durch 2 teilbar und bei der Division durch 2 bleibt Rest 1.

Wie man gesehen hat, lauten die Teilbarkeitsregeln für k = 3 und k = 9 = 32 sehr ähnlich. Man erwartet daher, dass die Teilbarkeitsregel für k = 4 ähnlich ist zu der Teilbarkeitsregel für k = 2.

Man geht wieder vor wie bei der Herleitung der Teilbarkeitsregel für 3 und benötigt:

10 ≡ 2 (mod 4) ⇒

100 = 10 · 10 ≡ 2 · 2 (mod 4) ≡ 0 (mod 4) ⇒

10n ≡ 0 (mod 4) für alle n = 2, 3, ...

Die Potenzen von 10 werden in einer Tabelle dargestellt – für den Teiler 4 ist dies kaum nötig, bei anderen Teiler wird sich diese Darstellung als sehr hilfreich erweisen:

n 0 1 2 3 ...
10n, n = 0, 1, 2, ... 1 10 100 1000 ...
10n (mod 4), n = 0, 1, 2, ... 1 2 0 0 ...

Liest man jetzt wieder die Darstellung von z durch Ziffern "modulo 4", erhält man:

z ≡ 2 · d1 + d0 (mod 4).

Das heißt die Teilbarkeit durch 4 wird allein durch die letzten beiden Ziffern bestimmt. Als Teilbarkeitsregel kann man daher auch schreiben:

Eine Zahl z ist durch 4 teilbar, wenn die aus den letzten beiden Ziffern gebildete Zahl

z2 = d1 · 101 + d0

durch 4 teilbar ist.

Gleichwertig:

Eine Zahl z ist durch 4 teilbar, wenn 2 · d1 + d0 ≡ 0 (mod 4).

Der Rest bei Division einer Zahl durch 4 wird bestimmt durch den Rest von z2 bei Division durch 4.

Beispiel:

Für z = 38 975 472 soll geprüft werden, ob sie durch 4 teilbar ist.

Da 72 = 18 · 4, ist sie durch 4 teilbar.

Alternativ untersucht man:

2 · 7 + 2 = 16 ≡ 0 (mod) 4.

Test:

38 975 472 ÷ 4 = 9 743 868.

Teilbarkeit durch 8

Man untersucht wieder die Potenzen von 10 auf ihre Teilbarkeit durch 8:

10 ≡ 2 (mod 8) ⇒

100 = 10 · 10 ≡ 2 · 2 (mod 8) = 4 (mod 8) ⇒

1000 = 10 · 100 ≡ 2 · 4 (mod 8) = 0 (mod 8) ⇒

10n ≡ 0 (mod 8) für alle n = 3, 4, ...

Man kann die Potenzen von 10 – umgerechnet entsprechend der Kongruenz modulo 8 – in einer Tabelle darstellen:

n 0 1 2 3 4 ...
10n 1 10 100 1000 10000 ...
10n (mod 8) 1 2 4 0 0 ...

Demnach kommen in der Darstellung von z "modulo 8" nur drei Summanden vor:

z ≡ 4 · d2 + 2 · d1 + d0.

Eine Zahl z ist durch 8 teilbar, wenn die aus den letzten drei Ziffern gebildete Zahl

z3 = d2· 102 + d1 · 101 + d0

durch 8 teilbar ist.

Gleichwertig:

Eine Zahl z ist durch 8 teilbar, wenn 4 · d2 + 2 · d1 + d0 ≡ 0 (mod 4).

Der Rest bei Division einer Zahl durch 8 wird bestimmt durch den Rest von z3 bei Division durch 8.

Beispiel:

Für z = 38 975 472 soll geprüft werden, ob sie durch 4 teilbar ist.

Da 472 = 8 · 59, ist z durch 8 teilbar.

Alternativ:

z ≡ 4 · 4 + 2 · 7 + 2 (mod 8) = 32 (mod 8) ≡ 0 (mod 8).

Aufgabe:

Leiten Sie die Teilbarkeitsregeln für k = 16, k = 32, ... k = 2i, i = 4, 5, ... her.

Teilbarkeit durch 6

Um die Teilbarkeitsregel für eine Zahl wie 6 zu formulieren, gibt es 2 Möglichkeiten:

Wegen der letzten Formulierung, reicht es, Teilbarkeitsregeln nur für Primzahlen zu formulieren, da sie für andere Zahlen z auf die Teilbarkeitsregeln der Teiler von z zurückgeführt werden können.

Teilbarkeit durch 7

Inzwischen sollte klar geworden sein, wie man vorgeht, um die Teilbarkeitsregeln herzuleiten und wie mn sie übersichtlich in den Tabellen mit den Potenzen 10n (mod k) darstellt.

Wird die Teilbarkeitsregel bezüglich des Teilers 7 gesucht, werden wieder die Potenzen von berechnet und modulo 7 dargestellt. Diese Rechnungen werden nicht nochmals vorgeführt, die Ergebnisse sind in folgender Tabelle zu sehen:

n 0 1 2 3 4 5 6 7 ...
Restsystem 10n 1 10 100 1000 104 105 106 107 ...
{0, 1, 2, 3, 4, 5, 6} 10n (mod 7) 1 3 2 6 4 5 1 3 ...
{-3, -2, -2, 0, 1, 2, 3} 10n (mod 7) 1 3 2 -1 -3 -2 1 3 ...

Man erkennt folgendes:

Das folgende Beispiel zeigt, wie man jetzt für eine Zahl die Teilbarkeit durch 7 feststellt (und den Rest bei Division durch 7 berechnet).

Beispiele:

1. Sei z = 98. Dann ist

z ≡ 1 · 8 + 3 · 9 ≡ 35 ≡ 0 (mod 7).

Also ist 98 durch 7 teilbar (14 · 4 = 98).

2. Sei wieder z = 38 975 472. Zuerst werde das Restsystem der Reste verwendet (der erste Faktor ist jeweils der Gewichtungsfaktor, der zweite Faktor die Ziffer):

38 975 472 ≡ 3 · 3 + 1 · 8 + 5 · 9 + 4 · 7 + 6 · 5 + 2 · 4 + 3 · 7 + 1 · 2 ≡ 151 ≡ 4 (mod 7)

Zur Kontrolle:

5 569 724 · 7 + 4 = 38 975 472.

Der Rechenaufwand ist bei Verwendung des vollständigen Restsystems der Reste sehr hoch, einfacher wird es mit dem vollständigen Restsystem {-3, -2, -2, 0, 1, 2, 3}:

38 975 472 ≡ 3 · 3 + 1 · 8 + (-2) · 9 + (-3) · 7 + (-1) · 5 + 2 · 4 + 3 · 7 + 1 · 2 ≡ 4 (mod 7)

Eine vielleicht einfachere Darstellung als obige Summen liefert die folgende Tabelle (wieder mit beiden vollständigen Restsystemen):

Restsystem z 3 8 9 7 5 4 7 2
{0, 1, 2, 3, 4, 5, 6} 10n (mod 7) 3 1 5 4 6 2 3 1
{-3, -2, -2, 0, 1, 2, 3} 10n (mod 7) 3 1 -2 -3 -1 2 3 1

Teilbarkeit durch 11

Die Teilbarkeitsregel für den Teiler 7 war sehr kompliziert; man erwartet vielleicht, dass bei größeren Teilern die Regeln immer umfangreicher werden. Die Teilbarkeitsregel für k = 11 bestätigt dies aber nicht.

Man berechnet wieder die Potenzen von 10 "modulo 11":

Die Zahl 10 ist noch eine Ziffer im 11er-System, also ist 10 ≡ 10 (mod 11).

100 = 11 · 9 + 1, daher ist:

100 ≡ 1 (mod 11).

Aber dann sind alle weiteren Potenzen von 10 abwechselnd kongruent zu 10 beziehungsweise 1. Verwendet man das vollständige Restsystem {-5, -4, ..., 4, 5}, wird die Teilbarkeitsregel deutlich einfacher, denn die relevanten Zahlen lauten 1 und -1. Das heißt man muss von einer Zahl z die alternierende Quersumme berechnen.

n 0 1 2 3 4 ...
Restsystem 10n 1 10 100 1000 104 ...
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10} 10n (mod 7) 1 10 1 10 1 ...
{-5, -4, -3, -2, -2, 0, 1, 2, 3, 4, 5} 10n (mod 7) 1 -1 1 -1 1 ...

1. Beispiel:

Für z = 321 gilt:

z ≡ 3 · 1 + 2 · (-1) + 1 · 1 = 3 - 2 + 1 = 2.

Also ist 321 ≡ 2 (mod 11).

Zur Kontrolle: 29 · 11 + 2 = 321.

2. Beispiel

Für z = 38 975 472 erhält man für die alternierende Quersumme:

-3 + 8 - 9 + 7 - 5 + 4 - 7 + 2 = -3.

Also gilt: z ≡ 8.

Zur Kontrolle:

38 975 472 = 3 543 224 · 11 + 8.

Restsystem z 3 8 9 7 5 4 7 2
{0, 1, 2, 3, 4, 5, 6} 10n (mod 7) 3 1 5 4 6 2 3 1
{-3, -2, -2, 0, 1, 2, 3} 10n (mod 7) 3 1 -2 -3 -1 2 3 1

Weitere Teilbarkeitsregeln sollen jetzt nicht hergeleitet werden, unten ist ein einfaches R-Skript angegeben, mit dem beliebige Teilbarkeitsregeln berechnet werden können.

Überprüfen von Multiplikationen

1. Beispiel:

Eine Multiplikation soll überprüft werden:

Gilt 237 · 683 = 161 881?

Richtig wäre 161 871. Auf den ersten Blick scheint das Ergebnis plausibel, da 7 · 3 = 21 und das obige Ergebnis mit der Ziffer 1 endet. Auch die Größenordnung erscheint glaubwürdig, da 200 · 700 = 14 000.

Betrachtet man aber die Gleichung modulo 9, sieht man sofort einen Fehler.

2 + 3 + 7 = 12, also liegt 237 in der Restklasse 3 (mod 9).

6 + 8 + 3 = 17, also liegt 683 in der Restklasse 8 (mod 9).

3 · 8 = 24 liegt in der Restklasse 6 modulo 9

Die rechte Seite liefert als Quersummen:

1 + 6 + 1+ 8 + 8 + 1 = 25; diese Zahl liegt aber in der Restklasse 7 modulo 9. Nach dem Satz über die Invarianz der Multiplikation gegenüber den Restklassen bedeutet dies, dass die Berechnung oben nicht richtig sein kann.

Aufgabe:

Überprüfen Sie obige Gleichung in den Restklassen modulo 3.

Bemerkung:

Der Rechengang zum Überprüfen einer Multiplikation mit den Restklassen modulo 3 beziehungsweise modulo 9 ist ähnlich aufwendig. Der Vorteil der Restklassen modulo 9 ist, dass die Wahrscheinlichkeit dafür geringer ist, dass die linke und rechte Seite "zufällig" übereinstimmen.

2. Beispiel:

Möchte man eine Multiplikation überprüfen, bei der man eher den Verdacht hat, dass nicht beim Berechnen sondern beim Übertragen des Ergebnisses ein Fehler entstanden ist, sollte man keine Teilbarkeitsregel anwenden, die auf der Quersumme beruht (Teilbarkeit durch 3 oder 9). Denn eine "Zahlendreher", also die Vertauschung zweier Ziffern, kann man mit der Quersumme nicht aufdecken. Hier ist die Teilbarkeitsregel für k = 11 besser geeignet

Gilt 237 · 683 = 161 781?

(Das Ergebnis ist aus dem richtigen Ergebnis 161 871 durch einen "Zahlendreher" entstanden.)

237 ≡ 2 - 3 + 7 ≡ 6 (mod 11) und

683 ≡ 6 - 8 + 3 ≡ 1 (mod 11).

Somit ist

237 · 683 ≡ 6 (mod 11).

Aber

161 781 ≡ -1 + 6 -1 + 7 - 8 + 1 ≡ 4 (mod 11).

Damit kennt man zwar nicht das richtige Ergebnis der Multiplikation, weiß aber, dass das angegebene Ergebnis falsch ist.

Ausblick: Ähnliche Methoden werden etwa bei der Verwendung von Prüfziffern eingesetzt. Mit iher Hilfe können zum Beispiel Übertragungsfehler mit hoher Wahrscheinlichkeit festgestellt werden.

R-Skripte

Vollständiges Restsystem

Test auf ein vollständiges Restsystem

Bei den folgenden Skripten wird öfters ein vollständiges Restsystem eingesetzt. Es ist daher hilfreich vor seinem Einsatz zu überprüfen, ob es einige Minimalanforderungen erfüllt, die man daran stellt.

Dies geschieht mit Hilfe der Funktion isResidualSystem(), die zwei Eingabewerte besitzt:

isResidualSystem <- function(modulus = 1, residualSystem = (0:(modulus - 1))){
  stopifnot(modulus > 0)
  stopifnot(length(modulus) == 1)
  stopifnot(length(residualSystem) == modulus)
  
  return( setequal(x = (0:(modulus - 1)), y = residualSystem %% modulus) )
}

# Test
isResidualSystem(modulus = 5, residualSystem = (-2:2))
# TRUE
isResidualSystem(modulus = 5, residualSystem = (-5:-1))
# TRUE
isResidualSystem(modulus = 5, residualSystem = rep(x = 1, times = 5))
# FALSE

Zur Erklärung:

Zeile 1: Als default-Werte werden der Teiler gleich 1 und residualSystem gleich den Resten zum Teiler modulus gesetzt.

Zeile 2 bis 4: Man könnte hier noch weitere Prüfungen anbringen, etwa ob modulus und die Elemente von residualSystem ganzzahlig sind; hier wird nur geprüft,

Zeile 6: Es wird geprüft, ob die beiden Mengen x und y übereinstimmen; eine Prüfung auf Mengengleichheit ist nötig, da die Elemente in residualSystem beliebige Reihenfolge haben können. Um y zu bilden, wird von jedem Element von residualSystem der Rest bei Division durch modulus berechnet. Dies wird mit x verglichen, dem vollständigen Restsystem zum Teiler modulus aus den Resten. Der Wert des Vergleichs ist der Rückgabewert der Funktion isResidualSystem().

Zeile 9 bis 15: Einige Tests für die Anwendung der Funktion isResidualSystem().

Berechnung eines kongruenten Elementes

Meistens arbeitet man mit dem vollständigen Restsystem der Reste; dann kann man sich zu einer gegebenen Zahl z den Rest zu einem Teiler modulus mit z %% modulus berechnen. Verwendet man aber ein anderes vollständiges Restsystem, ist es mühsam, zu einer gegebenen Zahl z das zugehörige kongruente Element zu bestimmen. Dies übernimmt die Funktion getCongruentElement():

getCongruentElement <- function(z = 1, modulus = 1, residualSystem = (0:(modulus - 1))){
  stopifnot(isResidualSystem(modulus = modulus, residualSystem = residualSystem))
  
  r <- z %% modulus
  
  idx <- which(rs %% modulus == r)
  
  return(rs[idx])
}

getCongruentElement(z = 556, modulus = 10, residualSystem = (-4:5))
# -4

Eingabewerte sind die Zahl z, der Teiler modulus und das vollständige Restsystem residualSystem.

Zeile 2: Es wird geprüft, ob tatsächlich ein vollständiges Restsystem vorliegt.

Zeile 4: Der Rest von z bei Division durch modulus wird bestimmt.

Zeile 6: Der Index wird bestimmt, wo im Vektor residualSystem das zu z kongruente Element steht.

Zeile 8: Rückgabewert ist das kongruente Element aus residualSystem.

Zeile 11: Test der Funktion getCongruentElement().

Man beachte, dass die Funktion getCongruentElement() tatsächlich nur auf eine Zahl z angewendet werden darf: Die Berechnung des Restes in Zeile 4 könnte zwar mit einem Vektor z ausgeführt werden (es wird dann der entsprechende Vektor von Resten gebildet), der logische Vergleich in Zeile 6 setzt aber voraus, dass der Rest r eine Zahl ist.

Damit man in einem Schritt einen Vektor z von Eingabewerten verarbeiten kann, wird eine weitere Funktion multCongruentElements() implementiert:

multCongruentElements <- function(z = 1, modulus, rs = (0:(modulus - 1))){
  stopifnot(isResidualSystem(modulus = modulus, residualSystem = rs))
  
  lgth <- length(z)
  result <- vector(mode = "integer", length = lgth)
  
  for(i in (1:lgth)){
    idx <- which( (rs %% modulus) == (z[i] %% modulus))
    result[i] <- rs[idx]
  }
  return(result)
}

multCongruentElement(z = (1:6), modulus = 4)
# [1] 1 2 3 0 1 2
multCongruentElement(z = (1:6), modulus = 4, rs = (-1:2))
# [1]  1  2 -1  0  1  2

Zeile 1: Der Name soll andeuten, dass mehrere kongruente Elemente gebildet werden (mult = multiple).

Zeile 5: Es wird ein Vektor mit der Länge des Eingabewertes z vorbereitet.

Zeile 7 bis 10: In der for-Schleife wird der vorbereitete Vektor mit Werten belegt. Dazu sind die beiden Anweisungen aus Zeile 4 und 6 der Funktion getCongruentElement() zu einer Anweisung zusammengefasst.

Zeile 13 bis 16: Zwei Tests der Funktion multCongruentElements(), einmal mit dem vollständigen Restsystem, das per default gesetzt wird und einmal mit einem anderen Restsystem.

Additions- und Multiplikationstabellen

In den Abbildung 2, 3 und 4 wurden Additions- und Multiplikationstabellen gezeigt. Mit Hilfe der Funktion multCongruentElements() kann man sie leicht erzeugen: Man erzeugt zunächst eine Additions- beziehungsweise Multiplikationstabelle als Matrix. Anschließend werden deren Elemente in das gewünschte vollständige Restsystem residualSystem übersetzt.

Tabellen mit dem vollständigen Restsystem der Reste

Das folgende Skript zeigt zunächst, wie man eine Additionstabelle zum Teiler 4 mit dem vollständigen Restsystem der Reste erzeugt; dazu wird einfach die Operation %% 4 (Rest bei Division durch 4) nach der Berechnung der Summe eingesetzt:

mod <- 4

v <- (0:(mod - 1))

m.add.4 <- outer(X = v, Y = v, FUN = function(X, Y, modulus = mod){return((X + Y) %% modulus)})
m.add.4
#      [,1] [,2] [,3] [,4]
# [1,]    0    1    2    3
# [2,]    1    2    3    0
# [3,]    2    3    0    1
# [4,]    3    0    1    2

Zeile 1: Der Teiler wird gleich 4 gesetzt. Möchte man später eine Tabelle zu einem anderen Teiler erzeugen, muss man nur mod abändern.

Zeile 3: Die Tabelle wird später mit dem kartesichen Produkt erzeugt; dazu benötigt man den Vektor der Eingabewerte für die Summe.

Zeile 5: An die Funktion outer() wird zweimal der Vektor v übergeben. Die anonyme Funktion, die an das Argument FUN übergeben wird, berechnet die Summe der Eingabewerte "modulo 4".

Zeile 6 bis 11: Die Ausgabe zeigt die Matrix, die in Abbildung 2 als Additionstabelle dargestellt wurde.

Um eine Multiplikationstabelle zu erzeugen, muss nur im Argument FUN von outer() das Produkt anstelle der Addition eingesetzt werden.

Alternative:

Anstelle der anonymen Funktion für das Argument FUN kann man auch die entstehende Matrix direkt bearbeiten. Das folgende Skript ist gleichwertig zum obigen Skript:

mod <- 4

v <- (0:(mod - 1))

m.add.4 <- outer(X = v, Y = v, FUN = "+")

m.add.4 <- m.add.4 %% 4
m.add.4
#      [,1] [,2] [,3] [,4]
# [1,]    0    1    2    3
# [2,]    1    2    3    0
# [3,]    2    3    0    1
# [4,]    3    0    1    2

Die Aufgabe der anonymen Funktion wird jetzt in zwei Anweisungen zerlegt (Zeile 5 und 7); der Vorteil liegt darin, dass man jetzt auf das Zwischenergebnis (Zeile 5) ausdrücklich zugreifen kann.

Beliebiges Restsystem

Möchte man mit einem anderen vollständigen Restsystem als dem der Reste (wie in den beiden letzten Skripten) arbeiten – wie etwa in Abbildung 4 – kann man folgendermaßen vorgehen:

Das folgende Skript zeigt die Anweisungen:

# m.add.4: Matrix, wie sie in den letzten Skripten erzeugt wurde

z.4 <- multCongruentElement(z = m.add.4, modulus = 4, rs = (-1:2))
z.4 <- matrix(data = z.4, nrow = 4)
z.4
#     [,1] [,2] [,3] [,4]
# [1,]    0    1    2   -1
# [2,]    1    2   -1    0
# [3,]    2   -1    0    1
# [4,]   -1    0    1    2

Zeile 3: Es wird das vollständige Restsystem {-1, 0, 1, 2} verwendet; die Funktion multCongruentElements() wird auf jedes Element der Matrix m.add.4 angewendet. Dabei wird allerdings ein Vektor erzeugt, da multCongruentElements() so implementiert ist, dass ein Vektor zurückgegeben wird.

Zeile 4 und 5: Der Vektor wird in eine 4 × 4 Matrix verwandelt und ausgegeben.

Multiplikationstabellen im Hexadezimalsystem

In Ganzzahl-Division: Kongruenzen und Restklassen als Beispiele für Äquivalenzrelationen und Äquivalenzklassen wurden in Abbildung 2 und 3 die Additions- und Multiplikationstabelle für die Zahlen 1, 2, ..., 9, A, ..., F, (10)16 im Hexadezimalsystem gezeigt. Dort wurde das Ergebnis als Hexadezimalzahl angegeben, also zum Beispiel

(10)16 · (10)16 = (100)16

oder

F · F = (E1)16.

Es ist jetzt naheliegend, die Multiplikationstabelle (und auch die Additionstabelle) mit

Es sollte aber auch klar sein, dass innerhalb Z16 die Buchstaben A, ..., F nicht für die Ziffern 10, ..., 15 eingesetzt werden müssen: Es gibt in Z16 keine zweistelligen Zahlen und daher kann eine Zahl wie 15 ∈ Z16 nur als Ziffer interpretiert werden. In den Skripten unten werden dennoch beide Varianten (mit Zahlen beziehungsweise mit Buchstaben gezeigt).

Nach den bisherigen Vorbereitungen ist es nicht mehr schwer, zum Beispiel die Multiplikationstabelle in Z16 zu erzeugen:

Zuerst wird die Multiplikationstabelle mit dem vollständigen Restsystem der Reste gebildet, wobei die Ziffern noch nicht als Hexadezimalzahlen dargestellt werden (dieses vollständige Restsystem muss in der Funktion multCongruentElements() nicht gesetzt werden, da es der default-Wert für rs ist). Verwirrend ist hier lediglich, dass die Zeilen- und Spaltennummern bei 1 (und nicht bei 0) beginnen.

v <- (0:15)
m.mult.16 <- outer(X = v, Y = v, FUN = "*")

m.mult.16 <- matrix(data = multCongruentElement(z = m.mult.16, modulus = 16), nrow = 16)
m.mult.16
#       [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14] [,15] [,16]
# [1,]    0    0    0    0    0    0    0    0    0     0     0     0     0     0     0     0
# [2,]    0    1    2    3    4    5    6    7    8     9    10    11    12    13    14    15
# [3,]    0    2    4    6    8   10   12   14    0     2     4     6     8    10    12    14
# [4,]    0    3    6    9   12   15    2    5    8    11    14     1     4     7    10    13
# [5,]    0    4    8   12    0    4    8   12    0     4     8    12     0     4     8    12
# [6,]    0    5   10   15    4    9   14    3    8    13     2     7    12     1     6    11
# [7,]    0    6   12    2    8   14    4   10    0     6    12     2     8    14     4    10
# [8,]    0    7   14    5   12    3   10    1    8    15     6    13     4    11     2     9
# [9,]    0    8    0    8    0    8    0    8    0     8     0     8     0     8     0     8
# [10,]    0    9    2   11    4   13    6   15    8     1    10     3    12     5    14     7
# [11,]    0   10    4   14    8    2   12    6    0    10     4    14     8     2    12     6
# [12,]    0   11    6    1   12    7    2   13    8     3    14     9     4    15    10     5
# [13,]    0   12    8    4    0   12    8    4    0    12     8     4     0    12     8     4
# [14,]    0   13   10    7    4    1   14   11    8     5     2    15    12     9     6     3
# [15,]    0   14   12   10    8    6    4    2    0    14    12    10     8     6     4     2
# [16,]    0   15   14   13   12   11   10    9    8     7     6     5     4     3     2     1

Zeile 1: Man beachte, dass die Eingabewerte zur Berechnung der Produkte innerhalb Z16 von 0 bis 15 laufen (in den ursprünglichen Multiplikationstabellen zum Hexadezimalsystem waren die Eingabewerte die Zahlen von 1 bis 16).

Zeile 2: Es wird die herkömmliche Multiplikationstabelle als Matrix für Eingabewerte von 1 bis 16 berechnet.

Zeile 4: Mit der Funktion multCongruentElements() werden die Elemente der Matrix im vollständigen Restsystem {0, ..., 15} dargestellt. Da multCongruentElements() einen Vektor zurückgibt, wird wieder eine Matrix mit 16 Zeilen (und Spalten) gebildet.

Ab Zeile 5: Ausgabe der Matrix, also der Multiplikationstabelle "modulo 16", wobei noch keine Hexadezimalziffern verwendet werden.

Im folgenden Skript wird die Matrix aus der Ausgabe von Zeile 5 mit Hexadezimalziffern dargestellt:

m.mult.16 <- as.hexmode(x = m.mult.16)
print(x = format(x = m.mult.16, upper.case = TRUE), quote = FALSE)
#      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14] [,15] [,16]
# [1,] 0    0    0    0    0    0    0    0    0    0     0     0     0     0     0     0    
# [2,] 0    1    2    3    4    5    6    7    8    9     A     B     C     D     E     F    
# [3,] 0    2    4    6    8    A    C    E    0    2     4     6     8     A     C     E    
# [4,] 0    3    6    9    C    F    2    5    8    B     E     1     4     7     A     D    
# [5,] 0    4    8    C    0    4    8    C    0    4     8     C     0     4     8     C    
# [6,] 0    5    A    F    4    9    E    3    8    D     2     7     C     1     6     B    
# [7,] 0    6    C    2    8    E    4    A    0    6     C     2     8     E     4     A    
# [8,] 0    7    E    5    C    3    A    1    8    F     6     D     4     B     2     9    
# [9,] 0    8    0    8    0    8    0    8    0    8     0     8     0     8     0     8    
# [10,] 0    9    2    B    4    D    6    F    8    1     A     3     C     5     E     7    
# [11,] 0    A    4    E    8    2    C    6    0    A     4     E     8     2     C     6    
# [12,] 0    B    6    1    C    7    2    D    8    3     E     9     4     F     A     5    
# [13,] 0    C    8    4    0    C    8    4    0    C     8     4     0     C     8     4    
# [14,] 0    D    A    7    4    1    E    B    8    5     2     F     C     9     6     3    
# [15,] 0    E    C    A    8    6    4    2    0    E     C     A     8     6     4     2    
# [16,] 0    F    E    D    C    B    A    9    8    7     6     5     4     3     2     1

Zeile 1: Die Elemente der Matrix werden ins Hexadezimalsystem umgerechnet; dabei werden sie allerdings in Zeichen verwandelt.

Zeile 2: Zur Ausgabe werden die Anführungsstriche unterdrückt und die Ziffern mit Großbuchstaben dargestellt.

Die letzte Multiplikationstabelle wird nun mit dem vollständigen Restsystem {-7, ..., 8} erzeugt:

v <- (0:15)
m.mult.16 <- outer(X = v, Y = v, FUN = "*")

m.mult.16 <- matrix(data = multCongruentElement(z = m.mult.16, modulus = 16, rs = (-7:8)), nrow = 16)
m.mult.16
#      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14] [,15] [,16]
# [1,]    0    0    0    0    0    0    0    0    0     0     0     0     0     0     0     0
# [2,]    0    1    2    3    4    5    6    7    8    -7    -6    -5    -4    -3    -2    -1
# [3,]    0    2    4    6    8   -6   -4   -2    0     2     4     6     8    -6    -4    -2
# [4,]    0    3    6   -7   -4   -1    2    5    8    -5    -2     1     4     7    -6    -3
# [5,]    0    4    8   -4    0    4    8   -4    0     4     8    -4     0     4     8    -4
# [6,]    0    5   -6   -1    4   -7   -2    3    8    -3     2     7    -4     1     6    -5
# [7,]    0    6   -4    2    8   -2    4   -6    0     6    -4     2     8    -2     4    -6
# [8,]    0    7   -2    5   -4    3   -6    1    8    -1     6    -3     4    -5     2    -7
# [9,]    0    8    0    8    0    8    0    8    0     8     0     8     0     8     0     8
# [10,]    0   -7    2   -5    4   -3    6   -1    8     1    -6     3    -4     5    -2     7
# [11,]    0   -6    4   -2    8    2   -4    6    0    -6     4    -2     8     2    -4     6
# [12,]    0   -5    6    1   -4    7    2   -3    8     3    -2    -7     4    -1    -6     5
# [13,]    0   -4    8    4    0   -4    8    4    0    -4     8     4     0    -4     8     4
# [14,]    0   -3   -6    7    4    1   -2   -5    8     5     2    -1    -4    -7     6     3
# [15,]    0   -2   -4   -6    8    6    4    2    0    -2    -4    -6     8     6     4     2
# [16,]    0   -1   -2   -3   -4   -5   -6   -7    8     7     6     5     4     3     2     1

Zeile 1 und 2: sind bereits bekannt.

Zeile 4: Hier ist lediglich neu, dass das vollständige Restsystem {-7, ..., 8} gesetzt wird. Eine Umrechnung ins Hexadezimalsystem ist hier nicht nötig.

Berechnung der Teilbarkeitsregeln

Im Theorieteil wurde gezeigt, wie man vorgehen muss, um zu einem beliebigen Teiler k die Teilbarkeitsregel herzuleiten:

Um den letzten Punkt zu realisieren, wird eine Funktion implementiert, die zu einem Teiler k das vollständige Restsystem mit den Zahlen mit den kleinsten Beträgen zurückgibt.

residualSystem <- function(modulus = 2){
  q <- modulus %/% 2
  r <- modulus %% 2
  return( (1:modulus) - q - r )
}

residualSystem(modulus = 16)
# [1] -7 -6 -5 -4 -3 -2 -1  0  1  2  3  4  5  6  7  8

Damit ist es nicht mehr schwer, eine Teilbarkeitsregel zu einem gegebenen Teiler als Folge anzugeben und in das geeignete vollständige Restsystem umzuwandeln:

getDivisibilityRule <- function(modulus, rs = (0:(modulus - 1))){
  sequ <- 1
  n <- 10
  
  while(length(sequ) == length(unique(sequ))){
    digit <- getCongruentElement(z = n, modulus = modulus, residualSystem =  rs)
    sequ <- append(x = sequ, values = digit)
    n <- getCongruentElement(z = (10 * n), modulus = modulus, residualSystem = rs)
  }
  return(sequ) 
}

div.rule <- getDivisibilityRule(modulus = 11)
div.rule
# [1] 1 10 1 
multCongruentElement(z = div.rule, modulus = 11, rs = residualSystem(modulus = 11))
# [1]  1 -1  1

Zeile 1: Um die Teilbarkeitsregel zu berechnen, benötigt man als Eingabewerte den Teiler modulus und das vollständige Restsystem; per default werden die Reste verwendet.

Zeile 2: Jede Folge muss mit 1 beginnen. An sequ werden dann weitere Folgenglieder angehängt und die Folge wird zurückgegeben, sobald sich ein Folgenglied wiederholt.

Zeile 3: Es müssen die Potenzen von 10 berechnet werden; die Variable n wird in der Schleife immer mit einem weiteren Faktor 10 multipliziert.

Zeile 5 bis 9: Schleife zum Erzeugen der Folge. Die Schleife bricht ab, wenn ein Folgenglied doppelt vorkommt.

Zeile 6 und 7: Es wird festgestellt, zu welcher Zahl aus dem vollständigen Restsystem rs die Zahl n kongruent ist. Diese Zahl wird an die Folge angehängt.

Zeile 8: Die Potenz wird um 1 erhöht, also wird n mit 10 multipliziert. Zu dieser Zahl wird sofort die kongruente Zahl gesucht (man würde sonst schnell den Zahlenbereich von integer überschreiten).

Zeile 10: Rückgabewert ist die gesamte Folge.

Ab Zeile 13: Test mit dem Teiler modulus = 11 in den beiden bevorzugten vollständigen Restsystemen.

Ausgabe mehrerer Teilbarkeitsregeln:

Die Ausgabe aus dem letzten Skript wird in eine Schleife verpackt und ansehnlicher aufbereitet:

for(i in (3:37)){
  cat("modulus: ", i, "\n")
  rule <- getDivisibilityRule(modulus = i)
  print(rule)
  print(multCongruentElement(z = rule, modulus = i, rs = residualSystem(modulus = i)))
  cat("\n")
}

# modulus:  3 
# [1] 1 1
# [1] 1 1
# 
# modulus:  4 
# [1] 1 2 0 0
# [1] 1 2 0 0
# 
# modulus:  5 
# [1] 1 0 0
# [1] 1 0 0
# 
# modulus:  6 
# [1] 1 4 4
# [1]  1 -2 -2
# 
# modulus:  7 
# [1] 1 3 2 6 4 5 1
# [1]  1  3  2 -1 -3 -2  1
# 
# modulus:  8 
# [1] 1 2 4 0 0
# [1] 1 2 4 0 0
# 
# modulus:  9 
# [1] 1 1
# [1] 1 1
# 
# modulus:  10 
# [1] 1 0 0
# [1] 1 0 0
# 
# modulus:  11 
# [1]  1 10  1
# [1]  1 -1  1
# 
# modulus:  12 
# [1]  1 10  4  4
# [1]  1 -2  4  4
# 
# modulus:  13 
# [1]  1 10  9 12  3  4  1
# [1]  1 -3 -4 -1  3  4  1
# 
# modulus:  14 
# [1]  1 10  2  6  4 12  8 10
# [1]  1 -4  2  6  4 -2 -6 -4
# 
# modulus:  15 
# [1]  1 10 10
# [1]  1 -5 -5
# 
# modulus:  16 
# [1]  1 10  4  8  0  0
# [1]  1 -6  4  8  0  0
# 
# modulus:  17 
# [1]  1 10 15 14  4  6  9  5 16  7  2  3 13 11  8 12  1
# [1]  1 -7 -2 -3  4  6 -8  5 -1  7  2  3 -4 -6  8 -5  1
# 
# modulus:  18 
# [1]  1 10 10
# [1]  1 -8 -8
# 
# modulus:  19 
# [1]  1 10  5 12  6  3 11 15 17 18  9 14  7 13 16  8  4  2  1
# [1]  1 -9  5 -7  6  3 -8 -4 -2 -1  9 -5  7 -6 -3  8  4  2  1
# 
# modulus:  20 
# [1]  1 10  0  0
# [1]  1 10  0  0
# 
# modulus:  21 
# [1]  1 10 16 13  4 19  1
# [1]  1 10 -5 -8  4 -2  1
# 
# modulus:  22 
# [1]  1 10 12 10
# [1]   1  10 -10  10
# 
# modulus:  23 
# [1]  1 10  8 11 18 19  6 14  2 20 16 22 13 15 12  5  4 17  9 21  3  7  1
# [1]   1  10   8  11  -5  -4   6  -9   2  -3  -7  -1 -10  -8 -11   5   4  -6   9  -2   3   7   1
# 
# modulus:  24 
# [1]  1 10  4 16 16
# [1]  1 10  4 -8 -8
# 
# modulus:  25 
# [1]  1 10  0  0
# [1]  1 10  0  0
# 
# modulus:  26 
# [1]  1 10 22 12 16  4 14 10
# [1]   1  10  -4  12 -10   4 -12  10
# 
# modulus:  27 
# [1]  1 10 19  1
# [1]  1 10 -8  1
# 
# modulus:  28 
# [1]  1 10 16 20  4 12  8 24 16
# [1]   1  10 -12  -8   4  12   8  -4 -12
# 
# modulus:  29 
# [1]  1 10 13 14 24  8 22 17 25 18  6  2 20 26 28 19 16 15  5 21  7 12  4 11 23 27  9  3  1
# [1]   1  10  13  14  -5   8  -7 -12  -4 -11   6   2  -9  -3  -1 -10 -13 -14   5  -8   7  12   4  11  -6  -2   9   3
# [29]   1
# 
# modulus:  30 
# [1]  1 10 10
# [1]  1 10 10
# 
# modulus:  31 
# [1]  1 10  7  8 18 25  2 20 14 16  5 19  4  9 28  1
# [1]   1  10   7   8 -13  -6   2 -11  14 -15   5 -12   4   9  -3   1
# 
# modulus:  32 
# [1]  1 10  4  8 16  0  0
# [1]  1 10  4  8 16  0  0
# 
# modulus:  33 
# [1]  1 10  1
# [1]  1 10  1
# 
# modulus:  34 
# [1]  1 10 32 14  4  6 26 22 16 24  2 20 30 28  8 12 18 10
# [1]   1  10  -2  14   4   6  -8 -12  16 -10   2 -14  -4  -6   8  12 -16  10
# 
# modulus:  35 
# [1]  1 10 30 20 25  5 15 10
# [1]   1  10  -5 -15 -10   5  15  10
# 
# modulus:  36 
# [1]  1 10 28 28
# [1]  1 10 -8 -8
# 
# modulus:  37 
# [1]  1 10 26  1
# [1]   1  10 -11   1

Anwendung der Teilbarkeitsregeln auf große Zahlen

Was heißt hier große Zahlen?

Mit der zuletzt angegebenen Funktion getDivisibilityRule() kann man sich zu beliebigem Teiler modulus die Folge berechnen lassen, mit der man für eine gegebene Zahl z überprüfen kann, ob sie durch modulus teilbar ist beziehungsweise welcher Rest bei einer Ganzzahl-Division bleibt. Den letzten Schritt möchte man natürlich auch von einem Skript erledigen lassen.

Allerdings stellt sich dann sofort die Frage: Wozu eigentlich? Sowohl die Ganzzahl-Division als auch die Berechnung des Restes kann man in einem Skript ausführen – dazu gibt es die Operatoren %/% und %% .

Interessant wird die Berechnung erst, wenn die Zahl z so groß ist, dass sie den erlaubten Zahlenbereich für den Speichermodus integer überschreitet. Man benötigt dann eine andere Kodierung für ganze Zahlen.

In den folgenden Abschnitten wird eine Lösung gezeigt, wie man die Stellen einer Zahl als Komponenten eines Vektors abspeichert und mit dieser Vektor-Repräsentation der Zahl rechnet. Man kann dies als Spezialfall eines umfangreicheren Problems betrachten: Nahezu alle Programmiersprachen bieten heute neben den elementaren Datentypen spezielle Datentypen für ganze Zahlen an, die weit über den eigentlichen Zahlenbereich der ganzen Zahlen hinausgehen. Bei Anwendung dieser Datentypen muss man sich aber im Klaren sein:

Für spezielle Probleme kann man sich derartige Datentypen leicht selbst definieren; sie so zu implementieren, dass sie für beliebige Aufgaben eingesetzt werden können, ist sehr aufwendig.

Kodierung einer ganzen Zahl als Vektor

In Stellenwertsysteme und Umrechnung zwischen den wichtigsten Zahlensystemen: Dezimalsystem, Hexadezimalsystem, Dualsystem wurde schon mit der zuletzt angedeuteten Kodierung von ganzen Zahlen durch Vektoren gearbeitet – die wichtigsten Eigenschaften dieser Kodierung sollen kurz beschrieben werden:

Das folgende Skript zeigt die wichtigste Funktionen zum Umgang mit den als Vektoren kodierten Zahlen, nämlich die Ausgabe einer Zahl. Dabei ist:

printNumber <- function(z, base = 10, N = length(z)){
  stopifnot(length(z) <= N)
  stopifnot(base < 11 && base > 1)
  stopifnot(N > 0)
  
  number <- paste0(rev(z), collapse = "")
  nulls <- N - length(z)    # Anzahl der führenden Nullen

  cat(paste("(", paste0(rep(x = 0, times = nulls), collapse = ""), number, ")_", base, sep = ""), "\n")
}

# Test

printNumber(z = c(8, 2, 1), N = 4)
# (0128)_10 

printNumber(z = rep(x = c(8, 2, 1), times = 5), N = 16)
# (0128128128128128)_10

Der letzte Test zeigt, dass man jetzt auch mit Zahlen rechnen kann, die in R nicht mehr im Speichermodus integer bewältigt werden. Allerdings muss man jetzt Rechenoperationen selber implementieren und an die Kodierung anpassen.

Die folgende Diskussion wird aber zeigen, dass für die hier gestellten Aufgaben allein das Skalarprodukt ausreichen wird.

Im Theorieteil wurde gezeigt, wie die Teilbarkeitsregeln auf Zahlen angewendet werden: Die meisten Teilbarkeitsregeln führen auf Endstellenregeln oder Quersummenregeln, bei denen eine Folge gegeben ist, die mit den Ziffern der zu untersuchenden Zahl multipliziert werden. Betrachtet man diese Operation genauer, so handelt es sich um ein Skalarprodukt. Der Unterschied zwischen den Endstellenregeln und den Quersummenregeln besteht lediglich darin, dass Erstere abbrechen (etwa Teilbarkeit durch 8 mit der Folge (1, 2, 4)) und Letztere im Prinzip unendlich oft wiederholt werden können (etwa Teilbarkeit durch 7 mit der Folge (1, 3, 2,-1,-3,-2)). Bei einigen Zahlen entsteht eine Kombination aus beiden Regeln, etwa bei der Teilbarkeit durch 14 mit der Folge (1, -4, 2, 6, 4, -2, -6, -4, ...). Hier wird die Endziffer mit 1 multipliziert (wie bei einer Endstellenregel) und dann wiederholt sich die Folge (-4, 2, 6, 4, -2, -6) periodisch (wie bei einer Quersummenregel).

Das folgende Skript zeigt das Skalarprodukt zweier Vektoren x und y, das mit folgenden Eigenschaften implementiert wird:

cutCombine <- function(x, y, FUN){
  l.x <- length(x)
  l.y <- length(y)
  
  if(l.x < l.y){
    y <- head(x = y, n = l.x)
  } else {
    x <- head(x = x, n = l.y)
  }
  cat("x: ", x, "\n")
  cat("y: ", y, "\n")
  return(FUN(x, y))
}

scalarProd <- function(x, y) {
  return(cutCombine(x = x, y = y, FUN = function(x,y){sum(x*y)} ))
}

Die Hilfsfunktion cutCombine() sorgt lediglich für das Abschneiden des längeren Vektors, ist aber so implementiert, dass man damit auch andere Funktionen als das Skalarprodukt berechnen könnte.

Anwendung einer Teilbarkeitsregel auf eine als Vektor kodierte Zahl

Es soll jetzt die Anwendung einer als Folge gegebenen Teilbarkeitsregel auf eine Zahl implementiert werden, wobei die Zahl nach obiger Konvention als Vektor kodiert ist.

Dazu sind drei Fälle zu unterscheiden, die oben an den Teilbarkeitsregeln für 8, 7 und 14 nochmal erklärt wurden. Eine Folge, die für eine Teilbarkeitsregel steht, kann:

Es wird daher eine Funktion sumOfDigits() angeboten, die drei Eingabewerte besitzt:

sumOfDigits <- function(z, offset, perSequ){
  sumOfDigits <- 0
  
  if( is.null(offset) && is.null(perSequ) ) {    # beide == NULL
    return(  NA_integer_ )
  }
  if( is.null(offset) ){                     # nur offset == NULL
    return( sumOfDigits.perSequ(z = z, perSequ = perSequ) )
  }
  if( is.null(perSequ) ){   # nur perSequ == NULL
      return(  sumOfDigits.offset(z = z, offset = offset) )
  }

  # jetzt sind beide != NULL
  # z = (z1, z2)
  lgth.z <- length(z); lgth.offset <- length(offset); lgth.perSequ <- length(perSequ);
  
  if(lgth.z < (lgth.offset + lgth.perSequ) ) {
    z <- append(x = z, values = rep(x = 0, times = (lgth.offset + lgth.perSequ) - lgth.z))
  }
  
  z1 <- head(x = z, n = lgth.offset)
  z2 <- tail(x = z, n = lgth.z - lgth.offset)
  # cat("z1, z2: ", z1, "::", z2, "\n")
  
  sumOfDigits <- sumOfDigits.offset(z = z1, offset = offset) + sumOfDigits.perSequ(z = z2, perSequ = perSequ)
  return(sumOfDigits)
}

Man erkennt, dass die Anwendung der Teilbarkeitsregel auf zwei einfachere Fälle zurückgeführt werden kann:

Das folgende Skript zeigt die Implementierung der beiden einfachen Funktionen:

# Nur offset:

sumOfDigits.offset <- function(z, offset){
  return(scalarProd(x = z, y = offset))
}

# Nur perSequ:

sumOfDigits.perSequ <- function(z, perSequ){
  period <- length(perSequ)
  N <- length(z)
  if(period < N){    # Matrix bilden
    
    if(period == 1){
      return( sum(perSequ[1] * z) )
    } else {
      
      periods <- (N %/% period) + 1
      perSequ.ext <- rep(x = perSequ, times = periods)
      return(scalarProd(x = z, y = perSequ.ext))
    }
    
  } else {          # Skalarprodukt
    return(scalarProd(x = z, y = perSequ))
  }
}

Man erkennt, dass das Skalarprodukt fast die gesamte Arbeit übernimmt; lediglich die periodische Folge muss an die Länge von z angepasst werden.

Die hier vorgestellte Funktion sumOfDigits() setzt somit voraus, dass man eine Teilbarkeitsregel in die beiden Anteile offset und perSequ zerlegt und der Rest wird automatisch erledigt. Naheliegend ist es nun eine Funktion zu implementieren, die

Das folgende Skript zeigt eine Funktion splitDivisibilityRule(), die aus der Teilbarkeitsregel die Bestandteile offset und perSequ erkennt und in einer Liste abspeichert:

splitDivisibilityRule <- function(modulus = 1, residualSystem = (0:(modulus - 1))){
  result <- vector(mode = "list", length = 2)
  names(result) <- c("offset", "perSequ")
  
  completeSequ <- getDivisibilityRule(modulus = modulus, rs = residualSystem)
  
  # 1. Fall: Länge == 2: Grenzfall periodisch mit Periode 1
  # perSequ <- completeSequ[1]
  # 2. Fall: doppeltes Element == 0: echte Endstellenregel, nur offset setzen
  # 3. Fall: doppeltes Element != 0: entweder echte Quesummenregel oder gemischte Regel -> weiter untersuchen
  # 3.1: doppeltes Element im Index 1: echte Quersummenregel, nur perSequ setzen
  # 3.2: doppeltes Element im späteren Index: gemischte Regel; beide setzen
  
  if(length(completeSequ) == 2){
    result$offset <- completeSequ[1]
    result$perSequ <- NULL
  } else {
    dupl <- duplicated(x = completeSequ)
    idx <- which(dupl == TRUE)
    
    if(completeSequ[idx] == 0){    # echte Endstellenregel
      result$offset <- head(x = completeSequ, n = idx - 2)   # 2 Nullen am Ende abschneiden
      result$perSequ <- NULL
    }  else {         # weiter untersuchen
        if(completeSequ[idx] == 1){    # echte Quersummenregel
          result$offset <- NULL
          result$perSequ <- head(x = completeSequ, n = idx - 1)
        } else {                       # gemischte Quersummenregel: aufteilen
          splitAt <- min(which(completeSequ == completeSequ[idx]))   # Index des 1. Vorkommens der doppelten Komponente
          
          result$offset <- head(x = completeSequ, n = splitAt - 1)    # 1, ..., splitAt - 1
          result$perSequ <- completeSequ[(splitAt:(idx - 1))]         # splitAt, ..., idx - 1
        }
      }
  }
  # cat("Teiler: ", modulus, "\n")
  # cat("complete: ", completeSequ, "\n")
  # cat("Liste: ", "\n")
  # cat(str(result), "\n\n")
  return(result)
}

Die Funktion getResiduum() fasst dann alle Aufgaben zusammen. Eingabewerte sind:

Rückgabewert ist der Rest bei Division von z durch modulus (und zwar im vollständigen Restsystem der Reste).

getResiduum <- function(z, modulus){
  rule <- splitDivisibilityRule(modulus, residualSystem(modulus = modulus))
  residuum <- sumOfDigits(z = z, offset = rule$offset, perSequ = rule$perSequ)
  return(getCongruentElement(z = residuum, modulus =  modulus, residualSystem = (0:(modulus - 1))))
}

# Tests:

getResiduum(z = rep(x = c(8, 2, 1), times = 3), modulus = 7)
# 2
getResiduum(z = rep(x = c(8, 2, 1), times = 5), modulus = 32)
# 0
getResiduum(z = rep(x = c(8, 2, 1), times = 5), modulus = 22)
# 18
getResiduum(z = rep(x = c(8, 2, 1), times = 3), modulus = 22)
# 18
# 128128128 %/% 22     # 5824005
# 128128128 %% 22      # 18

Einfachere Implementierung der Berechnung des Restes

Betrachtet man die Implementierung der Funktion getResiduum() aus dem letzten Skript, so fällt auf, dass hier eigentlich ein großer Umweg gegangen wird:

Vergleicht man diese Vorgehensweise mit dem Algorithmus, der die Teilbarkeitsregel berechnet hat, fällt auf, dass die Berechnung eines Restes bei einer Division auch sehr viel leichter durchzuführen ist:

Der ausführliche Algorithmus hat den Vorteil, dass man die Teilbarkeitsregeln ausdrücklich sieht und mit diesen arbeiten kann. Das heißt man kann das Problem der Berechnung eines Restes auf mehreren Bedeutungsebenen betrachten und zum Beispiel weitergehende Fragen stellen:

Stellt man sich dagegen auf eine pragmatischen Standpunkt und möchte nur den Rest bei einer Division berechnen, ist de folgende Implementierung von getResiduum() vorzuziehen; sie verwendet eine Hilfsfunktion getPowers.10(), die die Potenzen von 10 in das vollständige Restsystem der Reste umrechnet:

getPowers.10 <- function(lgth, modulus, residualSystem){
  
  powers <- vector(mode = "integer", length = lgth)
  powers[1] <- 1
  n <- 10
  
  for(i in (2:lgth)){
    powers[i] <- getCongruentElement(z = n, modulus = modulus, 
                                     residualSystem = residualSystem(modulus =  modulus))
    n <- getCongruentElement(z = 10 * n, modulus = modulus, residualSystem = (0:(modulus - 1)))
  }
  
  return(powers)
}

# Test:

getPowers.10(lgth = 16, modulus = 7, residualSystem = residualSystem(modulus = 7))
#  [1]  1  3  2 -1 -3 -2  1  3  2 -1 -3 -2  1  3  2 -1

getResiduum.simple <- function(z, modulus){
  powers <- getPowers.10(lgth = length(z), modulus = modulus, 
                         residualSystem = residualSystem(modulus = modulus))
  return(getCongruentElement(z = scalarProd(x = z, y = powers), 
                             modulus =  modulus, residualSystem = (0:(modulus - 1))))
}

# Test:

v <- rep(x = c(8, 2, 1), times = 5)
printNumber(z = v)
# (128128128128128)_10 

getResiduum.simple(z = v, modulus = 22)
# 18
getResiduum(z = v, modulus = 22)
# 18

Man könnte jetzt einwenden, dass die Teilbarkeitsregel vollständig in den Potenzen von 10 enthalten ist. Dies ist nur zum Teil richtig. Denn die Länge des Rückgabewertes von getPowers.10() kann beliebig vorgegeben werden und richtet sich im Aufruf in getResiduum.simple() nach der Länge von z. Um daraus die Teilbarkeitsregel abzulesen und ob es eine Quersummenregel oder eine Endstellenregel ist, müssten die Potenzen von 10 erst weiter untersucht werden – was in etwa den oben beschriebenen Funktionen getDivisibilityRule() und splitDivisibilityRule() entspricht. Man beachte dazu nochmals die Implementierung von getDivisibilityRule(): Dort wird eine while-Schleife durchlaufen, die erst abbricht, wenn eine Zahl in der Folge der Teilbarkeitsregel doppelt vorkommt – die Folge also abbricht oder periodisch ist, wodurch die Teilbarkeitsregel eindeutig festgelegt ist.

Aufgabe:

Sämtliche hier vorgestellten Funktionen sind so implementiert, dass sie ohne großen Aufwand in einem anderen Zahlensystem als zur Basis 10 verwendet werden können.

Identifizieren Sie die Stellen, die ausdrücklich das Dezimalsystem verwenden und geben Sie an, wie eine neue Implementierung aussehen könnte, in der eine beliebige Basis base vorgegeben werden kann.

Im Dezimalsystem sind die Teilbarkeitsregeln für die Teiler 9 und 11 besonders einfach. Untersuchen Sie, ob im Zahlensystem zur Basis base die Teilbarkeitsregeln für base - 1 und base + 1 ebenfalls besonders einfach sind. (Diese Untersuchung kann entweder mit den entsprechenden Skripten oder theoretisch erfolgen.)