Diophantische Gleichung lösen

13.08.2022, 14:04	Dio	Auf diesen Beitrag antworten »
Diophantische Gleichung lösen Hallo, eine Frau kauft für 1,43 Euro Äpfel und Birnen. Ein Apfel kostet 0,15 Euro und eine Birne 0,17 Euro. Wie viel Äpfel und Birnen hat die Frau gekauft? Als Gleichung 15x + 17y = 143 Mit dem erweiterten Euklidischen Algorithmus bekomme ich: 815 -717 = 1 also dann 814315 -714317 = 143, das würde aber auf 1144 Äpfel und -1001 Birnen hinauslaufen Wo ist hier der Fehler?
13.08.2022, 14:19	HAL 9000	Auf diesen Beitrag antworten »
Leider deutest du das Ergebnis des EEA falsch: Der liefert nicht $\begin{eqnarray} x=1144 \end{eqnarray}$ , sondern $\begin{eqnarray} x\equiv 1144\bmod 17 \end{eqnarray}$ , das muss natürlich passend gestutzt werden...
13.08.2022, 14:26	Dio	Auf diesen Beitrag antworten »
Ah, danke dafür!!!
13.08.2022, 16:39	HAL 9000	Auf diesen Beitrag antworten »
Es ist übrigens nicht zwingend notwendig, bei so kleinen Zahlen die ganze EEA-Ochsentour durchzumachen: Ich hätte einfach $\begin{eqnarray} 15x+17y=143 \end{eqnarray}$ modulo 15 unterzogen, das ergibt sofort $\begin{eqnarray} 2y\equiv 8\bmod 15 \end{eqnarray}$ und damit $\begin{eqnarray} y\equiv 4\bmod 15 \end{eqnarray}$ . Mit $\begin{eqnarray} y=4+15k \end{eqnarray}$ ergibt sich rückwärts eingesetzt $\begin{eqnarray} x = \frac{143-17y}{15} = 5-17k \end{eqnarray}$ . Und nur für $\begin{eqnarray} k=0 \end{eqnarray}$ hat man dort dann ein nichtnegatives Lösungspaar $\begin{eqnarray} (x,y) \end{eqnarray}$ .
14.08.2022, 14:05	Dio	Auf diesen Beitrag antworten »
Wie bist du so schnell von $\begin{eqnarray} 2y\equiv 8\bmod 15 \end{eqnarray}$ auf $\begin{eqnarray} y\equiv 4\bmod 15 \end{eqnarray}$ gekommen, welches Gesetz hast du dafür genutzt?
14.08.2022, 14:19	Elvis	Auf diesen Beitrag antworten »
Äquivalenzen kann man oft wie Gleichungen dividieren $\begin{eqnarray} 2y\equiv 8 \mod 15 \; \|\,:2 \end{eqnarray}$ $\begin{eqnarray} y\equiv 4\mod 15 \end{eqnarray}$
Anzeige

14.08.2022, 15:33	HAL 9000	Auf diesen Beitrag antworten »
Allgemein kann man eine Kongruenz $\begin{eqnarray} ay\equiv b\bmod m \end{eqnarray}$ (mit vorausgesetzt teilerfremden $\begin{eqnarray} a,m \end{eqnarray}$ ) so lösen, indem man eine ganze Zahl $\begin{eqnarray} k \end{eqnarray}$ findet, so dass $\begin{eqnarray} b+km \end{eqnarray}$ durch $\begin{eqnarray} a \end{eqnarray}$ teilbar ist. Die Lösung der Kongruenz ist dann natürlich $\begin{eqnarray} y\equiv \frac{b+km}{a}\bmod m \end{eqnarray}$ . Wie findet man nun eine solche Zahl $\begin{eqnarray} k \end{eqnarray}$ ? Nun, bei großem $\begin{eqnarray} a \end{eqnarray}$ durch den EEA - bei kleinen positiven $\begin{eqnarray} a \end{eqnarray}$ kann man aber auch schlicht $\begin{eqnarray} k=0,1,2,\ldots \end{eqnarray}$ durchprobieren, bis man Erfolg hat (was spätestens bei $\begin{eqnarray} k=a-1 \end{eqnarray}$ der Fall ist). Bei $\begin{eqnarray} a=2 \end{eqnarray}$ (wie hier) ist selbst im worst-case die Anzahl der zu probierenden Varianten sehr übersichtlich...

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »