WikiDer > Modulare Berechnung

Modulare Berechnung, oder modulo berechnen eine Zahl, ist eine Form von ganze Zahlberechnen mit einer Zahl, die als obere Schranke dient, die Modul. Ein typisches Beispiel ist der Takt, auf dem Modulo 12 (oder Modulo 24) gezählt wird. Wenn es 6 Uhr ist, dann ist die Uhr 8 Stunden später nicht 14, sondern 14 − 12 = 2 Uhr.

In Modulrechnung mit modulus ${displaystyle m}$ oder modulo berechnen ${displaystyle m}$ wird mit gezählt Zahlen${displaystyle 0,1,ldots,m-1}$, danach nicht ${displaystyle m}$ folgt, beginnt aber wieder mit 0. Das ${displaystyle m}$ Zahlen 0 bis ${Anzeigestil m-1}$ stehen sozusagen im Kreis. Das Ergebnis einer Berechnung modulo ${displaystyle m}$ ist der sich ausruhen des Ergebnisses durch gewöhnliche Berechnung nach Einteilung nach dem Modul ${displaystyle m}$. Die normalen Definitionen von Zusatz und Multiplikation verwendet werden, aber wenn das Ergebnis größer oder gleich ist ${displaystyle m}$ wird genauso oft ${displaystyle m}$ subtrahiert, bis das Ergebnis wieder kleiner ist als ${displaystyle m}$. Zahlen, die modulo . sind ${displaystyle m}$ gleich sind, also a mehrere von ${displaystyle m}$ voneinander unterscheiden, heißt kongruent modular ${displaystyle m}$.

Im obigen Taktbeispiel sind 6 8 und 2 kongruent modulo 12, was wie folgt geschrieben wird:

${displaystyle 6 8äquiv 2{pmod {12}}}$

Das Sammlung Zahlen mit modulo ${displaystyle m}$ wird gezählt wird bezeichnet als ${displaystyle mathbb {Z} /mmathbb {Z} }$, zum Symbol ${displaystyle mathbb {Z} }$ was die Menge der ganzen Zahlen bezeichnet.

Beispiel

Die Berechnung modulo 7 erfolgt mit den Zahlen 0,1,...,6. Das Ergebnis von 4 5 ist nicht 9, sondern 9 − 7 = 2. Denken Sie die Zahlen im Kreis oder wiederholen Sie:

0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 0, ...

und wenn Sie 5 weiter zählen als die Zahl 4, kommen Sie bei 2.

Was ist 4×5? Nicht 20, sondern 20 − 7 − 7 = 6. Das kann man auch so sehen als

4 × 5 = 5 5 5 5 = (5 5) 5 5 ≡ 3 5 5 = (3 5) 5 ≡ 1 5 = 6

(hier bezeichnet geeft a Äquivalenzrelation Auf)

Die folgende Tabelle zeigt alle Möglichkeiten für die Addition modulo 7.

Addition modulo 7

	0	1	2	3	4	5	6
0	0	1	2	3	4	5	6
1	1	2	3	4	5	6	0
2	2	3	4	5	6	0	1
3	3	4	5	6	0	1	2
4	4	5	6	0	1	2	3
5	5	6	0	1	2	3	4
6	6	0	1	2	3	4	5

Für die Multiplikation kann auch eine Tabelle erstellt werden.

Multiplikation modulo 7

×	0	1	2	3	4	5	6
0	0	0	0	0	0	0	0
1	0	1	2	3	4	5	6
2	0	2	4	6	1	3	5
3	0	3	6	2	5	1	4
4	0	4	1	5	2	6	3
5	0	5	3	1	6	4	2
6	0	6	5	4	3	2	1

Mit dieser Tabelle können auch Divisionen durchgeführt werden. Was ist 5 : 4 modulo 7? Nennen Sie diese Zahl q, dann 4 q 5 modulo 7. Aus der Tabelle kann man ablesen, dass q = 3, also 5 : 4 ≡ 3 modulo 7.

Definition

Sie ${displaystyle n}$ ein natürliche Zahl ungleich 0, dann heißen die beiden ganzen Zahlen ${Anzeigestil a}$ und ${displaystyle b}$kongruent modulo${displaystyle n}$, notiert:

${displaystyle aequiv b{pmod {n}}}$,

als ihr Unterschied ${Anzeigestil a-b}$ ist ein ganzzahliges Vielfaches von ${displaystyle n}$.

Die Nummer ${displaystyle n}$ wird der Modul erwähnt.

Es ist zu beachten, dass die Klammern um "${displaystyle {pmod {m}}}$auch weggelassen werden.

in vielen Programmiersprachen das Vorzeichen für den Modul ist das Prozentzeichen (%).

Anwendung

Das bekannteste Beispiel für modulare Arithmetik ist die Zeitberechnung in ganzen Stunden (beliebige Zeiten siehe auch unten), die nach Modulo 12 oder Modulo 24 geht. Zum Beispiel entspricht die Zeit 10 Stunden nach 22:00 Uhr 8 Stunden. Also 10 22 = 8 modulo 24.

Integer-Arithmetik im Digitalen Computers erfolgt in der Regel modulo ${Displaystil 2^{n}}$, bei welchem ${displaystyle n}$ die Anzahl der Bits wird verwendet, um eine Zahl darzustellen. ${displaystyle n}$ ist dann begrenzt durch (normalerweise) die Größe von a bound Prozessorregister. In einem typischen modernen Computer ${displaystyle n}$ der Wert 32 oder 64. Nicht-modulare Arithmetik wird von einigen Programmiersprachen unterstützt, geht jedoch auf Kosten der Rechengeschwindigkeit.

Im Belgien hat beides strukturierte Kommunikation von a Transfer, ebenso wie Kontonummer und der Nationale Versicherungsnummer als letzte zwei Ziffern a Prüfziffer dass Modulo 97 deckungsgleich mit den vorhergehenden Figuren ist. Für die strukturierte Kommunikation 090/9337/55493 gilt dies beispielsweise 0909337554 ≡ 93 (mod 97). Auch in der IBAN eine Modulo 97-Berechnung wird durchgeführt, um eine zweistellige Prüfziffer zu berechnen.

Algebra

Das lässt sich leicht zeigen ${displaystyle (mathbb {Z} /mmathbb {Z} )}$algebraisch gesehen als Ring ist und ist ein Kommutativer Ring mit Einheitselement. Die Elemente von ${displaystyle mathbb {Z} /mmathbb {Z} }$ heißt der Restklassen modular ${displaystyle m}$.

In dem speziellen Fall, dass ${displaystyle m}$ ein Primzahl ist, ist ${displaystyle (mathbb {Z} /mmathbb {Z} )}$ sogar ein Körper. (Achtung: was heißt a Körper anruft, ist in Belgien a Feld. Was in Belgien als Körper bezeichnet wird, ist in den Niederlanden ein krummer Körper!)

Letztere lässt sich wie folgt zeigen: Aus der Definition einer Primzahl folgt, dass eine Primzahl ${displaystyle m}$relativ prim ist mit allen Zahlen ${displaystyle 1,ldots,m-1}$ zwischen 0 und ${displaystyle m}$ (weil 1 der einzige Teiler von ist ${displaystyle m}$ was weniger ist als ${displaystyle m}$ selbst). Verwendung der Euklids erweiterter Algorithmus kann jetzt für alle gemacht werden ${displaystyle n}$ zwischen 1 und ${displaystyle m}$ die Zahlen ${Anzeigestil x}$ und ${Anzeigestil y}$ gefunden werden, damit ${displaystyle nx my={m {ggd}}(n,m)}$.

Jetzt der Begriff ${displaystyle mein}$ modular ${displaystyle m}$ gleich 0, weil ${displaystyle my/m=y{ ext{ rest }}0}$. Weiterhin gilt, dass ${displaystyle {m {ggd}}(n,m)=1}$, weil ${displaystyle n}$ und ${displaystyle m}$ sind relativ prim.

Also modulo eine Primzahl ${displaystyle m}$ ist für alle da ${displaystyle n}$ ein ${Anzeigestil x}$ so dass ${displaystyle nx=1}$.

Potenzierung

Bei der Erhöhung modular ${displaystyle m}$ darf nur die Basen reduziert werden, nicht die Exponenten. Beispielsweise:

${displaystyle 8^{5}Äquiv. 3^{5}{ mod {5}}}$

${Displaystil 3^{5}Äquiv. 3{mod {5}}}$

${Displaystil 3^{0}Äquiv. 1{ mod {5}}}$

Es gilt jedoch folgendes Satz von Euler: wenn die Basis keine Teiler mit gemein hat ${displaystyle m}$, dann kann der Exponent modulo de . umgewandelt werden Euler-Indikator${displaystyle varphi(m)}$ von ${displaystyle m}$.

große Mächte

Potenzierung modulo ${displaystyle m}$ zu großen Kräften können relativ einfach ausgeführt werden mit Potenzierung durch Quadrieren, schon seit

${displaystyle (x{ mod {m}})^{2}äquivalent x^{2}{ mod {m}}}$

Zu ${displaystyle 298^{187}{ mod {3}}19}$ können sukzessive die Leistungen berechnet werden ${displaystyle 298^{2}{ mod {3}}19}$, ${displaystyle(298^{2})^{2}{ mod {3}}19}$, ${displaystyle (298^{4})^{2}{ mod {3}}19,ldots ,298^{128}{ mod {3}}19}$ berechnet werden. weil ${Anzeigestil 187=128 32 16 8 2 1}$, wird die angeforderte Leistung als das Produkt Modulo 319 der entsprechenden Leistungen bestimmt.

Beispiel und Gegenbeispiel zum Satz von Euler

Der Euler-Indikator von 5 ist 4, und zwar:

${Displaystil 3^{5-4}Äquiv. 3{pmod {5}}}$

Dies liegt daran, dass 3 und 5 relativ prim sind.

Im Gegensatz dazu haben 5 und 10 einen gemeinsamen Teiler und nach Umrechnung des Exponenten modulo 4, des Euler-Indikators von 10, ergibt sich:

${displaystyle 5^{4}äquivalent 5{pmod {10}}{mbox{ }},}$ aber: ${displaystyle 5^{0}Äquiv. 1{pmod {10}}}$

Reale Nummern

In Analogie zur modularen Arithmetik mit ganzen Zahlen, wobei Vielfache einer bestimmten ganzen Zahl ${Anzeigestil a}$ außer Acht gelassen, kann man auch reelle Zahlen addieren und subtrahieren (und mit ganzen Zahlen multiplizieren), wobei Vielfache einer positiven reellen Zahl ${Anzeigestil a}$ außer Acht gelassen werden. Ein Beispiel ist das Rechnen mit der Tageszeit, das Nichtbeachten von Vielfachen von 24 Stunden oder die Zeitanzeige auf einer Uhr mit Zeigern, das Nichtbeachten von Vielfachen von 12 Stunden, und dementsprechend das Rechnen mit Winkeln, bei denen vollständige Umdrehungen vernachlässigt werden. Die mit der Addition verbundene Gruppe ist die Kreisgruppe${displaystyle mathbb {R} /amathbb {Z} }$.

Die Multiplikation mit ganzen Zahlen kann als additive Gruppe hinzugefügt werden, da sie einer wiederholten Addition oder einer wiederholten Subtraktion von Null entspricht. Wenn man jedoch die Multiplikation beliebiger Elemente hinzufügt (definiert durch einfache Multiplikation, ignoriert man Vielfache von ${Anzeigestil a}$) wird es nicht sein Ring, denn zum Beispiel für ${Anzeigestil b=min(a/2,1)}$ gilt ${displaystyle b imes (a/2 a/2)=b imes 0=0}$, während ${displaystyle b imes (a/2) b imes (a/2)=ba}$. Es gibt also keine Verteilungsfähigkeit (es bedeutet einfach, dass als Begriff ${Anzeigestil a}$ außer Acht gelassen, gilt dies offensichtlich nicht für eine beliebige reelle Zahl mal ${Anzeigestil a}$).

Siehe auch

• Sich ausruhen
• Integer-Division