Eieraufgabe des Brahmagupta

Die Eieraufgabe des Brahmagupta^[1], im Englischen auch als Egg Basket Problem^[2] bekannt, ist eine als Anwendungsproblem eingekleidete zahlentheoretische Aufgabe. Hierbei erfüllt die Anzahl der Eier in einem Korb eine Reihe von Bedingungen, anhand derer dann die genaue Anzahl der Eier zu ermitteln ist. Die heutige Aufgabe geht ursprünglich auf eine Aufgabe zurück, die der Mathematiker Brahmagupta (598–668) in seinem Buch Brahmasphutasiddhanta stellte. Die Aufgabe ist eine der ältesten überlieferten Beispiele für simultane Kongruenzen und deren Lösungsverfahren. Dieses Verfahren wird heute als chinesischer Restsatz bezeichnet.

Aufgabenstellung

Die folgende verbreitete Darstellung der Aufgabe entstammt dem Buch Number Theory and its History (1949) von Øystein Ore. Dort wird die Originalaufgabe von Brahmagupta um zwei zusatzliche Bedingungen erweitert und als Eieraufgabe eingekleidet.

In einem Korb befindet sich eine unbekannte Anzahl von Eiern. Beginnt man nun den Korb zu leeren, indem man immer zwei Eier auf einmal entfernt, so verbleibt am Ende ein einzelnes Ei im Korb. Wenn man stattdessen nun immer drei Eier auf einmal entnimmt, so bleiben am Ende zwei Eier übrig. Entsprechend ergibt sich bei vier Eiern ein Rest von drei, bei fünf Eiern ein Rest von vier und bei sechs Eiern ein Rest von fünf. Entfernt man jedoch immer sieben Eier auf einmal, so bleibt kein Rest, das heißt der Korb ist am Ende leer. Wie viele Eier befinden sich mindestens im Korb?^[3][2]

Eine weitere verbreitete Variante verwendet statt aufsteigender Reste bei der Division den konstanten Rest 1.

Eine alte Frau geht über den Marktplatz. Ein Pferd tritt auf ihre Tasche und zerbricht die gekauften Eier. Der Besitzer des Pferdes möchte den Schaden ersetzen und fragt die alte Frau, wie viele Eier in ihrer Tasche waren. Sie weiß die exakte Zahl nicht mehr, aber sie erinnert sich, dass genau ein Ei übrig bleibt, wenn sie beim Auspacken die Eier immer zu zweit aus der Tasche nimmt. Das Gleiche geschieht, wenn sie die Eier immer zu dritt, zu viert, zu fünft und zu sechst aus der Tasche nimmt. Nur wenn sie die Eier zu siebt aus der Tasche nimmt, bliebt kein Ei übrig. Was ist die kleinste Zahl an Eiern, welche die alte Frau in ihrer Tasche haben kann?^[4][1]

Die Originalaufgabe von Brahmagupta verwendet keinerlei Einkleidung, sondern ist direkt als zahlentheorisches Problem formuliert.

Welche Zahl liefert geteilt durch 6 den Rest 5, geteilt durch 5 den Rest 4, geteilt durch 4 den Rest 3 und geteilt durch 3 den Rest 2?^[5]

Geschichte

Das älteste bekannte Beispiel einer simultanen Kongruenz findet sich in dem chinesischen Mathematiktext Sunzi Suanjing (5. Jahrhundert oder früher).^[6] Wenig später treten simultane Kongruenzen auch in Indien im Zusammenhang mit der Kuttaka-Rechnung , einem Verfahren zur Lösung linearer Diophantischer Gleichungen, auf. Diese wurde in der indischen Mathematik ab dem 6. Jahrhundert vor allem zur Lösung astronomischer und kalendarischer Probleme verwendet. In diesen Anwendungen sind die auftretenden Zahlen meist wesentlich größer als in der Eieraufgabe, so etwa Umlaufzeiten von Planeten.^[7]

Bhaskara I. (c. 600-680) stellt diese Aufgabe in seinem Kommentar zum Aryabhatiya des Aryabhata (476- c. 550), der das Verfahren zuerst beschrieben hat. Brahmagupta benutzt sie in nicht eingekleideter Form ebenfalls als „gängiges“ Beispiel in seinem astronomischen Werk Brahmasphutasiddhanta (Kapitel 8 Algebra, Abschnitt 1).^[5] Seine Form enthält die erste und die letzte Bedingung (Division durch 2 mit Rest 1 und Teilbarkeit durch 7) nicht. Über Ibn al-Haytham, der ein Traktat über das Problem schrieb und Leonardo Fibonaccis Liber abaci gelangte die Aufgabe in die frühneuzeitlichen Rechenbücher. In einem byzantinische Werk des 15. Jahrhunderts ist sie zum ersten Mal in der Einkleidung enthalten. Sie findet sich in vielen Varianten mit unterschiedlichen Koeffizienten z. B. bei Tartaglia und im Rechenbuch des Filippo Calandri (1491). Als Einkleidung werden auch andere Dinge z. B. Schafe abgezählt.^[7]

Unter dem Namen Brahmaguptas wird sie noch heute, meist als Übungsaufgabe oder Anwendungsbeispiel zum chinesischen Restsatz, in mathematischen Lehrbüchern benutzt.

Darstellung mit Hilfe simultaner Kongruenzen

Bezeichnet man die Anzahl der Eier mit n, so erhält man aus dem obigen Aufgabentext von Ore die folgenden Bedingungen für n:

$n=1+2\cdot a_1$

$n=2+3\cdot a_2$

$n=3+4\cdot a_3$

$n=4+5\cdot a_4$

$n=5+6\cdot a_5$

$n=7 \cdot a_6$

Hierbei sind $a_1,\ldots,a_6$ (unbekannte) natürliche Zahlen.

Diese Bedingungen kann man nun als zahlentheoretische Kongruenzen auffassen:

$n\equiv 1\mod 2$

$n\equiv 2\mod 3$

$n\equiv 3\mod 4$

$n\equiv 4\mod 5$

$n\equiv 5\mod 6$

$n\equiv 0\mod 7$

Gesucht ist nun die kleinste natürliche Zahl, die alle diese Kongruenzen gleichzeitig (simultan) erfüllt.

Lösung

Die Lösung der Eieraufgabe mit aufsteigenden Resten beträgt 119^[2], die der Eieraufgabe mit konstantem Rest 301^[4] und die Lösung der Originalaufgabe von Brahmagupta 59^[5]. Wobei allerdings die Originalaufgabe streng genommen unendlich viele Lösungen besitzt, da hier nicht explizit nach der kleinsten natürlichen Zahl gefragt wird.

Man kann diese Zahlen durch eine exhaustive Suche ermitteln, indem man beginnend bei 1 solange aufsteigend natürliche Zahlen einsetzt, bis man eine gefunden hat, die alle obigen Kongruenzen beziehungsweise Bedingungen erfüllt.

Eleganter und effektiver lässt sich die Lösung mit dem verallgemeinerten chinesischen Restsatz bestimmen, oder indem man das Probieren aus der obigen exhaustiven Suche mit dem sukzessiven Einsetzen der Bedingungen ineinander kombiniert. Zudem ergibt sich bei der Variante mit einem konstanten Rest eine einfache Lösung über Teilbarkeitsargumente.^[8]

Literatur

• Johannes Tropfke Geschichte der Elementarmathematik, Bd 1. Arithmetik und Algebra, völlig neu bearb. von Kurt Vogel, Karin Reich, Helmuth Gericke. 4. Aufl, Berlin, de Gruyter, 1980. S. 640-642. (Online-Kopie der unbearbeiteten Originalfassung auf archive.org, enthält die Eieraufgabe nicht.)
• Øystein Ore: Number Theory and its History. Courier Dover Publications 1988 (Nachdruck, Erstveröffentlichung 1948), ISBN 9780486656205, S. 249 (eingeschränkte Online-Version in der Google Buchsuche-USA)
• Richard A. Mollin: An Introduction to Cryptography. CRC Press 2007, ISBN 9781584886181, S. 29-30 (eingeschränkte Online-Version in der Google Buchsuche-USA)

Weblinks

• Lösung der Eieraufgabe durch sukzessives Einsetzen (engl.)

Einzelnachweise

1. ↑ ^{a b} Michael Eisermann: Übungblatt 2: Ringe und Körper. In Algebra - Vorlesung an der Uni Stuttgart (Sommersemester 2010). Man beachte, dass die Variante im Übungsblatt andere Zahlen verwendet als Ore, siehe dazu Anmerkung weiter unten.
2. ↑ ^{a b c} Richard A. Mollin: An Introduction to Cryptography. CRC Press 2007, ISBN 9781584886181, S. 29-30 (eingeschränkte Online-Version in der Google Buchsuche-USA)
3. ↑ Øystein Ore: Number Theory and its History. Courier Dover Publications 1988 (Nachdruck), ISBN 9780486656205, S. 249 (eingeschränkte Online-Version in der Google Buchsuche-USA)
4. ↑ ^{a b} Chinese Remainder theorem auf cut-the-knot.org
5. ↑ ^{a b c} Henry Thomas Colebrooke: Algebra, with arithmetic and mensuration from the Sanscrit of Brahmegupta and Bhascara. 1917, S.326 (vollständige Online-Version in der Google Buchsuche)
6. ↑ Sun Zi im MacTutor History of Mathematics archive
7. ↑ ^{a b} Johannes Tropfke Geschichte der Elementarmathematik, Bd 1. Arithmetik und Algebra, völlig neu bearb. von Kurt Vogel, Karin Reich, Helmuth Gericke. 4. Aufl, Berlin, de Gruyter, 1980. S. 640-642.
8. ↑ Anmerkung: Diese vereinfachte Berechnung der gesuchten Zahl n lautet wie folgt. Da man als Rest in den ersten fünf Bedingungen nur 1 erhält, bedeutet dies, dass die Zahl n-1 durch 2, 3, 4, 5 und 6 teilbar ist. Somit ist sie auch durch das kgV dieser Zahlen, also 60, teilbar. Man sucht daher das kleinste Vielfache von 60, das, wenn man 1 hinzu addiert, durch 7 teilbar ist. Nun testet man einfach der Reihe nach die ersten Vielfachen von 60 und stellt fest, dass für 5 die Bedingung zum ersten Mal erfüllt ist. Die Lösung beträgt also $5\cdot 60+1=301$.