Zum Inhalt springen
L

Wikipedia · einfach zusammengefasst · Stand

Kongruenz (Zahlentheorie)

Dieser Artikel behandelt die Kongruenz bezüglich der Division mit Rest. Zur Kongruenz bezüglich des Flächeninhalts siehe Kongruente Zahl. Die Kongruenz ist …

Lesen · 5 Abschnitte Original auf Wikipedia
Inhalt5 Abschnitte
  1. 1. Grundidee und Definition
  2. 2. Beispiele und Restklassen
  3. 3. Rechnen mit Kongruenzen
  4. 4. Nützliche Folgerungen
  5. 5. Lineare und simultane Kongruenzen

Grundidee und Definition

Die Kongruenz ist eine Beziehung zwischen ganzen Zahlen. Zwei ganze Zahlen a und b heißen modulo m kongruent, wenn sie sich um ein ganzzahliges Vielfaches von m unterscheiden. Für m ≠ 0 gilt gleichwertig: Sie haben bei der Division durch m denselben Rest.

Formal gilt für a, b, m ∈ ℤ und m ≠ 0:

  • a ≡ b (mod m) ⇔ m ∣ (a − b)
  • a ≡ b (mod m) ⇔ ∃ k ∈ ℤ: a = km + b
  • a ≢ b (mod m) ⇔ m ∤ (a − b)

Übliche Schreibweisen sind a ≡ b mod m, a ≡ b (mod m) oder a ≡ₘ b. Der Modul m ist die Zahl, nach der die Kongruenz betrachtet wird. Für m = 0 erzwingt die Kongruenz in ℤ Gleichheit: a ≡ b (mod 0) ⇒ a = b. Die interessanten Standardfälle haben m ≠ 0.

Beispiele und Restklassen

Beispiele zeigen beide gleichwertigen Prüfungen:

  • 11 ≡ 5 (mod 3), weil beide bei Division durch 3 den Rest 2 haben und 11 − 5 = 6 = 2 · 3 gilt.
  • 11 ≢ 5 (mod 4), weil die Reste 3 und 1 verschieden sind und 11 − 5 = 6 nicht durch 4 teilbar ist.
  • −8 ≡ 10 (mod 6), weil beide den Rest 4 haben und die Differenz −18 durch 6 teilbar ist.

Bei negativen Zahlen gilt in der Mathematik die Konvention, dass ein nichtverschwindender Rest dasselbe Vorzeichen wie der Divisor hat. Daher ist −8 : 6 = −2 Rest 4 und nicht −1 Rest −2.

Die Kongruenz modulo m ist eine Äquivalenzrelation: Sie ist reflexiv, symmetrisch und transitiv. Ihre Äquivalenzklassen heißen Restklassen. Die Restklasse, die a enthält, wird mit [a] oder a̅ bezeichnet. Zwei Restklassen sind entweder gleich oder disjunkt; insbesondere gilt [a] = [b] genau dann, wenn a ≡ b (mod m).

Für m ≠ 0 enthält eine Restklasse alle Zahlen mit demselben Divisionsrest. Die Anzahl der Restklassen ist |m|. Für m = 2 gibt es beispielsweise die Restklasse der geraden und die der ungeraden Zahlen. Mit den von ℤ übernommenen Additions- und Multiplikationsregeln bilden die Restklassen den Restklassenring ℤ/mℤ. ℤ/1ℤ ist der Nullring mit nur einem Element.

Rechnen mit Kongruenzen

Seien m ≠ 0, a ≡ a′ (mod m) und b ≡ b′ (mod m). Dann darf man Kongruenzen unter anderem addieren, subtrahieren und multiplizieren:

  • ca ≡ ca′ (mod m)
  • a + b ≡ a′ + b′ (mod m)
  • a − b ≡ a′ − b′ (mod m)
  • ab ≡ a′b′ (mod m)

Für jedes Polynom f ∈ ℤ[X] gilt außerdem f(a) ≡ f(a′) (mod m).

Beim Kürzen ist Vorsicht nötig. Mit dem größten gemeinsamen Teiler ggT gilt:

ca ≡ cb (mod m) ⇔ a ≡ b (mod m/ggT(c,m)).

Ist m eine Primzahl p und p kein Teiler von c, darf man modulo p gewöhnlich kürzen: ca ≡ cb (mod p) ⇔ a ≡ b (mod p). Für jeden Teiler d von m folgt aus a ≡ b (mod m) auch a ≡ b (mod d). Kongruenzen modulo m₁, …, mₖ sind genau dann alle gleichwertig zu einer Kongruenz modulo ihrem kleinsten gemeinsamen Vielfachen m, wenn sie für alle mᵢ gelten.

Für n ∈ ℕ₀ gilt aⁿ ≡ (a′)ⁿ (mod m). Sind a und m teilerfremd, liefert der Satz von Euler aᵠ(m) ≡ 1 (mod m); daraus folgt aⁿ ≡ aⁿ′ (mod m), falls n ≡ n′ (mod φ(m)). Der kleine fermatsche Satz ist der Spezialfall aᵖ ≡ a (mod p) für jede Primzahl p.

Nützliche Folgerungen

Aus den Rechenregeln folgen unter anderem:

  • Für t ≠ 0 gilt t · a ≡ t · b (mod |t| · m).
  • Ist k ein Teiler von m, dann folgt aus a ≡ b (mod m), dass a ≡ b (mod k) gilt.
  • Für jede ungerade Zahl a gilt a² ≡ 1 (mod 8).
  • Für jede ganze Zahl ist a³ modulo 9 gleich 0, 1 oder 8; modulo 7 gleich 0, 1 oder 6.
  • Für jede ganze Zahl gilt a³ ≡ a (mod 6).
  • Für jede ganze Zahl ist a⁴ modulo 5 gleich 0 oder 1.
  • Ist a zugleich Quadratzahl und Kubikzahl, gilt modulo 36: a ≡ 0, 1, 9 oder 28.
  • Für eine Primzahl p mit n < p < 2n gilt (2n über n) ≡ 0 (mod p).
  • Für eine ungerade ganze Zahl a und n > 0 gilt a²ⁿ ≡ 1 (mod 2ⁿ⁺²).
  • Sind p und q = p + 2 Primzahlzwillinge mit p > 3, dann gilt p · q ≡ −1 (mod 9).

Lineare und simultane Kongruenzen

Eine lineare Kongruenz ax ≡ c (mod m) ist genau dann lösbar, wenn g = ggT(a,m) die Zahl c teilt. In diesem Fall gibt es genau g Lösungen im Bereich {0, 1, …, m − 1}; sie sind untereinander modulo m/g kongruent.

Der erweiterte euklidische Algorithmus bestimmt g sowie s und t mit g = s · a + t · m. Eine Lösung ist dann x₁ = s · c/g. Alle weiteren Lösungen unterscheiden sich von x₁ um ein Vielfaches von m/g.

Beispiel: 4x ≡ 10 (mod 18) ist lösbar, weil ggT(4,18) = 2 die 10 teilt. Der erweiterte euklidische Algorithmus liefert 2 = −4 · 4 + 1 · 18 und damit x₁ = (−4 · 10)/2 = −20. Die Lösungen sind modulo 18 die zwei Klassen; als ganze Zahlen lautet die Lösungsmenge {…, −20, −11, −2, 7, 16, 25, …}.

Bei simultanen Kongruenzen, etwa aᵢx ≡ cᵢ (mod mᵢ), ist eine Lösung sicher vorhanden, wenn jede einzelne Kongruenz lösbar ist, also ggT(aᵢ,mᵢ) cᵢ teilt, und die Zahlen mᵢ/ggT(aᵢ,mᵢ) paarweise teilerfremd sind. Der Chinesische Restsatz liefert den Lösungsweg.

Lernvideos zu Kongruenz (Zahlentheorie)

2:32 Kongruenz - Was ist kongruent? | Mathematik | Lehrerschmidt Lehrerschmidt · 208.760 Aufrufe 10:17 Die KNG-KONGRUENZ (KNG-Regel) einfach erklärt! // LATEIN mit LANGUAID Languaid - deine Sprachenhilfe · 19.307 Aufrufe 13:27 Positionen im Feldermodell - Valenz - Kongruenz - finite / infinite Verben - Ergänzung / Angabe Sprakuko - Deutsch lernen · 16.523 Aufrufe 5:06 Kongruenz von Dreiecken mathemagazin · 14.751 Aufrufe

Weiterlesen

Kongruente Zahl In der Zahlentheorie sind kongruente Zahlen ganze Zahlen, welche sich als Flächeninhalt eines rechtwinkligen Dreiecks mit rationalen Seitenlängen darstellen … Ganze Zahl Die ganzen Zahlen (auch Ganzzahlen, lateinisch numeri integri) sind eine Erweiterung der natürlichen Zahlen. ℤ. Der Buchstabe Z mit Doppelstrich Division mit Rest Die Division mit Rest ist auch für Polynome definiert. Die allgemeinste mathematische Struktur, in der es eine Division mit Rest gibt, ist der euklidische Ring. Kongruenzrelation In der Mathematik, genauer der Algebra, nennt man eine Äquivalenzrelation auf einer algebraischen Struktur eine Kongruenzrelation, wenn die fundamentalen … Gleichheit (Mathematik) Verwendet man die mathematische Formelsprache, heißen solche „Bezeichnungen und Beschreibungen“ Terme. Welches Objekt mit einem Term gemeint ist, ist vom … Integer (Datentyp) Als grundlegender arithmetischer Datentyp werden Ganzzahlen von der Hardware fast aller Rechenanlagen nativ unterstützt und sind in nahezu jeder … Gleichheitszeichen Das Gleichheitszeichen (=, auch Ist-gleich-Zeichen genannt) steht in der Mathematik, der formalen Logik und in den exakten Naturwissenschaften zwischen zwei … Gleichung Unter einer Gleichung versteht man in der Mathematik eine Aussage über die Gleichheit zweier Terme, die mit Hilfe des Gleichheitszeichens („=“) symbolisiert … Carl Friedrich Gauß Gauß-Newton-Verfahren, ein Verfahren zur Lösung nichtlinearer Gleichungen; Gauß-Seidel-Verfahren, ein Verfahren zur Lösung von linearen Gleichungssystemen … Leonhard Euler Mit Leonhard Eulers Namen verbunden sind in Mathematik und Naturwissenschaften eine Reihe von wichtigen Zahlen. Dazu zählen nicht zuletzt die Eulersche Zahl … Teilbarkeit Teilbarkeitsregeln für die Zahlen von 1 bis 20 · 1, immer teilbar · 2, Die letzte Ziffer ist eine 0, 2, 4, 6 oder 8, d. · 3, Die Quersumme ist durch 3 teilbar. Äquivalenzrelation Unter einer Äquivalenzrelation versteht man in der Mathematik eine zweistellige Relation, die reflexiv, symmetrisch und transitiv ist.