Kongruenz (Zahlentheorie)

Kongruenz (Zahlentheorie)

Die Kongruenz ist in der Zahlentheorie eine Beziehung zwischen drei ganzen Zahlen. Man nennt zwei Zahlen kongruent bezüglich eines Moduls (eine weitere Zahl), wenn sie bei Division durch den Modul denselben Rest haben. Das ist genau dann der Fall, wenn sie sich um ein ganzzahliges Vielfaches des Moduls unterscheiden. Stimmen die Reste nicht überein, so nennt man die Zahlen inkongruent bezüglich des Moduls.

Beispielsweise ist 5 kongruent 11 modulo 3, da 5: 3 = 1 \, \operatorname{Rest} \, 2 und 11: 3 = 3 \, \operatorname{Rest} \, 2, bzw. 11 - 5 = 6 = 2 \cdot 3. Und -8 ist kongruent zu 10 modulo 6, denn bei Division durch 6 liefern sowohl 10 als auch -8 den Rest 4. Man beachte, dass die mathematische Definition der Ganzzahldivision zugrunde gelegt wird, nach der der Rest dasselbe Vorzeichen wie der Divisor (hier 6) erhält, also -8 : 6 = -2 \, \operatorname{Rest} \, 4.

Für die Aussage „a und b sind kongruent modulo m“ verwendet man folgende Schreibweisen:

  • a \equiv b \mod m
  • a \equiv b \quad ( \bmod \; m)
  • a \equiv b \quad (m).

Die Bedeutung von Kongruenzen beruht darauf, dass mit ihnen annähernd wie mit Gleichungen gerechnet werden kann.

Die Theorie der Kongruenzen wurde von Carl Friedrich Gauß in seinem im Jahr 1801 veröffentlichten Werk „Disquisitiones Arithmeticae“ entwickelt. Der Begriff Kongruenz wurde von Christian Goldbach schon ab 1730 in Briefen an Leonhard Euler verwendet, jedoch ohne die theoretische Tiefe von Gauß. Im Gegensatz zu Gauß verwendete Goldbach das Symbol \mp und nicht \equiv.[1] Auch der chinesische Mathematiker Ch'in Chiu-Shao kannte schon Kongruenzen und die damit einhergehende Theorie, wie aus seinem 1247 veröffentlichten Buch „Mathematische Abhandlung in neun Kapiteln“ hervorgeht.[2]

Inhaltsverzeichnis

Formale Definition

In der Zahlentheorie wird die Kongruenz auf eine Teilbarkeitsaussage zurückgeführt. Seien dazu a, b und m ganze Zahlen, d.h. Elemente aus \Z.

Zwei Zahlen a und b heißen kongruent modulo m, wenn m die Differenz ab teilt.
Zwei Zahlen a und b heißen inkongruent modulo m, wenn m die Differenz ab nicht teilt.

Unter Verwendung der mathematischen Notation lassen sich diese beiden Aussagen wie folgt schreiben:

a \equiv b \pmod m
\Leftrightarrow m \mid (a-b)
\Leftrightarrow \exists k \in \Z: a = km + b
a \not \equiv b \pmod m
\Leftrightarrow m \nmid (a-b)
\Leftrightarrow \forall k \in \Z: a \ne km + b

Restklassen

Die Kongruenz ist eine Äquivalenzrelation. Sie hat also die folgenden Eigenschaften:

Reflexivität
a \equiv a \pmod{m} für alle a \in \mathbb{Z}
Symmetrie
a \equiv b \pmod{m} \Rightarrow b \equiv a \pmod{m} für alle (a, b) \in \mathbb{Z}^2
Transitivität
a \equiv b \pmod{m} und b \equiv c \pmod{m} \Rightarrow a \equiv c \pmod{m} für alle (a, b, c) \in \mathbb{Z}^3

Legt man einen Modul fest, so kann dadurch die Menge aller Zahlen auf sogenannte Restklassen verteilt werden. In einer Restklasse befinden sich alle Zahlen, die unter dem festgelegten Modul kongruent zueinander sind, die also stets den gleichen Rest aufweisen. Der Absolutwert des Modul entspricht immer der Anzahl der Restklassen. Beispielsweise existieren für den Modul 2 die beiden Restklassen der geraden und der ungeraden Zahlen. Die Restklassen eines Moduls bilden einen Ring, den sogenannten Restklassenring.

Rechenregeln

Im Folgenden seien a, a', b, b', c und m ganze Zahlen. Dabei sei m \ne 0, a \equiv a' \pmod{m} und b \equiv b' \pmod{m}. Dann gelten folgende Rechenregeln:

ca \equiv ca' \pmod{m}
a + b \equiv a' + b' \pmod{m}
a - b \equiv a' - b' \pmod{m}
ab \equiv a'b' \pmod{m}

Ist f \in \mathbb{Z}[X] ein Polynom über den ganzen Zahlen, dann gilt

f(a) \equiv f(a') \pmod{m}

Auch bei Kongruenzen ist ein Kürzen möglich. Es gelten jedoch andere Kürzungsregeln als von rationalen oder reellen Zahlen gewohnt. Ist der Modul m ungleich Null, so gilt

ca \equiv cb \pmod{m} \Leftrightarrow a \equiv b \pmod{\frac{m}{\operatorname{ggT}(c,m)}}

Daraus folgt unmittelbar, dass wenn der Modul eine Primzahl p und diese kein Teiler von c ist, gilt

ca \equiv cb \pmod{p} \Leftrightarrow a \equiv b \pmod{p}

Für jeden Teiler d von m folgt aus a\equiv b \mod m, dass a\equiv b \mod d.

Sind m_1, m_2, \ldots, m_k ganze Zahlen ungleich null und ist m ihr kleinstes gemeinsames Vielfaches, dann gilt

a \equiv a' \pmod{m_\kappa} für alle \kappa = 1, 2, \ldots, k \quad \Leftrightarrow \quad a \equiv a' \pmod{m}

Potenzen

Ist n \in \mathbb{N}_0 eine natürliche Zahl, dann gilt

a^n \equiv (a')^n \pmod{m}

Sind a und m teilerfremd, dann gilt nach dem Satz von Euler

a^{\varphi(m)} \equiv 1 \pmod m

wobei \varphi(m) die Eulersche φ-Funktion bezeichnet. Ein Spezialfall davon ist der kleine Fermat’sche Satz, demzufolge für alle Primzahlen p die Kongruenz

a^p \equiv a \pmod p

erfüllt ist.

Abgeleitete Rechenregeln

  1. Für t \ne 0 gilt: \qquad t \cdot a \equiv t \cdot b \mod |t| \cdot m
  2. Ist k ein Teiler von m, dann gilt: \qquad a \equiv b \mod k
  3. Für jede ungerade Zahl a gilt a^2 \equiv 1 \mod 8
  4. Für jede ganze Zahl gilt entweder a^3 \equiv 0 \mod 9 oder a^3 \equiv 1 \mod 9 oder a^3 \equiv 8 \mod 9
  5. Für jede ganze Zahl a gilt a^3 \equiv a \mod 6
  6. Für jede ganze Zahl gilt entweder a^3 \equiv 0 \mod 7 oder a^3 \equiv 1 \mod 7 oder a^3 \equiv 6 \mod 7
  7. Für jede ganze Zahl gilt entweder a^4 \equiv 0 \mod 5 oder a^4 \equiv 1 \mod 5
  8. Ist a sowohl eine Quadratzahl als auch eine Kubikzahl (z. B. a = 64) dann gilt entweder a \equiv 0 \mod 36 oder a \equiv 1 \mod 36 oder a \equiv 9 \mod 36 oder a \equiv 28 \mod 36
  9. Sei p eine Primzahl mit n < p < 2n. Dann gilt
    {2n \choose n} \equiv 0 \mod{p}
  10. Sei a eine ungerade ganze Zahl. Ferner sei n > 0. Dann gilt: a^{2^n} \equiv 1 \mod 2^{n+2}
  11. Sei p > 3. Ferner seien p und q = p + 2 Primzahlzwillinge. Dann gilt: p \cdot q \equiv -1 \mod 9

Lösbarkeit von Kongruenzen

Eine lineare Kongruenz der Form \qquad ax \equiv c \; (\bmod \, m) ist genau dann in x lösbar, wenn g = \operatorname{ggT}(a, m) die Zahl c teilt. g ist dann auch die Anzahl der Lösungen in \{0,1,\cdots,m-1\}, und die Lösungen sind zueinander kongruent modulo m / g.

Auch für große m kann man die Lösungen effizient ermitteln, indem man den erweiterten euklidischen Algorithmus auf a und m anwendet, der neben g auch zwei Zahlen s und t berechnet, die g als Linearkombination von a und m ausdrücken:

 g = \operatorname{ggT}(a, m) = s\cdot a + t \cdot m .

Eine Lösung erhält man dann mit x_1 = (s \cdot c) / g, und die übrigen Lösungen unterscheiden sich von x1 um ein Vielfaches von m / g.

Beispiel:  4x \equiv 10 \; (\bmod \, 18) ist lösbar, denn \operatorname{ggT}(4,18) = 2 teilt die Zahl 10, und es gibt 2 Lösungen im Bereich 0 \leq x < 18. Der erweiterte euklidische Algorithmus liefert  2 = -4 \cdot 4 + 1 \cdot 18, was die Lösung x = (-4 \cdot 10) / 2 = -20 ergibt. Die Lösungen sind kongruent modulo 18 / 2 = 9. Somit ist die Lösungsmenge

 \{ \cdots , -20, -11, -2, 7, 16, 25, \cdots \} .


Eine simultane Kongruenz wie

\qquad a_1x \equiv c_1 \; (\bmod \, m_1)
\qquad a_2x \equiv c_2 \; (\bmod \, m_2)
\qquad a_3x \equiv c_3 \; (\bmod \, m_3)

ist sicher dann lösbar, wenn für alle i gilt: g_i = \operatorname{ggT}(a_i, m_i) teilt die Zahl ci und wenn die mi / gi paarweise zueinander teilerfremd sind. Der Beweis des Chinesischen Restsatzes liefert den Lösungsweg für solche simultanen Kongruenzen.

Beziehung zur Modulo-Funktion

Sind zwei Zahlen kongruent modulo einer Zahl m, ergibt sich bei der Division durch m derselbe Rest.

Mithilfe der vor allem in der Informatik verbreiteten Modulo-Funktion kann man dies so schreiben:

a~\bmod~m = b~\bmod~m.

Man beachte, dass dies mit der in der Informatik üblichen Modulo-Funktion nur für positive a und b richtig ist. Damit die Gleichung tatsächlich für alle a und b äquivalent zur Kongruenz wird, muss man die durch

(a~\bmod~m)= a - \lfloor a/m \rfloor \cdot m

definierte Modulo-Funktion verwenden. (\lfloor. \rfloor ist die Gaußklammer.) Mit dieser Definition gilt beispielsweise ( − 1)mod 7 = 6.

Anwendungen

Kongruenzen bzw. Restklassen sind oft hilfreich, wenn man Berechnungen mit sehr großen Zahlen durchführen muss.

Eine wichtige Aussage über Kongruenzen von Primzahlen ist der kleine Satz von Fermat bzw. der fermatsche Primzahltest.

Siehe auch

Quellen

  1. Peter Bundschuh: Einführung in die Zahlentheorie. 5. Auflage. Springer, Berlin 2002, ISBN 3-540-43579-4
  2. Song Y. Yan: Number theory for computing. 2. Auflage. Springer, 2002, ISBN 3-540-43072-5, S. 111–117

Weblinks


Wikimedia Foundation.

Игры ⚽ Поможем решить контрольную работу

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Kongruenz — (lateinisch congruentia „Übereinstimmung“) steht für: Mathematik: Kongruenz (Geometrie), in der Geometrie die Deckungsgleichheit von Punktmengen Kongruenz (Zahlentheorie), in der Zahlentheorie die Eigenschaft zweier Zahlen, denselben Rest… …   Deutsch Wikipedia

  • Kongruénz — (lat.), in der Geometrie die besondere Beziehung zwischen zwei verschiedenen Figuren, daß die eine, in geeigneter Weise auf die andre gelegt, diese deckt; zwei solche Figuren, wie z. B. zwei Geradenstücke von gleicher Länge oder zwei Winkel von… …   Meyers Großes Konversations-Lexikon

  • Zahlentheorie — Zah|len|the|o|rie 〈f. 19; unz.〉 Teilgebiet der Arithmetik, das die Eigenschaften der Zahlen 1, 2, 3 ... untersucht, wenn sie mithilfe der vier Grundrechenarten miteinander verknüpft werden * * * Zah|len|the|o|rie, die (Math.): Teilgebiet der… …   Universal-Lexikon

  • Elementare Zahlentheorie — Ursprünglich ist die Zahlentheorie (auch: Arithmetik) ein Teilgebiet der Mathematik, das sich allgemein mit den Eigenschaften der ganzen Zahlen und insbesondere mit den Lösungen von Gleichungen in den ganzen Zahlen (Diophantische Gleichung)… …   Deutsch Wikipedia

  • Legendre-Kongruenz — Die Legendre Kongruenz ist ein Begriff aus dem mathematischen Teilgebiet der Zahlentheorie. Es handelt sich um eine Kongruenz, bei der auf beiden Seiten je eine Quadratzahl steht: Diese nach Adrien Marie Legendre benannten Kongruenzen bilden die… …   Deutsch Wikipedia

  • Lineare Kongruenz — Eine lineare Kongruenz bezeichnet in der Zahlentheorie eine Kongruenz der Form . Sei Diese Kongruenz hat genau dann Lösungen, wenn gilt: d | b Sei r eine spezielle Lösung, dann besteht die Lösungsmenge aus d verschiedenen Kongruenzklassen. Die x… …   Deutsch Wikipedia

  • Simultane Kongruenz — Eine simultane Kongruenz bezeichnet in der Zahlentheorie ein System von linearen Kongruenzen für die alle x bestimmt werden sollen, die sämtliche Kongruenzen gleichzeitig lösen. Es kann, aber muss keine eindeutige Lösung geben. Simultane… …   Deutsch Wikipedia

  • Kongruent — Kongruenz steht für: in der Geometrie die Deckungsgleichheit von Punktmengen, siehe Kongruenz (Geometrie) in der Dreiecksgeometrie speziell, siehe Kongruenzsatz in der Zahlentheorie, dass zwei Zahlen denselben Rest bezüglich eines Divisors haben …   Deutsch Wikipedia

  • Auflösbar — In diesem Glossar werden kurze Erklärungen mathematischer Attribute gesammelt. Unter einem Attribut wird eine Eigenschaft verstanden, die einem mathematischen Objekt zugesprochen wird. Ein Attribut hat oft die Form eines Adjektivs (endlich, offen …   Deutsch Wikipedia

  • Euklidisch — In diesem Glossar werden kurze Erklärungen mathematischer Attribute gesammelt. Unter einem Attribut wird eine Eigenschaft verstanden, die einem mathematischen Objekt zugesprochen wird. Ein Attribut hat oft die Form eines Adjektivs (endlich, offen …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”