Kongruenzen

29.01.2013, 09:36

Jewels

Kongruenzen

Meine Frage:
Liebes Forum,

gegeben ist folgende Aufgabe:

"Bestimmen Sie die zweitkleinste natürliche Zahl, die beim Teilen durch 4
den Rest 2 lässt, beim Teilen durch 5 den Rest 2, beim Teilen durch 7 den Rest 4 und beim Teilen durch 11 den Rest 8."

Meine Ideen:

Daraus ergeben sich für mich folgende Gleichungen (= kongruent):

x = 2 mod 4
x = 2 mod 5
x = 4 mod 7
x = 8 mod 11

Ich würde nun die letzten drei Gleichungen zusammenfassen als:

x + 3 = 0 mod 358
x = 355 mod 358
x = 355 + 358m

und dann in die erste Gleichung einsetzen

355 + 358m \equiv 2 mod 4

Aber an dieser Stelle komme ich nicht mehr weiter... Ich muss ja irgendwie auf 1m kommen, aber das ist ja nicht möglich, da 2 Teiler von 4 ist. Gibt es noch eine andere Möglichkeit oder habe ich irgendetwas übersehen? Vielleicht die ersten beiden Gleichungen zusammenfassen?

Vielen Dank schon mal im Voraus!
Julia

29.01.2013, 10:04

RavenOnJ

Auf diesen Beitrag antworten »

kennst du den Chinesischen Restsatz?

29.01.2013, 10:25

Jewels

Auf diesen Beitrag antworten »

Ne sagt mir leider nichts...

29.01.2013, 11:17

RavenOnJ

Auf diesen Beitrag antworten »

Das Lösungsverfahren für deine Aufgabe steht im wesentlichen hier.

Deine vier Kongruenzen kann man schreiben als

$\begin{eqnarray*} x \equiv a_i \!\!\!\!\!\mod m_i \end{eqnarray*}$

mit $\begin{align*} a_1 := 2, a_2 := 2,a_3 :=4,a_4 :=8 \end{align*}$ und $\begin{align*} m_1 := 4, m_2 :=5,m_3 :=7,m_4 :=11 \end{align*}$ .

Erst mal kann man sehen, dass die $\begin{align*} m_i \end{align*}$ teilerfremd sind. Das $\begin{align*} kgV(4,5,7,11) \end{align*}$ ist also gleich $\begin{align*} M:= kgV(4,5,7,11) = 4\cdot 5 \cdot 7\cdot 11 = 1540 \end{align*}$ . Wenn man jetzt die Quotienten $\begin{align*} M_i := M/m_i \end{align*}$ bildet, dann haben folgende Gleichungen eine ganzzahlige Lösung:

$\begin{eqnarray*} r_i m_i + s_i M_i = 1, \forall m_i,M_i \end{eqnarray*}$

da die $\begin{align*} m_i \end{align*}$ und $\begin{align*} M_i \end{align*}$ teilerfremd sind. Die $\begin{align*} s_i \end{align*}$ kannst du mit dem erweiterten euklidischen Algorithmus finden. Wenn man nun definiert $\begin{align*} e_i := s_i\cdot M_i \end{align*}$ , dann gilt

$\begin{eqnarray*} e_i \equiv 1 \!\!\!\! \mod m_i \end{eqnarray*}$

$\begin{eqnarray*} e_i \equiv 0 \!\!\!\! \mod m_j, j\ne i \end{eqnarray*}$

Eine Lösung lässt sich also angeben als

$\begin{eqnarray*} x_0 = \sum\limits_1^4 a_i e_i \end{eqnarray*}$

wie du durch Einsetzen in die Kongruenzen feststellen kannst. Ebenfalls sind alle Zahlen der Form

$\begin{eqnarray*} x = x_0 + k M, k\in\mathbb Z \end{eqnarray*}$

auch Lösungen. Diese Zahlen sind die gesamte Lösungsmenge. Davon gilt es dann die zweitkleinste größer Null zu finden.

29.01.2013, 11:23

RavenOnJ

Auf diesen Beitrag antworten »

Das Thema sollte übrigens im Forum "Algebra" stehen.

29.01.2013, 11:39

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Jewels
Ich würde nun die letzten drei Gleichungen zusammenfassen als:

x + 3 = 0 mod 358

Die Idee an sich ist gut, leider hast du dich verrechnet beim Produkt der drei Zahlen 5,7,11: Tatsächlich ist

$\begin{eqnarray*} x+3 \equiv 0 \bmod {\color{red} 385} \end{eqnarray*}$

$\begin{eqnarray*} x \equiv 382 \bmod 385 \end{eqnarray*}$ , also $\begin{eqnarray*} x = 382+385m \end{eqnarray*}$

und dies in $\begin{eqnarray*} x\equiv 2\bmod 4 \end{eqnarray*}$ eingesetzt, ergibt tatsächlich einen raschen Weg zur Lösung.

Natürlich gibt es nicht immer einen derartig schnellen Bypass, so dass es nicht verkehrt ist, sich das von RavenOnJ dargestellte allgemeine Verfahren anzusehen bzw. anzueignen.

29.01.2013, 12:13

Jewels

Auf diesen Beitrag antworten »

Ich zerbreche mir den Kopf und dabei ist nur ein doofer Zahlendreher drin.. statt 385, habe ich mit 358 gerechnet arghh Hammer

Tausend dank smile

So komme ich auf das richtige Ergebnis Augenzwinkern

29.01.2013, 12:17

RavenOnJ

Auf diesen Beitrag antworten »

aber wie HAL schon sagte: Die einfache Lösbarkeit hier ist nur der speziellen Aufgabenstellung zu verdanken. Du solltest auch das allgemeine Vefahren lernen, sonst weißt du nicht mehr weiter, wenn dann mal so ein "bypass" fehlt.

Neue Frage »

Antworten »

Kongruenzen

Verwandte Themen