Gleichungsproblem < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Gegeben ist die Gleichung 8x+9y=425. Frage: Wie findet man heraus, ob es (eine) ganzzahlige Lösung dieser Gleichung gibt (x und y element N), ohne alle in Frage kommenden Lösungen auszuprobieren? |
Hintergrund: Eine Bekannte hat Hefte in der Schule für 8 bzw. 9 Euro bestellt. Die Summe ist 425 Euro. Die Frage ist: Hat derjenige, der die Summe ermittelt hat, einen Fehler gemacht. Wie kann man das prüfen, ohne alles auszuprobieren? Ich dachte erst, das kann ja nicht so schwer sein, das war vor 6 Stunden grübeln....
Ich bin sehr gespannt auf eure Antworten!
Robert
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:32 Fr 29.09.2006 | | Autor: | M.Rex |
> Gegeben ist die Gleichung 8x+9y=425. Frage: Wie findet man
> heraus, ob es (eine) ganzzahlige Lösung dieser Gleichung
> gibt (x und y element N), ohne alle in Frage kommenden
> Lösungen auszuprobieren?
> Hintergrund: Eine Bekannte hat Hefte in der Schule für 8
> bzw. 9 Euro bestellt. Die Summe ist 425 Euro. Die Frage
> ist: Hat derjenige, der die Summe ermittelt hat, einen
> Fehler gemacht. Wie kann man das prüfen, ohne alles
> auszuprobieren? Ich dachte erst, das kann ja nicht so
> schwer sein, das war vor 6 Stunden grübeln....
> Ich bin sehr gespannt auf eure Antworten!
> Robert
Hallo und ![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
Ich glaube, das kann man relativ schnell prüfen. Wenn 8 und 9 Teiler von 425 wären, was ja bei 8 definitiv nicht der Fall ist, gäbe es ganzzahlige Lösungspaare [mm] \{x,y|x\in\IZ, y\in\IZ\}.
[/mm]
Sonst versuche das Ganze doch grafisch zu lösen. (ist zwar nicht sehr elegant, hilft aber manchmal)
Dazu forme deine Gelichung mal um zu [mm] y=\bruch{425}{9}-\bruch{8}{9}x [/mm] und zeichne diese Gerade in ein geeignetes Koordinatensystem ein, wobei das in diesem Fall sehr schwierig werden könnte
[Dateianhang nicht öffentlich]
gezeichnet per Funkyplot
Marius
Edit: Wie den Raktionen auf meinen Beitrag zu entnehmen ist, muss nur der ggT von 8 und 9 Teiler von 425 sein
Marius
Dateianhänge:
Anhang Nr. 1 (Typ: jpeg) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:21 Fr 29.09.2006 | | Autor: | robert170 |
Hallo Marius,
das hatte ich auch erst gedacht, aber 8 und 9 sind keine Teiler von 98, trotzdem ist 10*9+1*8=98 eine ganzzahlige Lösung von 98...
Die grafische Lösung ist schon ein guter Ansatz, man erkennt, dass x und y 25 sind, eine mathematische Lösung wäre halt noch eleganter.....
Gruß
Robert
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:37 Fr 29.09.2006 | | Autor: | felixf |
Hallo,
ohne mir alles genau durchgelesen zu haben:
> das hatte ich auch erst gedacht, aber 8 und 9 sind keine
> Teiler von 98, trotzdem ist 10*9+1*8=98 eine ganzzahlige
> Lösung von 98...
es muss ja auch nur der ggT von 8 und 9 ein Teiler von 98 sein.
LG Felix
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:18 Fr 29.09.2006 | | Autor: | felbec |
Moin! Moin!
Eine ganzzahlige Lsg. ist z.B. x=y=25.
Andere Lösungen Element N für x*8+y*9=425 ergeben sich mit x=7, x=16, x=34, x=43 und x=52.
425 ist modulo 9 Element der Restklasse 2.
Also bleibt 8x=2 (mod9), was entweder durch ausprobieren, oder mit Hilfe des Beweises zum g.g.T. geschehen kann (Lsg. x ist Element von (7+z*9 | z Element der ganzen Zahlen))
|
|
|
| |
|
hallo felbec,
danke für die Antwort, könntest Du den letzten Absatz noch etwas erläutern, meine Zeit an der Uni liegt schon etwas zurück und leider habe ich als Physiker keine Zahlentheorie belegt... Danke!
robert
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:03 Sa 30.09.2006 | | Autor: | felbec |
moin! moin!
wenn's dringend ist musst du mal unter "euklidischer algorithmus" nachgucken.
schönes wochenende,
felbec.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:21 Fr 29.09.2006 | | Autor: | riwe |
schau mal hier unter
![[]](/images/popup.gif) diophant
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 05:23 Mi 04.10.2006 | | Autor: | felixf |
Hallo!
> schau mal hier unter
> diophant
Etwas ausfuehrlicher (IMO) wird es hier beschrieben (da gibts auch noch Links zu weiteren Informationsquellen).
Jedoch loest das nicht ganz das Problem des OP. Er sucht ja nach natuerlichen Loesungen und nicht nur nach ganzzahligen Loesungen.
Er hat also eine Gleichung $a x + b y = c$ mit $a, b, c [mm] \in \IZ$ [/mm] konstant, und moechte wissen ob es Loesungen $(x, y) [mm] \in \IN^2$ [/mm] gibt. Dazu geht man wie folgt vor:
* Berechne $g := ggT(a, b)$.
* Ist $g$ kein Teiler von $c$, so hat die Gleichung keine ganzzahligen und somit insbesondere keine natuerlichen Loesungen.
* Andernfalls schreibe $a [mm] \lambda [/mm] + b [mm] \mu [/mm] = g$ mit ganzen Zahlen [mm] $\lambda, \mu \in \IZ$ [/mm] (erweiterter euklidischer Algorithmus).
* Damit ist $a [mm] (\lambda \frac{c}{g}) [/mm] + b [mm] (\mu \frac{c}{g}) [/mm] = [mm] \frac{c}{g} [/mm] (a [mm] \lambda [/mm] + b [mm] \mu) [/mm] = c$, womit [mm] $(\lambda \frac{c}{g}, \mu \frac{c}{g})$ [/mm] eine ganzzahlige Loesung ist.
* Die Gesamtheit aller ganzzahligen Loesungen ist also [mm] $\{ (\lambda \frac{c}{g} + t \frac{b}{g}, \mu \frac{c}{g} - t \frac{a}{g}) \mid t \in \IZ \}$.
[/mm]
* Damit eine solche zu $t$ gehoerende Loesung natuerlich ist, muss also [mm] $\lambda \frac{c}{g} [/mm] + t [mm] \frac{b}{g} \ge [/mm] 0$ und [mm] $\mu \frac{c}{g} [/mm] - t [mm] \frac{a}{g} \ge [/mm] 0$ sein. (Oder $> 0$ falls man $0$ nicht als natuerliche Zahl ansieht). Das kann man sehr leicht umformen und somit kann man sofort sehen, ob es natuerliche Loesungen gibt oder nicht (und man kann sie damit auch alle ganz einfach aufzaehlen).
LG Felix
|
|
|
| |
|
Hallo Robert,
> Gegeben ist die Gleichung 8x+9y=425. Frage: Wie findet man
> heraus, ob es (eine) ganzzahlige Lösung dieser Gleichung
> gibt (x und y element N), ohne alle in Frage kommenden
> Lösungen auszuprobieren?
> Hintergrund: Eine Bekannte hat Hefte in der Schule für 8
> bzw. 9 Euro bestellt. Die Summe ist 425 Euro. Die Frage
> ist: Hat derjenige, der die Summe ermittelt hat, einen
> Fehler gemacht. Wie kann man das prüfen, ohne alles
> auszuprobieren? Ich dachte erst, das kann ja nicht so
> schwer sein, das war vor 6 Stunden grübeln....
Ich hatte das mal als Übungsaufgabe:
Sind a,b teilerfremde natürliche Zahlen, dann gibt es zu jeder natürlichen Zahl m mit m>ab natürliche Zahlen x,y mit ax+by=m.
Zwei Zahlen a,b sind teilerfremd, wenn die größtmögliche natürliche Zahl d, die a und b teilt, 1 ist.
Wäre der Bestellwert aber z.B. 70 Euro gewesen, dann wär' da ein Fehler drin - die Gleichung 8x+9y=70 hat keine Lösung in natürlichen Zahlen.
Mfg
zahlenspieler
|
|
|
|
