Lineare Kongruenz

Lineare Kongruenz

Eine lineare Kongruenz bezeichnet in der Zahlentheorie eine Kongruenz der Form

ax \equiv b \mod m.

Sei

\operatorname{ggT}(a,m)=d

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 besitzen dann die Darstellung

x = r + t*m/d, t \in \mathbb{Z}

Beispiel

Gesucht sind alle Lösungen der linearen Kongruenz

6x \equiv 3 \mod 27.

eine spezielle Lösung findet man durch Ausprobieren und lautet r = 14.

Da \operatorname{ggT}(6,27)=3, gibt es drei verschiedene Lösungen modulo 27 und somit drei Äquivalenzklassen, nämlich


\left[ {14} \right]_{27} ,\left[ {14 - 9} \right]_{27}  = \left[ 5 \right]_{27} ,\left[ {14 + 9} \right]_{27}  = \left[ {23} \right]_{27}

Alternativ kann man auch die Rechenregeln für Kongruenzen ausnutzen um somit schneller eine Lösung zu finden:


 6x \equiv 3 \mod 27
  \Leftrightarrow 2x \equiv 1 \mod 9
  \Leftrightarrow_{\operatorname{ggT}(9,2) = 1} x \equiv 5 \mod 9

indem man die Gleichung zuerst mit dem Inversen von 3 multipliziert (hierbei verändert sich ebenfalls der Modul, da der \operatorname{ggT}(27,3)=3\ne 1 und dann mit dem Inversen von 2 multipliziert. Als Äquivalenzklasse der Lösungen erhält man dann

\left[ {5} \right]_9

Wikimedia Foundation.

Игры ⚽ Поможем написать курсовую

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

  • 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 …   Deutsch Wikipedia

  • Kongruenz (Matrix) — In der Linearen Algebra, einem Teilgebiet der Mathematik, nennt man zwei quadratische Matrizen A und B kongruent, wenn es eine invertierbare Matrix P gibt, sodass: B = PTAP. Dabei bedeutet PT die zu P transponierte Matrix. Die Kongruenz von… …   Deutsch Wikipedia

  • Liniengeometrie — Liniengeometrie, die Geometrie der Liniensysteme im Raum. Eine Gleichung n ter Ordnung in Linienkoordinaten (s. Koordinaten) f (p, q, r, π, κ, ρ) = 0 stellt ∞3 Gerade im Raum, einen Komplex oder Linienkomplex n ter… …   Lexikon der gesamten Technik

  • Index-Calculus-Algorithmus — Der Index Calculus Algorithmus ist ein Algorithmus zur Berechnung des diskreten Logarithmus. x = log αβ Vorgehensweise Es sei G eine endliche zyklische Gruppe der Ordnung n, die durch α erzeugt wird. Es sei S = p1,p2,...,pt(die Faktorbasis)… …   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

  • Fehlstand — 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

  • Integrabel — 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

  • Kollinear — 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

  • Kopunktal — 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”