Egyptian Fractions

An Egyptian fraction is the sum of finitely many rational numbers, each of which can be expressed in the form $\frac{1}{q},$ where $q$ is a positive integer.

For example, the Egyptian fraction $\frac{61}{66}$ can be written as $\frac{61}{66} = \frac12 + \frac13 + \frac{1}{11}.$

For any rational number $\frac{m}{n}$, where $m, n$ are integers, there exist unit fractions (with numerator 1, and integer denominators) such that the sum of these unit fractions is equal to $\frac{m}{n}$. As an example, $$\dfrac{2}{3}= \dfrac{1}{2} + \dfrac{1}{6}.$$ However, the representation of $\frac{m}{n}$ in this form is not unique because of the identity $$1 = \dfrac{1}{2} + \dfrac{1}{3} + \dfrac{1}{6}.$$ Thus we have $$\dfrac{2}{3}= \dfrac{1}{2} + \dfrac{1}{6} = \dfrac{1}{2} + \dfrac{1}{6}\left(\dfrac{1}{2} + \dfrac{1}{3} + \dfrac{1}{6}\right) = \dfrac{1}{2} + \dfrac{1}{12} + \dfrac{1}{18} + \dfrac{1}{36}$$ as well, and we can keep on decomposing any fraction as such.

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 $\frac{3}{5}$ 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 $\frac{1}{2}+\frac{1}{10}=\frac{3}{5}$.

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 $\frac{2}{3}$ and $\frac{3}{4}$, 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 $\frac{2}{n}$ 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.

One of the simplest algorithms to understand for finding Egyptian fractions is the greedy algorithm. With this algorithm, one takes a fraction $\frac{a}{b}$ and continues to subtract off the largest fraction $\frac{1}{n}$ until he/she is left only with a set of Egyptian fractions.

Find the Egyptian fraction representation of $\frac{8}{9}$.

---

The greatest unit fraction less than $\frac{8}{9}$ is $\frac{1}{2}$.
The remainder is $\frac{7}{18}$.
The greatest unit fraction less than $\frac{7}{18}$ is $\frac{1}{3}$.
The remainder is $\frac{1}{18}$.

This is a unit fraction, so the answer is given by $$\dfrac{8}{9} = \dfrac{1}{2} + \dfrac{1}{3} + \dfrac{1}{18}.\ _\square$$

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

($a,$b) = @ARGV;

$i = 2; while (1/$i > $a/$b) {$i++}

print "Greatest unit fraction:  1/$i\n";

$lcm = lcm($b, $i);
$a2 = $a * $lcm / $b;
$itop = $lcm / $i;
$remainder = $a2 - $itop;
$gcd = gcd($remainder,$lcm);
$r2 = $remainder/$gcd;
$lcm2 = $lcm/$gcd;

print "Remainder:   $r2/$lcm2\n";

if ($r2 == 1) {
    print "Greatest unit fraction:  $r2/$lcm2\n";
} else {
    print `egyptian $r2 $lcm2`;
}


sub gcd {
    my ($a, $b) = @_;
    while ($a) { ($a, $b) = ($b % $a, $a) }
    $b
}

sub lcm {
    my ($a, $b) = @_;
    ($a && $b) and $a / gcd($a, $b) * $b or 0
}

The Egyptian fractions were particularly useful when dividing a number of objects equally for more number of people. This was practically important because many of the Egyptian structures required massive labor work. Any uneven distribution of food ration among the labors could easily kindle dispute and disrupt their work process.

For example, if the Egyptian boss were to give 5 Kubz (Arabic pancake-like bread) rations for 5 workmen, and then he just realized there was an extra man in the site, how would he divide 5 Kubz among 6 men? The answer is, as we know, $\frac{5}{6}$.

Using common sense, we would simply divide each Kubz into 6 equal portions, resulting in 30 pieces, and each workman would happily pick 5 of them. Surely, the problem was solved, but the Egyptian mathematician would apply a more elegant way to divide the Kubz by following the Egyptian fractions:

$$\dfrac{5}{6} = \dfrac{1}{2}+\dfrac{1}{3}.$$

This way, each workman would get half a Kubz plus one-third of a Kubz. To do so, first we take 3 Kubz and divide each in halves, resulting in 6 equal half portions, and each man would obtain each half. Then we take the remaining 2 Kubz and divide each into 3 equal portions, resulting in 6 equal one-third portions, and again each man would get one. By using this method, only a few cuts are needed for each Kubz without any need to go through all the same 6-denominator!

Naturally, the easiest way to break down vulgar fraction into Egyptian summation is to follow through the greedy algorithm, where the unit fraction nearest to the vulgar fraction is put in the equation first, followed by another nearest one to the remained, and so on. As in the previous example, $\frac{1}{2}$ is the nearest fraction to $\frac{5}{6}$ as shown. Nonetheless, this algorithm may not give the shortest way of the summation and thus may result in more unit fraction terms to be used.

Some useful algebraic identities for the Egyptian fraction decomposition are

$$\begin{aligned} \dfrac{a}{ab - 1} &= \dfrac{1}{b} + \dfrac{1}{b(ab - 1)} \\\\ \dfrac{1}{a} &= \dfrac{1}{a + 1} + \dfrac{1}{a(a + 1)}. \end{aligned}$$

These are easily proved by the laws of addition of fractions.

Find the Egyptian fraction representation of $\frac{8}{11}$.

---

We have $$\dfrac{8}{11} = \dfrac{6}{11} + \dfrac{2}{11}.$$ Now, $11 = 2 \cdot 6 - 1.$ Thus, using the above identity $$\dfrac{a}{ab - 1} = \dfrac{1}{b} + \dfrac{1}{b(ab - 1)},$$ we have $$\begin{aligned} \dfrac{6}{11} &= \dfrac{1}{2} + \dfrac{1}{22} \\\\ \dfrac{2}{11} &= \dfrac{1}{6} + \dfrac{1}{66} \\\\ \Rightarrow \dfrac{8}{11} &= \dfrac{1}{2} + \dfrac{1}{6} + \dfrac{1}{22} + \dfrac{1}{66}.\ _\square \end{aligned}$$

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 $r$ and $s$ are two integers, such that $\gcd(r,s) = 1$ and $a_1, a_2, \ldots, a_n$ are integers such that $$\frac{r}{s} = \sum\limits_{i = 1} ^n \frac{1}{a_i},$$ then $s$ is a divisor of $a_1\times a_2 \times \cdots \times a_n$.

By summing up the fractions on the right-hand side, we have $$\frac{r}{s} = \frac{\sum\limits_\text{cyc} {(a_1\times a_2 \times \cdots \times a_{n-1})}}{a_1\times a_2 \times \cdots \times a_n}.$$
Clearly, $\sum\limits_\text{cyc} {(a_1\times a_2 \times \cdots \times a_{n-1})} = t$ is an integer. Thus, we have $$st = r (a_1\times a_2 \times \cdots \times a_n),$$ which means $r (a_1\times a_2 \times \cdots \times a_n)$ is a multiple of $s.$ But $s$ cannot divide $r$ as $\gcd(r,s) = 1$.

Therefore, $s$ divides $a_1\times a_2 \times \cdots \times a_n$. $_\square$

[IMO 1979 Problem 1]
If $p$ and $q$ are positive integers such that $$\frac{p}{q}=1-\frac{1}{2}+\frac{1}{3}-\frac{1}{4}+ \cdots -\frac{1}{1318}+\frac{1}{1319},$$ prove that $p$ is divisible by $1979$.

---

We have

$$\begin{aligned} \dfrac{p}{q} &= 1 + \dfrac{1}{2}+ \dfrac{1}{3} + \dfrac{1}{4}+ \cdots + \dfrac{1}{1318}+\dfrac{1}{1319} - 2\left(\dfrac{1}{2} + \dfrac{1}{4} + \cdots + \dfrac{1}{1318}\right) \\ &= 1 + \dfrac{1}{2}+ \dfrac{1}{3} + \dfrac{1}{4}+ \cdots + \dfrac{1}{1318}+\dfrac{1}{1319} - \left(1 + \dfrac{1}{2}+ \dfrac{1}{3} + \dfrac{1}{4}+ \cdots + \dfrac{1}{659}\right) \\ &= \dfrac{1}{660}+ \dfrac{1}{661} + \dfrac{1}{662}+ \cdots + \dfrac{1}{1318}+\dfrac{1}{1319}. \end{aligned}$$

Now, $$\dfrac{1}{660} + \dfrac{1}{1319} = \dfrac{660 + 1319}{660 \cdot 1319} = \dfrac{1979}{660 \cdot 1319}.$$

Similarily, $$\dfrac{1}{661} + \dfrac{1}{1318} = \dfrac{661 + 1318}{661 \cdot 1318} = \dfrac{1979}{661 \cdot 1318}.$$

We can pair up all the fractions as such (as there are an even number of them).

We can now write $$\frac{p}{q} = 1979 \cdot \frac{r}{s},$$ where $$\frac{r}{s} = \dfrac{1}{660 \cdot 1319} + \dfrac{1}{661 \cdot 1318} + \cdots + \dfrac{1}{989 \cdot 990}.$$

Hence, $$p = 1979 \cdot \frac{qr}{s}.$$

But $1979$ is prime! Therefore, as $p$ is an integer and $s$ does not divide $1979$ $($as $s$ is a divisor of $660 \times 661 \times \cdots \times 1319$, using our lemma above$)$, $p$ is a multiple of $1979$. $_\square$

The next problem is from the USA Mathematical Olympiad.

[USAMO 2010 Problem 5]
Let $p$ be an odd prime, and let $q = \frac{3p-5}{2}$. If $$S_q = \frac{1}{2\cdot 3 \cdot 4} + \frac{1}{5\cdot 6 \cdot 7} + \cdots + \frac{1}{q(q+1)(q+2)}$$ and $\frac{1}{p}-2S_q = \frac{m}{n}$ for integers $m$ and $n$, then $m - n$ is divisible by $p$.