Summe von Kehrwerten

[Arne 'Timwi' Heizmann]

Hallo,

jede rationale Zahl läßt sich als Summe von Kehrwerten schreiben, z.B.:

47/60 = 1/2 + 1/4 + 1/30 (3 Terme)
47/70 = 1/2 + 1/7 + 1/35 (3 Terme)

Manchmal treten Kehrwerte mit großen Nennern auf, selbst wenn die
ursprüngliche Zahl keine solch großen Zahlen hatte:

42/47 = 1/2 + 1/3 + 1/17 + 1/690 + 1/91885 (5 Terme)

Manchmal gibt es mehrere Möglichkeiten, z.B.:

511/512 = 1/2 + 1/3 + 1/7 + 1/46 + 1/8528 + 1/131808768
511/512 = 1/2 + 1/4 + 1/8 + 1/16 + 1/32 + 1/64 + 1/128 + 1/256 + 1/512

Die erste Folge habe ich erstellt, indem ich immer den größten Kehrwert
nehme, der noch in die Zahl reinpasst, und solange subtrahiere, bis ein
Kehrwert rauskommt.

Frage: Ist dieser Algorithmus optimal, d.h. kriegt man dadurch immer die
geringste Anzahl von Termen?

Wenn nicht, wie würde ein Algorithmus aussehen, der dieses Optimum
bewerkstelligt?

Danke,
Timwi

[David Kastrup]

Post by Arne 'Timwi' Heizmann
47/60 = 1/2 + 1/4 + 1/30 (3 Terme)
47/70 = 1/2 + 1/7 + 1/35 (3 Terme)
Manchmal treten Kehrwerte mit großen Nennern auf, selbst wenn die
42/47 = 1/2 + 1/3 + 1/17 + 1/690 + 1/91885 (5 Terme)
511/512 = 1/2 + 1/3 + 1/7 + 1/46 + 1/8528 + 1/131808768
511/512 = 1/2 + 1/4 + 1/8 + 1/16 + 1/32 + 1/64 + 1/128 + 1/256 + 1/512
Die erste Folge habe ich erstellt, indem ich immer den größten
Kehrwert nehme, der noch in die Zahl reinpasst, und solange
subtrahiere, bis ein Kehrwert rauskommt.
Frage: Ist dieser Algorithmus optimal, d.h. kriegt man dadurch immer
die geringste Anzahl von Termen?

79:120 = 1:3 + 1:5 + 1:8
= 1:2 + 1:7 + 1:65 + 1:10920

Post by Arne 'Timwi' Heizmann
Wenn nicht, wie würde ein Algorithmus aussehen, der dieses Optimum
bewerkstelligt?

Knifflig.

[Markus Sigg]

Post by Arne 'Timwi' Heizmann
Hallo,
...

Wenn Du den Begriff "Kehrwert" vergißt und statt dessen nach "Stammbruch"
forschst, wirst Du sicher einige Antworten auf Deine Fragen finden.

Gruß,
Markus

[Jutta Gut]

Post by Arne 'Timwi' Heizmann
47/60 = 1/2 + 1/4 + 1/30 (3 Terme)
47/70 = 1/2 + 1/7 + 1/35 (3 Terme)

(...)

Post by Arne 'Timwi' Heizmann
Frage: Ist dieser Algorithmus optimal, d.h. kriegt man dadurch immer die
geringste Anzahl von Termen?
Wenn nicht, wie würde ein Algorithmus aussehen, der dieses Optimum
bewerkstelligt?

Keine Ahnung, aber die alten Ägypter haben Brüche so dargestellt. Vielleicht
findest du ja etwas unter dem Stichwort "Ägyptische Mathematik".

Grüße
Jutta

[Rainer Rosenthal]

Post by Arne 'Timwi' Heizmann
47/60 = 1/2 + 1/4 + 1/30 (3 Terme)
47/70 = 1/2 + 1/7 + 1/35 (3 Terme)

Kapitel D11 in UPINT = Unsolved Problems in Number Theory
von Richard K. Guy gibt eine Übersicht mit vielen inter-
essanten Fragestellungen und Literatur zu den
"Egyptian Fractions".

Du wirst dies Buch mögen.

Gruss,
Rainer Rosenthal
***@web.de

[Wolfgang Kirschenhofer]

"Arne 'Timwi' Heizmann" <***@gmx.net> schrieb im Newsbeitrag news:***@individual.net...
|
| Hallo,
|
| jede rationale Zahl läßt sich als Summe von Kehrwerten schreiben,
z.B.:
|
| 47/60 = 1/2 + 1/4 + 1/30 (3 Terme)
| 47/70 = 1/2 + 1/7 + 1/35 (3 Terme)
|
| Manchmal treten Kehrwerte mit großen Nennern auf, selbst wenn die
| ursprüngliche Zahl keine solch großen Zahlen hatte:
|
| 42/47 = 1/2 + 1/3 + 1/17 + 1/690 + 1/91885 (5 Terme)
|
| Manchmal gibt es mehrere Möglichkeiten, z.B.:
|
| 511/512 = 1/2 + 1/3 + 1/7 + 1/46 + 1/8528 + 1/131808768
| 511/512 = 1/2 + 1/4 + 1/8 + 1/16 + 1/32 + 1/64 + 1/128 + 1/256 +
1/512
|
| Die erste Folge habe ich erstellt, indem ich immer den größten
Kehrwert
| nehme, der noch in die Zahl reinpasst, und solange subtrahiere, bis
ein
| Kehrwert rauskommt.
|
| Frage: Ist dieser Algorithmus optimal, d.h. kriegt man dadurch immer
die
| geringste Anzahl von Termen?
|
| Wenn nicht, wie würde ein Algorithmus aussehen, der dieses Optimum
| bewerkstelligt?
|
| Danke,
| Timwi

Hallo Timwi!

Man nennt die Brüche mit dem Zähler 1 und Nenner >1 Stammbrüche oder
auch Ägyptische Brüche.
Der Algorithmus, den du verwendet hast, wird in der Fachliteratur
"Greedy Algorithmus" genannt. Er ist nicht optimal in deinem Sinn.
Es gibt zwar "bessere" Algorithmen als den Greedy-Algorithmus, aber
vermutlich keinen optimalen.
Auch Erdös hat sich mit Ägyptischen Brüchen befaßt.
Da ich jetzt zu Bett gehe, werde ich dir erst morgen mehr dazu sagen
und zwar auch zur Vermutung von Erdös und Strauss.
Abschließend noch das folgende Beispiel:
4/5 = 1/2 + 1/4 + 1/20 , nur drei Summanden,gefunden mit Hilfe des
Greedy-Algorithmus.

Grüße,
Wolfgang Kirschenhofer

[Wolfgang Kirschenhofer]

"Wolfgang Kirschenhofer" <***@kstp.at> schrieb im Newsbeitrag news:***@news.aic.at...
|
| "Arne 'Timwi' Heizmann" <***@gmx.net> schrieb im Newsbeitrag
| news:***@individual.net...
| |
| | Hallo,
| |
| | jede rationale Zahl läßt sich als Summe von Kehrwerten schreiben,
| z.B.:
| |
| | 47/60 = 1/2 + 1/4 + 1/30 (3 Terme)
| | 47/70 = 1/2 + 1/7 + 1/35 (3 Terme)
| |
| | Manchmal treten Kehrwerte mit großen Nennern auf, selbst wenn die
| | ursprüngliche Zahl keine solch großen Zahlen hatte:
| |
| | 42/47 = 1/2 + 1/3 + 1/17 + 1/690 + 1/91885 (5 Terme)
| |
| | Manchmal gibt es mehrere Möglichkeiten, z.B.:
| |
| | 511/512 = 1/2 + 1/3 + 1/7 + 1/46 + 1/8528 + 1/131808768
| | 511/512 = 1/2 + 1/4 + 1/8 + 1/16 + 1/32 + 1/64 + 1/128 + 1/256 +
| 1/512
| |
| | Die erste Folge habe ich erstellt, indem ich immer den größten
| Kehrwert
| | nehme, der noch in die Zahl reinpasst, und solange subtrahiere, bis
| ein
| | Kehrwert rauskommt.
| |
| | Frage: Ist dieser Algorithmus optimal, d.h. kriegt man dadurch
immer
| die
| | geringste Anzahl von Termen?
| |
| | Wenn nicht, wie würde ein Algorithmus aussehen, der dieses Optimum
| | bewerkstelligt?
| |
| | Danke,
| | Timwi
|
| Hallo Timwi!
|
| Man nennt die Brüche mit dem Zähler 1 und Nenner >1 Stammbrüche oder
| auch Ägyptische Brüche.
| Der Algorithmus, den du verwendet hast, wird in der Fachliteratur
| "Greedy Algorithmus" genannt. Er ist nicht optimal in deinem Sinn.
| Es gibt zwar "bessere" Algorithmen als den Greedy-Algorithmus, aber
| vermutlich keinen optimalen.
| Auch Erdös hat sich mit Ägyptischen Brüchen befaßt.
| Da ich jetzt zu Bett gehe, werde ich dir erst morgen mehr dazu sagen
| und zwar auch zur Vermutung von Erdös und Strauss.
| Abschließend noch das folgende Beispiel:
| 4/5 = 1/2 + 1/4 + 1/20 , nur drei Summanden,gefunden mit Hilfe des
| Greedy-Algorithmus.
|
| Grüße,
| Wolfgang Kirschenhofer
|

Hallo Timwi!

Nun habe ich wieder Zeit und kann dir weitere Tips geben.
1.)Wenn du in GOOGLE das Stichwort "Egyptian Fractions"
eingibst, erhälts du eine Fülle von Links zum Thema.

Besonders hinweisen möchte ich auf

http://www.ics.uci.edu/~eppstein/numth/egypt/intro.html
Hier findet man 7 verschiedene Algorithmen für ägyptische Brüche
einschließlich des "Greedy Algorithmus".

Und auf

http://kevingong.com/Math/EgyptianFractions.pdf

Dies ist ein 80-seitiges PDF-File mit Algorithmen.
In diesem PDF-File findet man auch einen Algorithmus von Erdös.

http://math.uindy.edu/swett/esc.htm

ist ein Artikel zur Erdös- Strauss-Vermutung

2.)Die Vermutung von Erdös-Strauss:

Für jede natürliche Zahl n>=3 ist die folgende Gleichung

4/n = 1/a + 1/b +1/c in ganzen Zahlen a, b, c mit 1<=a < b < c
lösbar.

Mit dem Computer wurde die Vermutung für 3<=n<=10^14 bestätigt.

Beispiele dazu: 4/3 = 1 +1/4 +1/12 , 4/4 = 1/2 + 1/3 +1/6 , 4/5 = 1/2 +
1/4 +1/20 ,

4/6 = 1/3 + 1/4 +1/12 , 4/7 = 1/3+1/6+1/14 .

3.) Zwei Fragen zum Nachdenken und zum Beantworten:

Man zeige, daß sich die Zahl 1 auch als Summe von verschiedenen
Stammbrüchen schreiben läßt, die nur ungerade Nenner haben.
Aus wieviel Summanden muß eine derartige Darstellung zumindest bestehen
?
Man gebe eine derartige Darstellung mit dieser minimalen Summandenzahl
an.

4.)Historisches:
Das "greedy" ("gierige") Verfahren geht auf FIBONACCI und SYLVESTER
zurück.

Historisch bedeutsam sind die Stammbruchdarstellungen durch ihre
Überlieferung
am Papyrus Rhind (im British Museum). Warum die dort zu findenden
derartigen
Zerlegungen der Brüche 2/n (mit n<=101 und n ungerade) in Stammbrüche
mit
verschiedenen Nennern für die Ägypter bedeutsam waren, scheint bis
heute ungeklärt.

Interessant ist auch ein Darstellungssatz aus der Dissertation von RON
GRAHAM.
Weiteres dazu nur auf Anfrage.

Grüße,
Wolfgang Kirschenhofer

[Klaus-R. Loeffler]

Wolfgang Kirschenhofer <***@kstp.at> wrote:

[...]

Post by Wolfgang Kirschenhofer
Für jede natürliche Zahl n>=3 ist die folgende Gleichung
4/n = 1/a + 1/b +1/c in ganzen Zahlen a, b, c mit 1<=a < b < c
lösbar.
Mit dem Computer wurde die Vermutung für 3<=n<=10^14 bestätigt.
Beispiele dazu: 4/3 = 1 +1/4 +1/12 , 4/4 = 1/2 + 1/3 +1/6 , 4/5 = 1/2 +
1/4 +1/20 ,
4/6 = 1/3 + 1/4 +1/12 , 4/7 = 1/3+1/6+1/14 .

[...]

Kleine Bemerkung anlässlich der erwähnten Vermutung von Erdös-Strauss
zur Darstellbarkeit von Zahlen des Typs 4/n - hier mit zwei Summanden:

Im Bundeswettbewerb Mathematik wurde 1989 (4. Aufgabe der ersten Runde)
der Nachweis folgender Aussage für n aus N verlangt:
Die Gleichung 4/n = 1/x + 1/y hat genau dann Lösungen in NxN, wenn n
bei Division durch 4 den Rest 3 lässt.

Klaus-R.

[Ingrid Voigt]

Post by Klaus-R. Loeffler
Kleine Bemerkung anlässlich der erwähnten Vermutung von Erdös-Strauss
Im Bundeswettbewerb Mathematik wurde 1989 (4. Aufgabe der ersten Runde)
Die Gleichung 4/n = 1/x + 1/y hat genau dann Lösungen in NxN, wenn n
bei Division durch 4 den Rest 3 lässt.

Das kann so nicht ganz stimmen.

4/2 = 1/1 + 1/1
4/4 = 1/2 + 1/2
4/7 = 1/2 + 1/14
4/9 = 1/3 + 1/9

(n mod 4) hat offenbar nichts damit zu tun.

Viele Grüße
Ingrid

[Klaus-R. Loeffler]

Post by Ingrid Voigt

Post by Klaus-R. Loeffler
Kleine Bemerkung anlässlich der erwähnten Vermutung von Erdös-Strauss
Im Bundeswettbewerb Mathematik wurde 1989 (4. Aufgabe der ersten Runde)
Die Gleichung 4/n = 1/x + 1/y hat genau dann Lösungen in NxN, wenn n
bei Division durch 4 den Rest 3 lässt.

Das kann so nicht ganz stimmen.
4/2 = 1/1 + 1/1
4/4 = 1/2 + 1/2
4/7 = 1/2 + 1/14
4/9 = 1/3 + 1/9
(n mod 4) hat offenbar nichts damit zu tun.
Viele Grüße
Ingrid

Hallo Ingrid,

du hast recht; ich hatte die Aufgabe nicht genau im Kopf. Die Aussage
gilt für _ungerade_ natürliche Zahlen und es muss heißen "wenn n einen
Teiler mit Viererrest 3 besitzt".
Sorry und Dank für die Aufmerksamkeit. Man sollte halt im Alter nicht
mehr ungeprüft aus dem Gedächtnis zitieren.

Herzl. Gruß
Klaus-R.

[Wolfgang Kirschenhofer]

"Klaus-R. Loeffler" <***@t-online.de> schrieb im Newsbeitrag news:1hksnf9.gqxzuh1jwe3kgN%***@t-online.de...
| Ingrid Voigt <***@gmx.net> wrote:
|
| > Klaus-R. Loeffler wrote:
| >
| > > Kleine Bemerkung anlässlich der erwähnten Vermutung von
Erdös-Strauss
| > > zur Darstellbarkeit von Zahlen des Typs 4/n - hier mit zwei
Summanden:
| > >
| > > Im Bundeswettbewerb Mathematik wurde 1989 (4. Aufgabe der ersten
Runde)
| > > der Nachweis folgender Aussage für n aus N verlangt:
| > > Die Gleichung 4/n = 1/x + 1/y hat genau dann Lösungen in NxN,
wenn n
| > > bei Division durch 4 den Rest 3 lässt.
| >
| > Das kann so nicht ganz stimmen.
| >
| > 4/2 = 1/1 + 1/1
| > 4/4 = 1/2 + 1/2
| > 4/7 = 1/2 + 1/14
| > 4/9 = 1/3 + 1/9
| >
| > (n mod 4) hat offenbar nichts damit zu tun.
| >
| > Viele Grüße
| > Ingrid
|
| Hallo Ingrid,
|
| du hast recht; ich hatte die Aufgabe nicht genau im Kopf. Die Aussage
| gilt für _ungerade_ natürliche Zahlen und es muss heißen "wenn n
einen
| Teiler mit Viererrest 3 besitzt".
| Sorry und Dank für die Aufmerksamkeit. Man sollte halt im Alter nicht
| mehr ungeprüft aus dem Gedächtnis zitieren.
|
| Herzl. Gruß
| Klaus-R.


Hallo !

Danke für die interessanten Hinweise.
Damit keine Mißverständnisse auftreten können, habe ich den
Originaltext der Aufgabe 4 der ersten Runde hierher kopiert:
Aufgabe 4:

Es sei n eine ungerade natürliche Zahl. Man beweise:
Die Gleichung 4/n = 1/x + 1/y hat dann und nur dann eine Lösung (x,y)
mit natürlichen Zahlen x, y, wenn n einen Teiler der Form 4k-1 besitzt
(k Element von N).

Diejenigen in der NG, die wirklich an Mathematik interessiert sind,
könnten diese Aufgabe ja für sich lösen.

Grüße,
Wolfgang Kirschenhofer

[Jirka Klaue]

Post by Wolfgang Kirschenhofer
Die Gleichung 4/n = 1/x + 1/y hat dann und nur dann eine Lösung (x,y)
mit natürlichen Zahlen x, y, wenn n einen Teiler der Form 4k-1 besitzt
(k Element von N).

Kommt mir immer noch komisch vor.

x=1 und y=1 -> 4/n = 2 -> n=2

Wie groß soll jetzt k sein?

Jirka

[Klaus-R. Loeffler]

Post by Jirka Klaue

Post by Wolfgang Kirschenhofer
Die Gleichung 4/n = 1/x + 1/y hat dann und nur dann eine Lösung (x,y)
mit natürlichen Zahlen x, y, wenn n einen Teiler der Form 4k-1 besitzt
(k Element von N).

Kommt mir immer noch komisch vor.
x=1 und y=1 -> 4/n = 2 -> n=2
Wie groß soll jetzt k sein?

Dass n ungerade ist, wird in de Aufgabe vorausgesetzt und ist keineswegs
eine Folgerung aus der Darstellung.

Klaus-R.

[Hermann Jurksch]

Post by Klaus-R. Loeffler

Post by Jirka Klaue

Post by Wolfgang Kirschenhofer
Die Gleichung 4/n = 1/x + 1/y hat dann und nur dann eine Lösung (x,y)
mit natürlichen Zahlen x, y, wenn n einen Teiler der Form 4k-1 besitzt
(k Element von N).

Kommt mir immer noch komisch vor.
x=1 und y=1 -> 4/n = 2 -> n=2
Wie groß soll jetzt k sein?

Dass n ungerade ist, wird in de Aufgabe vorausgesetzt und ist keineswegs
eine Folgerung aus der Darstellung.

Und dann klappt es auch. Sei n ungerade und a und b natürliche Zahlen
mit
4/n = 1/a + 1/b <==> 4*a*b = (a+b)*n

so folgt 4 | a+b. Es gibt also ein natürliches c, so daß

a + b = 4*c und a * b = c * n. Vieta verrät uns, daß dann a und b

Lösungen der quadratischen Gleichung

x^2 - 4*c*x + c*n = 0 ist. Hieraus erhalten wir

(x-2*c)^2 = c*(4*c-n). Sei nun q = ggt(c,4*c-n)=ggt(c,n), dann müssen

c/q und (4*c-n)/q, da teilerfremd, beide Quadratzahlen sein.

Sei also c = q * c'^2 und n = q*n', so erhalten wir

(x-2*c)^2 = q^2*c'^2*(4*c'^2-n'), d.h. 4*c'^2-n' muß Quadratzahl

sein, was, da n' wie n ungerade ist, nur für n' = 3 (mod 4) möglich

ist. Damit muß aber n' und damit n wenigstens einen Primfaktor der

Form 4*k-1 enthalten.

Sei nun umgekehrt n = (4*k-1)*q, dann wähle

a = k*q und b = k*q*(4*k-1).


MfG
Hermann

[Wolfgang Kirschenhofer]

"Hermann Jurksch" <***@elektron-bbs.de> schrieb im Newsbeitrag news:9+laa0oev+***@elektron-bbs.de...
| ***@t-online.de wrote:
|
| > Jirka Klaue <***@dresearch.de> wrote:
|
| >>> Es sei n eine ungerade natürliche Zahl. Man beweise:
| >>> Die Gleichung 4/n = 1/x + 1/y hat dann und nur dann eine Lösung
(x,y)
| >>> mit natürlichen Zahlen x, y, wenn n einen Teiler der Form 4k-1
besitzt
| >>> (k Element von N).
| >>
| >> Kommt mir immer noch komisch vor.
| >>
| >> x=1 und y=1 -> 4/n = 2 -> n=2
| >>
| >> Wie groß soll jetzt k sein?
| >>
| > Dass n ungerade ist, wird in de Aufgabe vorausgesetzt und ist
keineswegs
| > eine Folgerung aus der Darstellung.
|
| Und dann klappt es auch. Sei n ungerade und a und b natürliche Zahlen
| mit
| 4/n = 1/a + 1/b <==> 4*a*b = (a+b)*n
|
| so folgt 4 | a+b. Es gibt also ein natürliches c, so daß
|
| a + b = 4*c und a * b = c * n. Vieta verrät uns, daß dann a und b
|
| Lösungen der quadratischen Gleichung
|
| x^2 - 4*c*x + c*n = 0 ist. Hieraus erhalten wir
|
| (x-2*c)^2 = c*(4*c-n). Sei nun q = ggt(c,4*c-n)=ggt(c,n), dann müssen
|
| c/q und (4*c-n)/q, da teilerfremd, beide Quadratzahlen sein.
|
| Sei also c = q * c'^2 und n = q*n', so erhalten wir
|
| (x-2*c)^2 = q^2*c'^2*(4*c'^2-n'), d.h. 4*c'^2-n' muß Quadratzahl
|
| sein, was, da n' wie n ungerade ist, nur für n' = 3 (mod 4) möglich
|
| ist. Damit muß aber n' und damit n wenigstens einen Primfaktor der
|
| Form 4*k-1 enthalten.
|
| Sei nun umgekehrt n = (4*k-1)*q, dann wähle
|
| a = k*q und b = k*q*(4*k-1).
|
|
| MfG
| Hermann
|

Hallo Hermann! Hallo Klaus-R.!

Der Beweis, den ich kenne, verläuft teilweise etwas anders:
Seien n ungerade und a und b natürliche Zahlen
mit 4/n = 1/a + 1/b und ggT(a,b)=d (1)

dann gilt a=d*u und b=d*v und ggT(u,v)=1 .
Aus (1) folgt dann 4/n = (u+v)/(d*u*v) und daraus weiter
4*u*v*d = n*(u+v) (2)
Aus (2) folgt 4 | (u+v), da n ungerade ist und außerdem
u | n und v | n , da ggT(u,v)=1 ist.
Da (u+v)== 0 (mod 4) ist, muß einer der beiden Teiler u,v von n
in der Restklasse 1 und der andere in der Restklasse -1 (ist gleich
Restklasse 3 mod4) liegen.
n besitzt daher einen Teiler der Form 4*k - 1.
Der Rest des Beweises läuft wörtlich wie bei Hermann (siehe die letzten
beiden Zeilen von Hermanns Beweis).

Ob diese Beweis-Version mit der offiziellen Lösung des Bundesbewerbes
übereinstimmt, weiß ich nicht.
Das müßte eigentlich Klaus-R. wissen.

Mit freundlichen Grüßen,
Wolfgang Kirschenhofer

[Klaus-R. Loeffler]

Post by Wolfgang Kirschenhofer
|
|
| >>> Die Gleichung 4/n = 1/x + 1/y hat dann und nur dann eine Lösung
(x,y)
| >>> mit natürlichen Zahlen x, y, wenn n einen Teiler der Form 4k-1
besitzt
| >>> (k Element von N).
| >>
| >> Kommt mir immer noch komisch vor.
| >>
| >> x=1 und y=1 -> 4/n = 2 -> n=2
| >>
| >> Wie groß soll jetzt k sein?
| >>
| > Dass n ungerade ist, wird in de Aufgabe vorausgesetzt und ist
keineswegs
| > eine Folgerung aus der Darstellung.
|
| Und dann klappt es auch. Sei n ungerade und a und b natürliche Zahlen
| mit
| 4/n = 1/a + 1/b <==> 4*a*b = (a+b)*n
|
| so folgt 4 | a+b. Es gibt also ein natürliches c, so daß
|
| a + b = 4*c und a * b = c * n. Vieta verrät uns, daß dann a und b
|
| Lösungen der quadratischen Gleichung
|
| x^2 - 4*c*x + c*n = 0 ist. Hieraus erhalten wir
|
| (x-2*c)^2 = c*(4*c-n). Sei nun q = ggt(c,4*c-n)=ggt(c,n), dann müssen
|
| c/q und (4*c-n)/q, da teilerfremd, beide Quadratzahlen sein.
|
| Sei also c = q * c'^2 und n = q*n', so erhalten wir
|
| (x-2*c)^2 = q^2*c'^2*(4*c'^2-n'), d.h. 4*c'^2-n' muß Quadratzahl
|
| sein, was, da n' wie n ungerade ist, nur für n' = 3 (mod 4) möglich
|
| ist. Damit muß aber n' und damit n wenigstens einen Primfaktor der
|
| Form 4*k-1 enthalten.
|
| Sei nun umgekehrt n = (4*k-1)*q, dann wähle
|
| a = k*q und b = k*q*(4*k-1).
|
|
| MfG
| Hermann
|
Hallo Hermann! Hallo Klaus-R.!
Seien n ungerade und a und b natürliche Zahlen
mit 4/n = 1/a + 1/b und ggT(a,b)=d (1)
dann gilt a=d*u und b=d*v und ggT(u,v)=1 .
Aus (1) folgt dann 4/n = (u+v)/(d*u*v) und daraus weiter
4*u*v*d = n*(u+v) (2)
Aus (2) folgt 4 | (u+v), da n ungerade ist und außerdem
u | n und v | n , da ggT(u,v)=1 ist.
Da (u+v)== 0 (mod 4) ist, muß einer der beiden Teiler u,v von n
in der Restklasse 1 und der andere in der Restklasse -1 (ist gleich
Restklasse 3 mod4) liegen.
n besitzt daher einen Teiler der Form 4*k - 1.
Der Rest des Beweises läuft wörtlich wie bei Hermann (siehe die letzten
beiden Zeilen von Hermanns Beweis).
Ob diese Beweis-Version mit der offiziellen Lösung des Bundesbewerbes
übereinstimmt, weiß ich nicht.
Das müßte eigentlich Klaus-R. wissen.
Mit freundlichen Grüßen,
Wolfgang Kirschenhofer

Hallo Wolfgang, hallo Hermann,

was heißt schon "offizielle Lösung"; Hauptsache richtig.

Für die Teilnehmer und anderen Interessenten hat der Bundeswettbewerb
Mathematik damals vier Lösungen veröffentlicht, wobei die Varianten auch
nur die eine - auch bei euch unterschiedlich begründete - Richtung des
Beweises betrafen; Variante 1 entspricht im Lösungsgedanken Wolfgangs
Lösung; der Lösungsweg von Hermann war nicht bei den damals angegebenen,
- aber die "offiziellen" Lösungsbeispiele waren (und sind noch) immer
nur eine Auswahl. Und originelle und besonders interessante
Teilnehmerlösungen gelangen nur dann in die Lösungsbeispiele, wenn die
Korrektoren dieser Arbeiten diese Lösungen empfehlend an die Zentrale
weitergeben.

Gruß an alle Aufgabenfreunde
Klaus-R.

[Michael Lange]

Hallo Wolfgang und andere,

Wolfgang Kirschenhofer schrieb:

[...]

Post by Wolfgang Kirschenhofer
Seien n ungerade und a und b natürliche Zahlen
mit 4/n = 1/a + 1/b und ggT(a,b)=d (1)
dann gilt a=d*u und b=d*v und ggT(u,v)=1 .
Aus (1) folgt dann 4/n = (u+v)/(d*u*v) und daraus weiter
4*u*v*d = n*(u+v) (2)
Aus (2) folgt 4 | (u+v), da n ungerade ist und außerdem
u | n und v | n , da ggT(u,v)=1 ist.
Da (u+v)== 0 (mod 4) ist, muß einer der beiden Teiler u,v von n
in der Restklasse 1 und der andere in der Restklasse -1 (ist gleich
Restklasse 3 mod4) liegen.
n besitzt daher einen Teiler der Form 4*k - 1.
Der Rest des Beweises läuft wörtlich wie bei Hermann (siehe die letzten
beiden Zeilen von Hermanns Beweis).

Ich habe tatsächlich mir auch einen Beweis überlegt, der in groben Zügen
wahrscheinlich aufs gleiche rausläuft. Es waren ja zwei Richtungen zu
beweisen: Lösungen existieren gdw n hat einen zu 3 kongruenten Teiler mod
4.

"<=": ist wirklich nur nachrechnen, insbesondere, wenn man die n == 3 mod 4
als (z.b.) primitiv bezeichnet (im Gegensatz zu Vielfachen, da kann man
mittles Distributivgesetz dann weiter ran).

Für primitive n = k*4+3 = 4(k+1)-1 gilt dann: a=k+1 und b=n(k+1) tuns.

"=>": Dafür habe ich mir überlegt, dass ich dann annehmen kann, dass
ggT(n,a)=1 (und damit auch ggT(n,b)=1) gilt, ansonsten kann man den ggT
austeilen (taucht in Deinem Beweis ja auch auf).
Damit habe ich aus 4/n = 1/a + 1/b:
4/n-1/a = 1/b = (4a-n)/(na). Ist der letzte Bruch gekürzt, so folgt direkt:
4a-n = 1, also n = 4a+1, fertig.
Aus der Annahme, dass der letzte Bruch NICHT gekürzt ist leitet man schnell
her: der Teiler, mit dem der Bruch gekürzt werden kann, ist ein Teiler von
4, woraus wegen Teilerfremdheit von a und n folgt, dass n eine gerade Zahl
ist. # (Voraussetzung n ungerade).

Post by Wolfgang Kirschenhofer
Ob diese Beweis-Version mit der offiziellen Lösung des Bundesbewerbes
übereinstimmt, weiß ich nicht.
Das müßte eigentlich Klaus-R. wissen.

[...]

Das weiß ich auch nicht, bin aber auch nicht Klaus-R. ;-)
Ebenso weiß ich nicht, ob "mein" Beweis der "offizielle" ist (Gibt es das
überhaupt? Ich dachte, die geben nur ein/zwei wirklich schöne Beispiele
raus?!). Allerdings würde ich gern noch wissen, wieso Klaus-R. das wissen
könnte/müsste? Die Frage geht natürlich speziell an ihn, wenn er darauf
antworten mag.

Mfg Michael

[Klaus-R. Loeffler]

Michael Lange <***@germanynet.de> wrote:

[...]

Post by Michael Lange

Post by Wolfgang Kirschenhofer
Ob diese Beweis-Version mit der offiziellen Lösung des Bundesbewerbes
übereinstimmt, weiß ich nicht.
Das müßte eigentlich Klaus-R. wissen.

[...]
Das weiß ich auch nicht, bin aber auch nicht Klaus-R. ;-)
Ebenso weiß ich nicht, ob "mein" Beweis der "offizielle" ist (Gibt es das
überhaupt? Ich dachte, die geben nur ein/zwei wirklich schöne Beispiele
raus?!). Allerdings würde ich gern noch wissen, wieso Klaus-R. das wissen
könnte/müsste? Die Frage geht natürlich speziell an ihn, wenn er darauf
antworten mag.

Wolfgang meint, ich müsste die "offiziellen" (das heißt: Die vom
Bundeswettbewerb Mathematik für die Teilnehmer angefertigten und später
im Klettverlag publizierten) Lösungen kennen, weil ich diese einige
Jahre lang zusammengestellt habe. Allerdings kann auch jeder Teilnehmer
der ersten Runde 1989 und jeder, der sich den Band mit den Aufgaben und
Lösungen aus der Zeit beschafft hat, nachsehen, welche Lösungsbeispiele
damals zu dieser Aufgabe veröffentlicht worden sind. Allerdings sind
extrem selten nur "ein/zwei wirklich schöne Beispiele" gegeben worden;
es macht ja einen Teil des Reizes einer Aufgabe aus, wenn sie auf ganz
unterschiedliche Weisen zu lösen ist. Und wenn der Aufgabenausschuss bei
einer erwogenen Aufgabe wirklich nur einen einzigen Lösungsweg kennt,
ist das in der Regel ein Grund, die Aufgabe nicht zu stellen.

Klaus-R.

[Michael Lange]

Hallo Klaus-R.

Klaus-R. Loeffler schrieb:

[...]

Post by Klaus-R. Loeffler
Wolfgang meint, ich müsste die "offiziellen" (das heißt: Die vom
Bundeswettbewerb Mathematik für die Teilnehmer angefertigten und später
im Klettverlag publizierten) Lösungen kennen, weil ich diese einige
Jahre lang zusammengestellt habe. Allerdings kann auch jeder Teilnehmer
der ersten Runde 1989 und jeder, der sich den Band mit den Aufgaben und
Lösungen aus der Zeit beschafft hat, nachsehen, welche Lösungsbeispiele
damals zu dieser Aufgabe veröffentlicht worden sind. Allerdings sind
extrem selten nur "ein/zwei wirklich schöne Beispiele" gegeben worden;
es macht ja einen Teil des Reizes einer Aufgabe aus, wenn sie auf ganz
unterschiedliche Weisen zu lösen ist. Und wenn der Aufgabenausschuss bei
einer erwogenen Aufgabe wirklich nur einen einzigen Lösungsweg kennt,
ist das in der Regel ein Grund, die Aufgabe nicht zu stellen.

[...]

Vielen Dank für die Information. Ich hoffe, ich war nicht zu neugierig. Als
Mathelehrer ist es für michnatürlich besonders interessant, mal so ein Buch
in die Hand zu bekommen. Die Lösung der Aufgaben kostet ja doch immer ein
bisschen Zeit. Allerdings ist es auch immer wieder eine Herausforderung ;-)

Mfg Michael

[Hermann Jurksch]

Post by Wolfgang Kirschenhofer
Hallo Hermann! Hallo Klaus-R.!
Seien n ungerade und a und b natürliche Zahlen
mit 4/n = 1/a + 1/b und ggT(a,b)=d (1)
dann gilt a=d*u und b=d*v und ggT(u,v)=1 .
Aus (1) folgt dann 4/n = (u+v)/(d*u*v) und daraus weiter
4*u*v*d = n*(u+v) (2)
Aus (2) folgt 4 | (u+v), da n ungerade ist und außerdem
u | n und v | n , da ggT(u,v)=1 ist.
Da (u+v)== 0 (mod 4) ist, muß einer der beiden Teiler u,v von n
in der Restklasse 1 und der andere in der Restklasse -1 (ist gleich
Restklasse 3 mod4) liegen.
n besitzt daher einen Teiler der Form 4*k - 1.

Das ist natürlich eine an Kürze kaum mehr zu überbietende
Musterlösung. Man muß sie allerdings 'sehen'.
Meine Lösung ist eher aus dem Hause "Hauruck": Ich habe
lediglich 4k-1 als quadratischen Nichtrest wahrgenommen und
in ab und a+b die Bausteine einer quadratischen Gleichung
und bin einfach dem 'Stallgeruch' hinterhergelaufen.
Die explizite Lösungsdarstellung für n = (4k-1)*q hätte
vielleicht zu obigem Gedankengang führen können ...

MfG
Hermann