Egyptian Fractions
An Egyptian fraction is the sum of finitely many rational numbers, each of which can be expressed in the form where is a positive integer.
For example, the Egyptian fraction can be written as
Contents
Formal Definition
For any rational number , where are integers, there exist unit fractions (with numerator 1, and integer denominators) such that the sum of these unit fractions is equal to . As an example, However, the representation of in this form is not unique because of the identity Thus we have as well, and we can keep on decomposing any fraction as such.
History
Dating back to over 2,000 B.C., the Egyptians had developed their fraction system for mathematical division and calculation for any rational numbers. The Egyptian mathematicians exclusively used only unit fractions in their perception and did not seem to accept the idea of vulgar fraction, where the numerator is divided by denominator, as we do today. For example, if a cylindrical bucket has of water full, we can understand that by dividing the bucket into 5 equal heights, the water level will reach the brim of such 3 heights. However, for the Egyptians, other numerators apart from 1 were simply inconsistent with their algorithm. Instead, they would see such volume as half a bucket full of water plus one-tenth of that, for .
Moreover, they specifically designated the hieroglyphics for various denominators or rather symbols of equal dividing for any natural number. As such, their numerator would be assumed to be 1 though there were rare exceptions for and , for which they invent special symbols. The classic examples of the Egyptian fractions could be found in the ancient image of the Eye of Horus as shown below:
The reasons behind the Egyptian usage of such system remained unclear, but they might have perceived these unit fractions as "units" to be added as we similarly build up integers by summing the decimal units system. Their further study also contributed vastly to numerous writings, problems, and solutions. One of the most well-known work was called the Rhind Papyrus, written by Ahmes, which contained a table of converting to the sets of Egyptian fractions of various terms. This proved that the Egyptian fractions were indeed foundation of many Egyptian mathematical development and civilization during that period of time.
Greedy Algorithm for Finding Egyptian Fractions
One of the simplest algorithms to understand for finding Egyptian fractions is the greedy algorithm. With this algorithm, one takes a fraction and continues to subtract off the largest fraction until he/she is left only with a set of Egyptian fractions.
Find the Egyptian fraction representation of .
The greatest unit fraction less than is .
The remainder is .
The greatest unit fraction less than is .
The remainder is .This is a unit fraction, so the answer is given by
A recursive implementation of this algorithm in a perl script called "egyptian" is as follows:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
|
Methods for Decomposing an Egyptian Fraction
Some useful algebraic identities for the Egyptian fraction decomposition are
These are easily proved by the laws of addition of fractions.
Find the Egyptian fraction representation of .
We have Now, Thus, using the above identity we have
Relevance to Modern Number Theory
Egyptian fractions show up in all sorts of places! Below are some problems that involve Egyptian fraction representations. First, we prove a useful lemma:
Lemma:
If and are two integers, such that and are integers such that then is a divisor of .
By summing up the fractions on the right-hand side, we have
Clearly, is an integer. Thus, we have which means is a multiple of But cannot divide as .Therefore, divides .
[IMO 1979 Problem 1]
If and are positive integers such that prove that is divisible by .
We have
Now,
Similarily,
We can pair up all the fractions as such (as there are an even number of them).
We can now write where
Hence,
But is prime! Therefore, as is an integer and does not divide as is a divisor of , using our lemma above, is a multiple of .
The next problem is from the USA Mathematical Olympiad.
[USAMO 2010 Problem 5]
Let be an odd prime, and let . If and for integers and , then is divisible by .