In der Mathematik ist Modularithmetik (manchmal genannt Uhr-Arithmetik) ein System der Arithmetik für ganze Zahlen, wo sich Zahlen "ringsherum einhüllen", nachdem sie einen bestimmten Wert — das Modul erreichen.

Der schweizerische Mathematiker Leonhard Euler hat für die moderne Annäherung an die Kongruenz ungefähr 1750 den Weg gebahnt, als er ausführlich die Idee von der Kongruenz modulo eine Nummer N eingeführt hat.

Modularithmetik wurde weiter von Carl Friedrich Gauss in seinem Buch Disquisitiones Arithmeticae, veröffentlicht 1801 vorgebracht.

Ein vertrauter Gebrauch der Modularithmetik ist in der 12-stündigen Uhr, in der der Tag in zwei 12-stündige Perioden geteilt wird. Wenn die Zeit 7:00 jetzt ist, dann 8 Stunden später wird es 3:00 sein. Übliche Hinzufügung würde darauf hinweisen, dass die spätere Zeit 7 + 8 = 15 sein sollte, aber das ist nicht die Antwort, weil sich Uhr-Zeit "ringsherum" alle 12 Stunden einhüllt; in der 12-stündigen Zeit gibt es keine "15 Uhr". Ebenfalls, wenn die Uhr-Anfänge an 12:00 (Mittag) und 21 Stunden vergehen, dann wird die Zeit 9:00 am nächsten Tag, aber nicht 33:00 sein. Da die Stunde-Zahl anfängt, nachdem sie 12 reicht, ist das Arithmetik modulo 12. 12 ist nicht nur zu 12 selbst, sondern auch zu 0 kongruent, so konnte die Zeit genannt "12:00" auch "0:00", seit 0  12 mod 12 genannt werden.

Kongruenz-Beziehung

Modularithmetik kann mathematisch durch das Einführen einer Kongruenz-Beziehung auf den ganzen Zahlen behandelt werden, die mit den Operationen des Rings von ganzen Zahlen vereinbar ist: Hinzufügung, Subtraktion und Multiplikation. Für eine positive ganze Zahl, wie man gesagt wird, sind n, zwei ganze Zahlen a und b kongruenter modulo n, geschrieben:

:

wenn ihr Unterschied ein  b eine von n vielfache ganze Zahl ist. Die Nummer n wird das Modul der Kongruenz genannt.

Zum Beispiel,

:

weil 38  14 = 24, der ein Vielfache 12 ist.

Dieselbe Regel hält für negative Werte:

:::

Wenn und entweder beide positiv oder beide negativen sind, auch dann als das Erklären gedacht werden kann, dass beide und denselben Rest haben. Zum Beispiel:

:

weil beide und denselben Rest haben. Es ist auch der Fall, der eine ganze Zahl ist, die dessen vielfach ist, der mit der vorherigen Definition der Kongruenz-Beziehung übereinstimmt.

Eine Bemerkung auf der Notation: Weil es üblich ist, mehrere Kongruenz-Beziehungen für verschiedene Module zur gleichen Zeit zu denken, wird das Modul in der Notation vereinigt. Trotz der dreifältigen Notation ist die Kongruenz-Beziehung für ein gegebenes Modul binär. Das wäre klarer gewesen, wenn die Notation ein b statt der allgemeinen traditionellen Notation verwendet worden wäre.

Die Eigenschaften, die diese Beziehung eine Kongruenz-Beziehung machen (Hinzufügung, Subtraktion und Multiplikation respektierend), sind das folgende.

Wenn:und:

dann:

Es sollte bemerkt werden, dass die obengenannten zwei Eigenschaften noch halten würden, ob die Theorie ausgebreitet wurde, um alle reellen Zahlen einzuschließen, ist dieser, wenn nicht notwendigerweise alle ganzen Zahlen waren. Das folgende Eigentum würde jedoch scheitern, wenn diese Variablen nicht alle ganzen Zahlen wären:

Ring von Kongruenz-Klassen

Wie jede Kongruenz-Beziehung ist Kongruenz modulo n eine Gleichwertigkeitsbeziehung, und die Gleichwertigkeitsklasse der ganzen Zahl a, angezeigt dadurch, ist der Satz. Dieser Satz, aus den ganzen Zahlen bestehend, die zu einem modulo n kongruent sind, wird die Kongruenz-Klasse oder die Rückstand-Klasse oder einfach den Rückstand der ganzen Zahl a, modulo n genannt. Wenn das Modul n vom Zusammenhang bekannt ist, kann dieser Rückstand auch angezeigt werden.

Der Satz aller Kongruenz-Klassen modulo n wird angezeigt, oder (wird die abwechselnde Notation wegen der möglichen Verwirrung mit dem Satz von n-adic ganzen Zahlen nicht empfohlen). Es wird definiert durch:

:

Wenn n  0, n Elemente hat, und als geschrieben werden kann:

:

Wenn n = 0, Nullelemente nicht hat; eher ist es zu seitdem isomorph.

Wir können Hinzufügung, Subtraktion und Multiplikation auf durch die folgenden Regeln definieren:

Die Überprüfung, dass das eine richtige Definition ist, verwendet die Eigenschaften, die vorher gegeben sind.

Auf diese Weise, wird ein Ersatzring. Zum Beispiel, im Ring, haben wir

:

als in der Arithmetik für die 24-stündige Uhr.

Die Notation wird verwendet, weil es der Faktor-Ring durch das Ideal ist, das alle durch n teilbaren ganzen Zahlen enthält, wo der Singleton-Satz ist. So ist ein Feld, wenn ein maximales Ideal ist, d. h. wenn erst ist.

In Bezug auf Gruppen ist die Rückstand-Klasse der coset in der Quotient-Gruppe, einer zyklischen Gruppe.

Der Satz hat mehrere wichtige mathematische Eigenschaften, die foundational zu verschiedenen Zweigen der Mathematik sind.

Anstatt des Ausschließens des speziellen Falls n = 0 ist es nützlicher einzuschließen (der, wie erwähnt, vorher, zum Ring von ganzen Zahlen isomorph ist), zum Beispiel, wenn man die Eigenschaft eines Rings bespricht.

Reste

Der Begriff der Modularithmetik ist mit diesem des Rests in der Abteilung verbunden. Die Operation, den Rest zu finden, wird manchmal die modulo Operation genannt, und wir können sehen. Der Unterschied ist im Gebrauch der Kongruenz, die durch "" und Gleichheit angezeigt ist, die durch "=" angezeigt ist. Gleichheit bezieht spezifisch den "allgemeinen Rückstand", das am wenigsten nichtnegative Mitglied einer Gleichwertigkeitsklasse ein. Wenn man mit der Modularithmetik arbeitet, wird jede Gleichwertigkeitsklasse gewöhnlich durch seinen allgemeinen Rückstand zum Beispiel vertreten, der mit der langen Abteilung gefunden werden kann. Hieraus folgt dass, während es richtig ist, um zu sagen, und, es falsch ist (mit "=" aber nicht "") zu sagen.

Der Unterschied ist am klarsten, wenn er eine negative Zahl teilt, seitdem in diesem Fall sind Reste negativ. Folglich, um den Rest auszudrücken, würden wir schreiben müssen, aber nicht, da Gleichwertigkeit nur von allgemeinen Rückständen mit demselben Zeichen gesagt werden kann.

In der Informatik ist es der Rest-Maschinenbediener, der gewöhnlich durch jeden "%" (z.B in C, Java, Javascript, Perl und Python) oder "mod" (z.B in Pascal, GRUNDLEGEND, SQL, Haskell) mit Ausnahmen angezeigt wird (z.B. Ragen Sie Hervor). Diese Maschinenbediener werden als "mod" allgemein ausgesprochen, aber es ist spezifisch ein Rest, der geschätzt wird (da in C ++ negative Zahl zurückgegeben wird, wenn das erste Argument negativ ist, und in der Pythonschlange eine negative Zahl zurückgegeben wird, wenn das zweite Argument negativ ist). Die Funktion modulo statt mod, wie 38  14 (modulo 12) wird manchmal verwendet, um den allgemeinen Rückstand aber nicht einen Rest (z.B in Ruby) anzuzeigen.

Parenthesen sind manchmal vom Ausdruck z.B fallen gelassen oder, oder um den Teiler z.B Notation gelegt, die auch beobachtet worden ist, aber ohne Kontexterläuterung zweideutig ist.

Funktionelle Darstellung der Rest-Operation

Die Rest-Operation kann mit der Fußboden-Funktion vertreten werden. Wenn b  (mod n), wo n> 0, dann, wenn der Rest b berechnet wird

:

wo die größte ganze Zahl weniger ist als oder gleich, dann

::

ein \equiv b \pmod n \text {und, }\\\

0 \le b

Wenn stattdessen ein Rest b in der Reihe n  b

Rückstand-Systeme

Jede Rückstand-Klasse modulo n kann von irgendwelchen seiner Mitglieder vertreten werden, obwohl wir gewöhnlich jede Rückstand-Klasse durch die kleinste natürliche Zahl vertreten, die dieser Klasse gehört (da das der richtige Rest ist, der sich aus Abteilung ergibt). Bemerken Sie, dass irgendwelche zwei Mitglieder von verschiedenen Rückstand-Klassen modulo n incongruent modulo n sind. Außerdem gehört jede ganze Zahl einer und nur einer Rückstand-Klasse modulo n.

Der Satz von ganzen Zahlen {0, 1, 2..., n - 1} wird kleinstes Rückstand-System modulo n genannt. Jeder Satz von n ganzen Zahlen, von denen keine zwei kongruenter modulo n sind, wird ein ganzes Rückstand-System modulo n genannt.

Es ist klar, dass kleinstes Rückstand-System ein ganzes Rückstand-System ist, und dass ein ganzes Rückstand-System einfach ein Satz ist, der genau einen Vertreter jeder Rückstand-Klasse modulo n enthält. Kleinstes Rückstand-System modulo 4 ist {0, 1, 2, 3}. Einige andere ganze Rückstand-Systeme modulo 4 sind:

• {1,2,3,4 }\
• {13,14,15,16 }\
• {-2,-1,0,1 }\
• {-13,4,17,18 }\
• {-5,0,6,21 }\
• {27,32,37,42 }\

Einige Sätze, die nicht ganze Rückstand-Systeme modulo 4 sind, sind:

• {-5,0,6,22} seitdem 6 ist zu 22 modulo 4 kongruent.
• {5,15} da muss ein ganzes Rückstand-System modulo 4 genau 4 incongruent Rückstand-Klassen haben.

Reduzierte Rückstand-Systeme

Jeder Satz von φ (n) ganze Zahlen, die zu n relativ erst sind, und die gegenseitig incongruent modulo n sind, wo φ (n) die Totient-Funktion von Euler anzeigt, wird ein reduziertes Rückstand-System modulo n genannt. Das Beispiel oben, {5,15} ist ein Beispiel eines reduzierten Rückstand-Systems modulo 4.

Anwendungen

In

Modularithmetik wird in der Zahlentheorie, Gruppentheorie, Ringtheorie, Knoten-Theorie, abstrakten Algebra, Geheimschrift, Informatik, Chemie und den Seh- und Musikkünsten Verweise angebracht.

Es ist eines der Fundamente der Zahlentheorie, fast jeden Aspekt seiner Studie berührend, und stellt Schlüsselbeispiele für die Gruppentheorie, Ringtheorie und abstrakte Algebra zur Verfügung.

Modularithmetik wird häufig verwendet, um Kontrollsummen zu berechnen, die innerhalb von Bezeichnern verwendet werden - machen Internationale Bankkonto-Zahlen (IBANs) zum Beispiel von modulo 97 Arithmetik Gebrauch, um Benutzereingangsfehler in Bankkonto-Zahlen zu fangen.

In der Geheimschrift unterstützt Modularithmetik direkt öffentliche Schlüsselsysteme wie RSA und Diffie-Hellman, sowie Versorgung begrenzter Felder, die elliptischen Kurven unterliegen, und in einer Vielfalt von symmetrischen Schlüsselalgorithmen einschließlich AES, IDEE und RC4 verwendet wird.

In der Informatik wird Modularithmetik häufig in bitwise Operationen und anderen Operationen angewandt, die mit fester Breite, zyklischen Datenstrukturen verbunden sind. Die modulo Operation, wie durchgeführt, auf vielen Programmiersprachen und Rechenmaschinen, ist eine Anwendung der Modularithmetik, die häufig in diesem Zusammenhang verwendet wird. XOR ist die Summe von 2 Bit, modulo 2.

In der Chemie ist die letzte Ziffer der CAS Registrierungszahl (eine Zahl, die für jede chemische Zusammensetzung einzigartig ist) eine Prüfziffer, die durch die Einnahme der letzten Ziffer der ersten zwei Teile der CAS Registrierungszahl-Zeiten 1, die nächsten Ziffer-Male 2, die nächsten Ziffer-Male 3 usw., das Hinzufügen von allen diese und die Computerwissenschaft der Summe modulo 10 berechnet wird.

In der Musik wird Arithmetik modulo 12 in der Rücksicht des Systems des gleichen Zwölftontemperaments verwendet, wo Oktave und enharmonic Gleichwertigkeit vorkommen (d. h. Würfe in einem 12 oder 21 Verhältnis sind gleichwertig, und C-sharp wird dasselbe als D-Wohnung betrachtet).

Die Methode, nines zu vertreiben, bietet eine Schnellkontrolle der dezimalen arithmetischen Berechnung durchgeführt mit der Hand an. Es basiert auf der Modularithmetik modulo 9, und spezifisch auf dem entscheidenden Eigentum dass 10  1 (mod 9).

Arithmetik modulo 7 ist in der Bestimmung des Tages der Woche im Gregorianischen Kalender besonders wichtig. Insbesondere die Kongruenz von Zeller und der Weltgericht-Algorithmus machen schweren Gebrauch der modulo-7 Arithmetik.

Mehr allgemein hat Modularithmetik auch Anwendung in Disziplinen wie Gesetz (sieh z.B, richtige Verteilung), Volkswirtschaft, (sieh z.B, Spieltheorie), und andere Gebiete der Sozialwissenschaften, wo proportionale Abteilung und Zuteilung von Mitteln eine Hauptrolle der Analyse spielen.

Rechenbetonte Kompliziertheit

Da Modularithmetik solch eine breite Reihe von Anwendungen hat, ist es wichtig zu wissen, wie hart es ein System von Kongruenzen lösen soll. Ein geradliniges System von Kongruenzen kann in der polynomischen Zeit mit einer Form der Beseitigung von Gaussian gelöst werden, weil Details geradlinigen Kongruenz-Lehrsatz sehen. Algorithmen, wie die Verminderung von Montgomery, bestehen auch, um einfache arithmetische Operationen, wie Multiplikation und exponentiation modulo n zu erlauben, effizient auf der großen Anzahl durchgeführt zu werden.

Das Lösen eines Systems von nichtlinearen arithmetischen Modulgleichungen ist NP-complete.

Siehe auch

• Boolean rufen an
• Kreisförmiges kreisförmiges Puffermathegedächtnis, richtend
• Kongruenz-Beziehung
• Abteilung
• Begrenztes Feld
• Symbol von Legendre
• Modularer exponentiation
• Multiplicative Modulgegenteil
• Operation von Modulo
• Periode von Pisano (Folgen von Fibonacci modulo n)
• Primitive Wurzel
• Quadratische Reziprozität
• Quadratischer Rückstand
• Zahlentheorie
• Reduziertes Rückstand-System
• Boolean Zwei-Elemente-Algebra
• Seriennummer-Arithmetik (ein spezieller Fall der Modularithmetik)
• Themen in Zusammenhang mit der Gruppentheorie hinter der Modularithmetik:
• Zyklische Gruppe
• Gruppe von Multiplicative von ganzen Zahlen modulo n
• Andere wichtige Lehrsätze in Zusammenhang mit der Modularithmetik:
• Der Lehrsatz von Carmichael
• Chinesischer Rest-Lehrsatz
• Der Lehrsatz von Euler
• Der kleine Lehrsatz von Fermat (ein spezieller Fall des Lehrsatzes von Euler)
• Der Lehrsatz von Lagrange

Referenzen

• http://www.britannica.com/EBchecked/topic/920687/modular-arithmetic Encyclopædia Britannica. Modularithmetik.
• . Sieh in besonderen Kapiteln 5 und 6 für eine Rezension der grundlegenden Modularithmetik.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest und Clifford Stein. Einführung in Algorithmen, die Zweite Ausgabe. MIT Presse und McGraw-Hügel, 2001. Internationale Standardbuchnummer 0-262-03293-7. Abschnitt 31.3: Modularithmetik, Seiten 862-868.
• Anthony Gioia, Zahlentheorie, ein Einführungsnachdruck (2001) Dover. Internationale Standardbuchnummer 0-486-41449-3

. .

Links

• In diesem Modulkunstartikel kann man mehr über Anwendungen der Modularithmetik in der Kunst erfahren.
• Ein Artikel über die Modularithmetik auf dem GIMPS wiki
• Modularithmetik und Muster außerdem und Multiplikationstabellen
• Musik-Kasten von Whitney — eine Audio/Video Demonstration der ganzen Zahl Modulmathematik
• Automatisierter arithmetischer Modullehrsatz provers:
• Speer
• AAProver — Einfache C ++ Fachwerk, das leicht ist, in anderen Anwendungen zu verwenden, (unter anderen) alle Maschinenbediener der ganzen Zahl unterstützend, präsentieren auf Sprachen wie C/C ++/Java und willkürliche Bit-Breite.