Egg delivery of the Brahmagupta

The Brahmagupta egg problem (also known as the Egg Basket Problem ) is a number-theoretical problem disguised as an application problem. The number of eggs in a basket fulfills a number of conditions, on the basis of which the exact number of eggs can then be determined. Today's task originally goes back to a task that the mathematician Brahmagupta (598–668) asked in his book Brahmasphutasiddhanta . The task is one of the oldest surviving examples of simultaneous congruences and their solution methods. This procedure is known today as the Chinese remainder sentence .

Task

The following widespread account of the problem comes from the book Number Theory and its History (1949) by Øystein Ore . There the original task of Brahmagupta is expanded by two additional conditions and dressed as an egg task.

There is an unknown number of eggs in a basket. If you now begin to empty the basket by removing two eggs at a time, a single egg will end up in the basket. If you take three eggs at once instead, you will end up with two eggs. Accordingly, with four eggs there is a remainder of three, with five eggs a remainder of four and with six eggs a remainder of five. However, if you always remove seven eggs at once, nothing remains, i.e. the basket is empty at the end. What is the minimum number of eggs in the basket?

Another common variant uses the constant remainder 1 instead of ascending remainders for division.

An old woman walks across the market square. A horse steps on her bag and breaks the eggs she bought. The owner of the horse wants to make good the damage and asks the old woman how many eggs were in her bag. She no longer knows the exact number, but she remembers that exactly one egg is left if the two of them take the eggs out of the bag when unpacking. The same thing happens when three, four, five and six people take the eggs out of the bag. Only when she takes seven of the eggs out of her pocket will there be no egg left. What's the smallest number of eggs the old woman can have in her pocket?

Brahmagupta's original task does not use any disguise, but is formulated directly as a number-theoretic problem.

What number divided by 6 gives the remainder 5, divided by 5 the remainder 4, divided by 4 the remainder 3 and divided by 3 the remainder 2?

history

The oldest known example of simultaneous congruence is found in the Chinese mathematical text Sunzi Suanjing (5th century or earlier). A little later, simultaneous congruences also appear in India in connection with the Kuttaka calculation , a method for solving linear Diophantine equations . This was mainly used in Indian mathematics from the 6th century onwards to solve astronomical and calendar problems. In these applications, the numbers that occur are usually much larger than in the egg feed, such as the orbital times of planets.

Bhaskara I. (c. 600-680) sets this task in his commentary on the Aryabhatiya of Aryabhata (476- c. 550), who first described the procedure. Brahmagupta also uses it in unclothed form as a "common" example in his astronomical work Brahmasphutasiddhanta (Chapter 8 Algebra , Section 1). Its form does not contain the first and the last condition (division by 2 with remainder 1 and divisibility by 7). Via Ibn al-Haytham , who wrote a treatise on the problem, and Leonardo Fibonacci's Liber abaci , the task made its way into the early modern arithmetic books . In a Byzantine work of the 15th century, it is included in the clothing for the first time. It can be found in many variants with different coefficients, e.g. B. in Tartaglia and in Filippo Calandri's arithmetic book (1491). Other things such. B. Sheep counted.

It is still used today under the name Brahmaguptas, mostly as an exercise or application example for the remaining Chinese sentence, in mathematical textbooks.

Representation with the help of simultaneous congruences

If you denote the number of eggs with , you get the following conditions from the above task text by Ore for : ${\displaystyle n}$ ${\displaystyle n}$

${\displaystyle n=1+2\cdot a_{1}}$

${\displaystyle n=2+3\cdot a_{2}}$

${\displaystyle n=3+4\cdot a_{3}}$

${\displaystyle n=4+5\cdot a_{4}}$

${\displaystyle n=5+6\cdot a_{5}}$

${\displaystyle n=7\cdot a_{6}}$

Here are (unknown) natural numbers. ${\displaystyle a_{1},\ldots ,a_{6}}$

These conditions can now be understood as number-theoretical congruences :

${\displaystyle n\equiv 1\mod 2}$

${\displaystyle n\equiv 2\mod 3}$

${\displaystyle n\equiv 3\mod 4}$

${\displaystyle n\equiv 4\mod 5}$

${\displaystyle n\equiv 5\mod 6}$

${\displaystyle n\equiv 0\mod 7}$

We are now looking for the smallest natural number that fulfills all of these congruences simultaneously (simultaneously).

solution

The solution to the egg task with ascending remainders is 119, that of the egg task with a constant remainder is 301 and the solution to the original problem by Brahmagupta 59. Strictly speaking, however, the original problem has an infinite number of solutions, since the smallest natural number is not explicitly asked here.

These numbers can be determined through an exhaustive search by using natural numbers starting at 1 in ascending order until one has found one that fulfills all of the above congruences or conditions.

The solution can be determined more elegantly and effectively with the generalized Chinese remainder of the sentence, or by combining the experimentation from the exhaustive search above with the successive substitution of the conditions. In addition, the variant with a constant remainder results in a simple solution using divisibility arguments.

literature

• Johannes Tropfke: History of Elementary Mathematics , Vol. 1. Arithmetic and Algebra , completely revised. by Kurt Vogel, Karin Reich , Helmuth Gericke. 4th ed., Berlin, de Gruyter, 1980. pp. 640-642. ( Online copy of the unedited original version on archive.org , does not contain the egg task.)
• Øystein Ore : Number Theory and its History . Courier Dover Publications 1988 (reprint, first published 1948), ISBN 9780486656205 , p. 249 ( restricted online version in Google Book Search - USA )
• Richard A. Mollin: An Introduction to Cryptography . CRC Press 2007, ISBN 9781584886181 , pp. 29–30 ( limited online version in Google Book Search - USA )

Web links

• Solving the egg task through successive insertion

Individual evidence

1. ↑ ^{a b} Michael Eisermann: Exercise sheet 2: Rings and bodies (PDF; 86 kB). In algebra lecture at the University of Stuttgart (summer semester 2010). Note that the variant in the exercise sheet uses different numbers than Ore, see note below.
2. ^ ^{A b c} Richard A. Mollin: An Introduction to Cryptography . CRC Press 2007, ISBN 9781584886181 , pp. 29–30 ( limited online version in Google Book Search - USA )
3. ↑ Øystein Ore : Number Theory and its History . Courier Dover Publications 1988 (reprint), ISBN 9780486656205 , p. 249 ( limited online version in Google Book Search - USA )
4. ↑ ^{a b} Chinese Remainder theorem on cut-the-knot.org
5. ^ ^{A b c} Henry Thomas Colebrooke: Algebra, with arithmetic and mensuration from the Sanscrit of Brahmegupta and Bhascara . 1917, p. 326 ( full online version in the Google book search)
6. ^ Sun Zi in the MacTutor History of Mathematics archive
7. ↑ ^{a b} Johannes Tropfke History of Elementary Mathematics , Vol. 1. Arithmetic and Algebra , completely revised. by Kurt Vogel, Karin Reich, Helmuth Gericke. 4th ed., Berlin, de Gruyter, 1980. pp. 640-642.
8. ↑ Note: This simplified calculation of the searched number n is as follows. Since you only get 1 as the remainder in the first five conditions, this means that the number n-1 is divisible by 2, 3, 4, 5 and 6. It is therefore also divisible by the LCM of these numbers, i.e. 60. You are therefore looking for the smallest multiple of 60, which, if you add 1, is divisible by 7. Now one simply tests the first multiples of 60 one after the other and finds that the condition is met for the first time for 5. So the solution is . ${\displaystyle 5\cdot 60+1=301}$