any rational number is a sum of unit fractions


Any rational numberPlanetmathPlanetmathPlanetmath ab between 0 and 1 can be represented as a sum of different unit fractionsPlanetmathPlanetmath. This result was known to the Egyptians, whose way for representing rational numbers was as a sum of different unit fractions.

The following greedy algorithm can represent any 0ab<1 as such a sum:

  1. 1.



    be the smallest natural numberMathworldPlanetmath for which 1nab. If a=0, terminate.

  2. 2.

    Output 1n as the next term of the sum.

  3. 3.

    Continue from step 1, setting


Proof of correctness


The algorithm can never output the same unit fraction twice. Indeed, any n selected in step 1 is at least 2, so 1n-1<2n – so the same n cannot be selected twice by the algorithm, as then n-1 could have been selected instead of n.

It remains to prove that the algorithm terminates. We do this by inductionMathworldPlanetmath on a.

For a=0:

The algorithm terminates immediately.

For a>0:

The n selected in step 1 satisfies




and 0an-b<a – by the induction hypothesis, the algorithm terminates for ab-1n.


  1. 1.

    The greedy algorithm always works, but it tends to produce unnecessarily large denominators. For instance,


    but the greedy algorithm selects 12, leading to the representation

  2. 2.

    The representation is never unique. For instance, for any n we have the representations


    So given any one representation of ab as a sum of different unit fractions we can take the largest denominator appearing n and replace it with two (larger) denominators. Continuing the process indefinitely, we see infinitely many such representations, always.

Title any rational number is a sum of unit fractions
Canonical name AnyRationalNumberIsASumOfUnitFractions
Date of creation 2013-03-22 12:48:31
Last modified on 2013-03-22 12:48:31
Owner Mathprof (13753)
Last modified by Mathprof (13753)
Numerical id 7
Author Mathprof (13753)
Entry type Derivation
Classification msc 11A67
Synonym Egyptian algorithm