Fraction égyptienne

Une fraction égyptienne est, suivant les ouvrages, soit simplement une fraction unitaire, une fraction de numérateur égal à un et de dénominateur entier strictement positif, soit une somme de fractions unitaires distinctes. Quand on identifie fraction égyptienne et fraction unitaire, une telle somme peut se nommer développement en fractions égyptiennes, en raccourci développement égyptien.

Un exemple de développement égyptien de 1.

Un problème classique est justement d'écrire une fraction (positive) comme somme de fractions unitaires avec des dénominateurs tous différents. En effet tous les nombres rationnels positifs peuvent être écrits sous cette forme et ce, d'une infinité de façons différentes. Par exemple ${\displaystyle {\frac {2}{5}}={\frac {1}{5}}+{\frac {1}{6}}+{\frac {1}{30}}={\frac {1}{5}}+{\frac {1}{8}}+{\frac {1}{20}}+{\frac {1}{40}}}$.

Les anciens Égyptiens utilisaient une écriture pour les fractions qui correspond essentiellement à une telle somme (ils utilisaient aussi la fraction 2/3), et l'étude de telles sommes a continué à faire l'objet d'études lors de la période médiévale et lors de la période contemporaine.

En notation mathématique moderne, les développements en fractions égyptiennes ont été remplacées par les fractions ordinaires et la notation décimale. Néanmoins, ils continuent d'être un objet d'étude en théorie des nombres moderne et en mathématiques récréatives, aussi bien que dans les études historiques modernes des mathématiques anciennes.

Cet article résume ce qui est connu à propos des fractions égyptiennes à la fois anciennes et modernes. Pour les détails des sujets traités ici, voir les articles liés.

Histoire

Les fractions dans l'Égypte antique

Les anciens Égyptiens exprimaient toutes les fractions de valeur inférieure à 1 comme somme de fractions unitaires toutes distinctes. Les fractions 2/3 et 3/4 étaient, elles, parfois utilisées directement^[1].

Le hiéroglyphe en forme de bouche ouverte qui signifie partie, était utilisé pour représenter le numérateur 1 :

Les fractions étaient écrites avec ce hiéroglyphe dessus et le dénominateur en dessous. Ainsi 1/3 était écrit :

${\displaystyle ={\frac {1}{3}}}$

Il y avait des symboles spéciaux pour les fractions les plus courantes comme 1/2 et pour deux fractions non unitaires 2/3 et 3/4 :

${\displaystyle ={\frac {1}{2}}}$

${\displaystyle ={\frac {2}{3}}}$

${\displaystyle ={\frac {3}{4}}}$

Si le dénominateur devenait trop large, la « bouche » était placée juste au début du dénominateur :

${\displaystyle ={\frac {1}{331}}}$

La « table de deux » du Papyrus Rhind

Le papyrus Rhind.

Le papyrus Rhind (vers 1650 av. J.-C.), qui est conservé au British Museum de Londres, est le plus important document nous informant des connaissances mathématiques des temps anciens. Il comporte quatre-vingt-quatre problèmes résolus d'arithmétique, de géométrie et d'arpentage. Mais, avant de prendre connaissance de ces problèmes, l'Égyptien devait avoir à sa disposition différentes tables lui permettant de décomposer directement les fractions non unitaires en fractions unitaires. Une de ces tables, la table dite « des fractions doubles » ou « de 2/n », se trouve en première position sur le papyrus Rhind. Elle répertorie les fractions dont le numérateur est deux et dont le dénominateur n varie de trois à cent-un, n impairs et donne leur équivalent en somme de fractions unitaires^[2].

Quelques exemples de décomposition en fractions unitaires de la table de deux :

	2/5	→ 1/3 + 1/15
	2/7	→ 1/4 + 1/28
	2/9	→ 1/6 + 1/18
	2/11	→ 1/6 + 1/66
	2/101	→ 1/101 + 1/202 + 1/303 + 1/606.

Ces différents résultats furent obtenus par les anciens Égyptiens en appliquant la technique de la division.

Exemple de 2/5 :

	1	5
	2/3	3 + 1/3
✔	1/3	1 + 2/3
✔	1/15	1/3
	1/3 + 1/15	2

(1 + 2/3) + 1/3 = 2 par conséquent le résultat est 1/3 + 1/15.

Exemple du papyrus Rhind

Le problème numéro vingt-quatre du papyrus est le suivant : un nombre ajouté à son septième donne dix-neuf, quel est ce nombre ?

Sous forme symbolique moderne, le problème se résout facilement : x + x/7 = 8x/7 = 19, soit x = 133/8.

Le symbolisme algébrique n'existant pas il y a 4 000 ans, les Égyptiens utilisaient une méthode que l'on reconstitue comme étant celle dite de la fausse position. On appelle ainsi une méthode de résolution algébrique consistant à fournir une fausse solution qui conduit, ici par proportionnalité, à la solution du problème considéré.

Dans notre exemple, l'idée première est de se débarrasser du dénominateur gênant en choisissant sept comme fausse solution : le scribe obtient huit dans le calcul du nombre augmenté de son septième. Comme pour une telle équation (linéaire), on a proportionnalité entre la fausse solution 7 qui donne 8, et la solution cherchée qui doit donner 19. Une règle de trois donne donc cette solution, soit x = (19 × 7)/8.

Cela correspond à ce qui est proposé dans le papyrus : on divise dix-neuf par huit, ce qui fournit 2 + 1/4 + 1/8 et multiplie le tout par 7 = 1 + 2 + 4, ce qui fournit (2 + 1/4 + 1/8) + (4 + 1/2 + 1/4) + (9 + 1/2), soit 16 + 1/2 + 1/8.

Mathématiques médiévales

La notation sous forme de fractions égyptiennes a été utilisée pendant la période grecque et même au Moyen Âge^[3].

Le Liber abaci (1202) de Fibonacci contient plusieurs sections sur les mathématiques liées aux fractions égyptiennes. La plus connue de ces dernières est l'algorithme glouton pour le calcul des fractions égyptiennes, par le choix répété de la fraction unitaire avec le plus petit dénominateur qui n'est pas plus grande que la fraction restant à développer^{[note 1]}.

Fibonacci propose aussi de chercher une représentation du numérateur de la fraction comme somme de diviseurs du dénominateur, ce qui fournit alors un développement égyptien. Ceci est possible lorsque le dénominateur est un nombre pratique.

Dans le Liber Abaci, Fibonacci a écrit aussi à propos de la forme ascendante d'une fraction continue,

${\displaystyle x={\frac {\displaystyle 1+{\frac {\displaystyle 1+{\frac {\displaystyle 1+\cdots }{\displaystyle a_{3}}}}{\displaystyle a_{2}}}}{\displaystyle a_{1}}},}$

qui peut être réécrite comme développement égyptien :

${\displaystyle x={\frac {1}{a_{1}}}+{\frac {1}{a_{1}a_{2}}}+{\frac {1}{a_{1}a_{2}a_{3}}}+\cdots }$.

Un développement de cette forme dans lequel les entiers a_i sont croissants est appelé un développement en série de Engel. Chaque nombre rationnel possède un développement de Engel fini, tandis que les nombres irrationnels ont un développement de Engel infini^[4].

Études modernes

Les théoriciens des nombres modernes ont étudié beaucoup de problèmes reliés aux fractions égyptiennes^[5], incluant les problèmes de borne pour la longueur ou de dénominateur maximum dans les représentations en fractions égyptiennes, la recherche de recouvrement ou de développements de certaines formes spéciales ou dans lesquels les dénominateurs sont tous d'un certain type spécial, l'arrêt de diverses méthodes pour les développements en fractions égyptiennes et ont montré que les développements existent pour un ensemble suffisamment dense quelconque de nombres suffisamment lisses. Des mathématiciens connus tels que James Sylvester, Solomon Golomb, Wacław Sierpiński, Paul Erdős, Ernst G. Straus, Ronald Graham, ou Gérald Tenenbaum ont notamment contribué à ce champ de recherche.

Existence d'un développement égyptien pour tout rationnel positif

Ce chapitre explique, par étapes successives, comment on peut démontrer que tout nombre rationnel positif peut être exprimé sous forme de développement égyptien.

E1 : le nombre 1 et toute fraction unitaire peuvent être exprimés en développement égyptien

On remarque que ${\displaystyle 1={\frac {1}{2}}+{\frac {1}{2}}={\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{6}}}$, qui est un développement égyptien. Pour tout ${\displaystyle n>1}$, on remarque que : ${\displaystyle {\frac {1}{n}}-{\frac {1}{n+1}}={\frac {1}{n\times (n+1)}}}$. Donc ${\displaystyle {\frac {1}{n}}={\frac {1}{n+1}}+{\frac {1}{n\times (n+1)}}}$, ce qui est un développement égyptien car ${\displaystyle n>1}$ donc ${\displaystyle n\times (n+1)>n+1}$. La propriété annoncée est donc démontrée. On a aussi démontré que toute fraction unitaire ${\displaystyle {\frac {1}{n}}}$ avec ${\displaystyle n>1}$ peut être décomposée comme la somme de deux fractions unitaires distinctes, et que le nombre ${\displaystyle 1}$ peut l'être comme somme de trois fractions unitaires distinctes.

La suite A002966 de l'OEIS donne le nombre de développement égyptiens de longueur donnée du nombre 1.

E2 : tout rationnel positif inférieur à 1 peut être exprimé sous forme de développement égyptien

L'application de l'algorithme de Fibonacci permet de construire un tel développement égyptien^[6].

E3 : tout nombre rationnel positif peut être exprimé sous forme de développement égyptien commençant par toute fraction unitaire qui lui est inférieure

Plusieurs méthodes peuvent être utilisées pour démontrer cette propriété^[7]. Celle explicitée ci-dessous s'appuie sur la série harmonique ${\displaystyle H}$ , série strictement croissante divergente de terme général^[8] : $${\displaystyle H_{n}=\sum _{i=1}^{n}{\frac {1}{i}}=1+{\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{4}}+{\frac {1}{5}}+\cdots +{\frac {1}{n}}}$$

Démonstration

Il faut démontrer que pour tout rationnel positif ${\displaystyle r}$, il existe un développement égyptien de ${\displaystyle r}$ dont le plus grand élément est ${\displaystyle {\frac {1}{m}}}$ et ce quel que soit l'entier ${\displaystyle m}$ tel que ${\displaystyle r>{\frac {1}{m}}}$. Considérons d'abord un rationnel positif ${\displaystyle r>{\frac {1}{2}}}$ et définissons la série ${\displaystyle J}$ par : ${\displaystyle J_{1}=0}$ et son terme générique pour ${\displaystyle n>1}$ : $${\displaystyle J_{n}=H_{n}-1=\sum _{i=2}^{n}{\frac {1}{i}}={\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{4}}+{\frac {1}{5}}+\cdots +{\frac {1}{n}}}$$ Comme ${\displaystyle H}$, ${\displaystyle J}$ est une série strictement croissante et divergente, tous ses termes ${\displaystyle J_{n}}$ sont des nombres rationnels et ils ont, par construction, un développement égyptien. Il existe donc un entier ${\displaystyle k}$ tel que ${\displaystyle J_{k}\leq r<J_{k+1}}$. Si ${\displaystyle r=J_{k}}$, alors ${\displaystyle r}$ a bien un développement égyptien donné par le développement de ${\displaystyle J_{k}}$. Si ${\displaystyle J_{k}<r}$, notons ${\displaystyle a=r-J_{k}}$. Puisque ${\displaystyle J_{k}}$ et ${\displaystyle r}$ sont des rationnels, ${\displaystyle a}$ est également un rationnel. Et comme ${\displaystyle J_{k}<r<J_{k+1}}$, nous avons : ${\displaystyle 0<a<J_{k+1}-J_{k}={\frac {1}{k+1}}}$. Donc ${\displaystyle a}$ est un rationnel inférieur à ${\displaystyle 1}$ : il a donc, d'après l'algorithme de Fibonacci, un développement égyptien, dont le terme le plus important est inférieur à ${\displaystyle {\frac {1}{k+1}}}$. Soit un tel développement : ${\displaystyle a=\sum _{i=1}^{l}{\frac {1}{p_{i}}}}$ avec ${\displaystyle p_{l}>p_{l-1}>...>p_{1}>k+1}$. Nous avons donc ${\displaystyle r=J_{k}+a=\sum _{i=2}^{k}{\frac {1}{i}}+\sum _{i=1}^{l}{\frac {1}{p_{i}}}}$. Et comme les ${\displaystyle p_{i}}$ sont tous différents et supérieurs à ${\displaystyle k+1}$, ceci est bien un développement égyptien. Donc ${\displaystyle r}$ a un développement égyptien commençant par ${\displaystyle {\frac {1}{2}}}$, et la propriété est démontrée pour ${\displaystyle m=2}$ et ${\displaystyle r>{\frac {1}{2}}}$.

Généralisons le résultat à tout entier ${\displaystyle m\geq 2}$. Définissons la série ${\displaystyle J(m)}$ par son terme générique $${\displaystyle J_{n}(m)=\sum _{i=m}^{m+n-2}{\frac {1}{i}}={\frac {1}{m}}+{\frac {1}{m+1}}+{\frac {1}{4}}+{\frac {1}{5}}+\cdots +{\frac {1}{n}}}$$ On a démontré ci-dessus la propriété recherchée pour ${\displaystyle m=2}$ en utilisant la série ${\displaystyle J(2)}$ : le même raisonnement, en utilisant ${\displaystyle J(m)}$ pour tout ${\displaystyle m\geq 2}$, démontre l'existence d'un développement de ${\displaystyle r}$ commençant par ${\displaystyle {\frac {1}{m}}}$. La propriété est donc démontrée pour tout rationnel ${\displaystyle r>{\frac {1}{2}}}$ : ${\displaystyle r}$ a un développement égyptien qui commence par toute fraction unitaire ${\displaystyle {\frac {1}{m}}}$ avec ${\displaystyle m\geq 2}$.

Généralisons de nouveau aux rationnels positifs ${\displaystyle r\leq {\frac {1}{2}}}$. Il existe donc un entier ${\displaystyle k\geq 2}$ tel que ${\displaystyle {\frac {1}{k+1}}<r\leq {\frac {1}{k}}}$. Considérons la série ${\displaystyle J(k+p)}$ où ${\displaystyle p}$ est un entier quelconque non nul : son premier terme est ${\displaystyle {\frac {1}{k+p}}}$, son second terme ${\displaystyle {\frac {1}{k+p}}+{\frac {1}{k+p+1}}}$, etc. Comme cette série est croissante et divergente, il existe un entier ${\displaystyle n}$ tel que : ${\displaystyle J_{n}(k+p)\leq r<J_{n+1}(k+p)}$. En appliquant le même raisonnement que précédemment, on démontre que ${\displaystyle r}$ a bien un développement égyptien commençant par ${\displaystyle {\frac {1}{k+p}}}$. Ce qui conclut la démonstration générale.

Propriétés

Depuis le XIII^e siècle, les développements égyptiens ont fait l'objet de nombreuses études, relatives notamment à la taille de ces développements, ou à l'existence de développements soumis à diverses contraintes. Certaines des propriétés étudiées, démontrées ou conjecturées, sont indiquées dans ce chapitre.

Taille minimale du développement

Il est possible pour n'importe quelle rationnel d'obtenir un développement égyptien aussi grand que l'on veut en utilisant l'identité ${\displaystyle {\frac {1}{b}}={\frac {1}{(b+1)}}+{\frac {1}{b(b+1)}}}$ et en l'appliquant de manière répétitive au dernier terme d'un de ses développements^[9]. On a aussi vu plus haut qu'il est même possible de faire commencer tout développement d'un rationnel par n'importe quelle fraction unitaire qui lui est inférieure.

L'une des questions étudiées par plusieurs mathématiciens est la suivante : quelle est la taille minimale du développement égyptien d'un nombre rationnel donné? et comment construire un développement de cette taille minimale?

Les algorithmes de Fibonacci et de Golomb^{[note 2]} donnent un développement dont le nombre de terme est au plus égal au numérateur de la fraction initiale^[10]. On peut cependant être plus précis. En effet il existe pour toute fraction ${\displaystyle {\frac {a}{b}}}$ une représentation avec au plus ${\displaystyle O({\sqrt {\log b}})}$ termes^[11].

Il est conjecturé que pour tout entier ${\displaystyle t\geq 3}$ et pour tout ${\displaystyle k>t}$, la fraction ${\displaystyle {\frac {a}{b}}}$ peut s'écrire comme la somme de ${\displaystyle t}$ fractions égyptiennes dès lors que ${\displaystyle b}$ est suffisamment grand^[10]. D'autres conjectures plus spécifiques ont été émises.

Conjectures d'Erdős-Straus et de Sierpiński

En 1948, Paul Erdős et Ernst G. Straus ont conjecturé que pour tout entier ${\displaystyle n>1}$, ${\displaystyle 4/n}$ peut s'écrire comme somme de trois fractions égyptiennes^{[note 3]}

${\displaystyle {\frac {4}{n}}={\frac {1}{a}}+{\frac {1}{b}}+{\frac {1}{c}}}$.

De même, Wacław Sierpiński a conjecturé en 1956 que pour tout entier ${\displaystyle n>1}$, il existe trois naturels ${\displaystyle a}$, ${\displaystyle b}$ et ${\displaystyle c}$ tels que^{[note 3]}:

${\displaystyle {\frac {5}{n}}={\frac {1}{a}}+{\frac {1}{b}}+{\frac {1}{c}}}$.

Aucune de ces deux conjectures n'est démontrée à ce jour, même s'il existe beaucoup de résultats assez forts concernant notamment la conjecture d'Erdős-Straus.

Plus grand dénominateur

Majorant

En étudiant les développements fournis par l'algorithme d'Erdős-Bleicher (voir supra), Yokota et Gérald Tenenbaum ont montré^[10] que pour toute fraction ${\displaystyle {\frac {a}{b}}}$, il existe un développement égyptien dont le plus grand dénominateur est inférieur à ${\displaystyle 4b(\log b)^{2}\log(\log b)}$.

Ce résultat peut être raffiné. En effet une fraction ${\displaystyle {\frac {a}{b}}}$ quelconque possède une représentation en fractions égyptiennes dans laquelle le dénominateur maximum est borné par^[12] :

${\displaystyle O\left({\frac {b\log b}{\log \log b}}\right)}$

Minorant

Pour une fraction égyptienne ${\displaystyle {\frac {a}{p}}}$ dont le dénominateur est un nombre premier, le plus grand dénominateur de tout développement égyptien de ${\displaystyle {\frac {a}{p}}}$ est supérieur à ${\displaystyle p\log _{2}(p)}$, d'après un théorème montré en 1976 par Paul Erdős et Bleicher^[10].

Problèmes de combinatoire

• La conjecture d'Erdős-Graham en théorie combinatoire des nombres établit que pour toute partition finie de l'ensemble des entiers supérieurs (ou égaux) à deux, l'une des parties peut être utilisée pour former un développement égyptien du nombre un. C’est-à-dire, pour chaque r > 0, et chaque r-coloration des entiers supérieurs à deux, il existe un sous-ensemble monochromatique fini S de ces entiers tel que :${\displaystyle \sum _{n\in S}1/n=1}$.La conjecture a été démontrée en 2000 par Ernest S. Croot III (en).

Développements restreints à des dénominateurs particuliers

• Les nombres qui peuvent être représentés par des sommes de fractions égyptiennes dans lesquelles tous les dénominateurs sont des puissances n-ièmes. En particulier, un nombre rationnel q peut être représenté en somme de fractions égyptiennes avec des dénominateurs carrés si et seulement si q est situé dans un des deux intervalles demi-ouverts^[13] :${\displaystyle \left[0,{\frac {\pi ^{2}}{6}}-1\right[\cup \left[1,{\frac {\pi ^{2}}{6}}\right[}$.

Autres

• Le problème de Znám est intimement relié à l'existence des développements égyptiens de la forme :${\displaystyle \sum {\frac {1}{x_{i}}}+\prod {\frac {1}{x_{i}}}=1}$.
• Un nombre rationnel quelconque possède des développements très denses, en utilisant une fraction constante de dénominateurs allant jusqu'à N pour un N suffisamment grand^[14].

Algorithmes

Obtenir un développement de ${\displaystyle {\frac {a}{b}}}$ en fraction égyptienne^{[note 4]} peut se faire grâce à différents algorithmes, qui donneront des résultats différents mais néanmoins valides.

Méthode élémentaire

On peut obtenir le développement de la fraction ${\displaystyle {\frac {a}{b}}}$ grâce à l'identité suivante^{[note 5]}:

${\displaystyle {\frac {1}{b}}={\frac {1}{(b+1)}}+{\frac {1}{b(b+1)}}}$

L'algorithme récursif suivant permet alors de trouver le développement cherché :

procédure Élémentaire${\displaystyle \left({\frac {a}{b}}\right)}$
      Si ${\displaystyle a=1}$ : 
            Renvoyer ${\displaystyle {\frac {a}{b}}}$
      Sinon :
            Renvoyer ${\displaystyle {\frac {1}{b}}}$ + Élémentaire${\displaystyle \left({\frac {a-1}{b+1}}\right)}$ + Élémentaire${\displaystyle \left({\frac {a-1}{b(b+1)}}\right)}$
fin-procédure

Terminaison

L'algorithme proposé se termine car la suite des numérateurs ${\displaystyle r}$ est une suite d'entiers strictement décroissante et minorée par 1. L'algorithme s'achève donc en un nombre fini d'étapes.

Correction

À l'issue de chaque étape, on a égalité entre ${\displaystyle {\frac {a}{b}}}$ et une somme de fractions égyptiennes et d'une autre fraction. Lorsque l'algorithme termine, on a donc égalité entre ${\displaystyle {\frac {a}{b}}}$ et une somme de fractions égyptiennes. L'algorithme est donc correct.

Exemple

On veut le développement de ${\displaystyle {\frac {3}{16}}}$ :

Étape	Résultat
0	${\displaystyle {\frac {3}{16}}}$
1	${\displaystyle {\frac {1}{16}}+\left({\frac {2}{17}}+{\frac {2}{16\times 17}}\right)}$
2	${\displaystyle {\frac {1}{16}}+{\frac {1}{17}}+{\frac {1}{272}}+\left({\frac {1}{18}}+{\frac {1}{17\times 18}}\right)+\left({\frac {1}{273}}+{\frac {1}{272\times 273}}\right)}$
Sortie	${\displaystyle {\frac {1}{16}}+{\frac {1}{17}}+{\frac {1}{18}}+{\frac {1}{272}}+{\frac {1}{273}}+{\frac {1}{306}}+{\frac {1}{74256}}}$

Algorithme de Fibonacci-Sylvester (algorithme glouton)

On veut obtenir le développement de ${\displaystyle {\frac {a}{b}}}$, on peut pour cela utiliser l'algorithme glouton suivant :

procédure Fibonacci${\displaystyle \left({\frac {a}{b}}\right)}$
      Si ${\displaystyle a=1~{\mathtt {OU}}~a=0}$ : 
            Renvoyer ${\displaystyle {\frac {a}{b}}}$
      Sinon :
            Déterminer le plus petit entier ${\displaystyle n}$ qui est plus grand que ${\displaystyle {\frac {1}{\frac {a}{b}}}={\frac {b}{a}}}$, soit ${\displaystyle n=\left\lceil {\frac {b}{a}}\right\rceil }$
            Renvoyer ${\displaystyle {\frac {1}{n}}}$ + Fibonacci${\displaystyle \left({\frac {a}{b}}-{\frac {1}{n}}\right)}$
fin-procédure

Si, à chaque étape, on choisit le dénominateur : ${\displaystyle \lfloor b/a\rfloor +1}$ à la place de ${\displaystyle \lceil b/a\rceil }$, on obtient le développement en série de Sylvester.

Terminaison

On a l'égalité ${\displaystyle {\frac {a}{b}}-{\frac {1}{n}}={\frac {an-b}{bn}}}$ avec ${\displaystyle n=\left\lceil {\frac {b}{a}}\right\rceil }$ (où ${\displaystyle \lceil ~\rceil }$ désigne la fonction plafond).

Or on a ${\displaystyle {\frac {b}{a}}<\left\lceil {\frac {b}{a}}\right\rceil <{\frac {b}{a}}+1}$ et donc ${\displaystyle {\frac {b}{a}}\times a-b<\left\lceil {\frac {b}{a}}\right\rceil \times a-b<\left({\frac {b}{a}}+1\right)\times a-b}$. C'est-à-dire en simplifiant ${\displaystyle 0<an-b<a}$. Une étape de l'algorithme renvoie donc la somme d'une fraction de numérateur 1 et d'une fraction dont le numérateur est un entier positif strictement plus petit que ${\displaystyle a}$. L'algorithme termine donc en un nombre fini d'étapes^[10].

Correction

À l'issue de chaque étape, on a égalité entre ${\displaystyle {\frac {a}{b}}}$ et une somme de fractions égyptiennes de dénominateurs distincts et d'une autre fraction. Lorsque l'algorithme termine, on a donc égalité entre ${\displaystyle {\frac {a}{b}}}$ et une somme de fractions égyptiennes. L'algorithme est donc correct^[10]. Cela a été démontré par Sylvester en 1880^[15].

Avantages et inconvénients

L'algorithme de Fibonacci donne un développement qui peut contenir des dénominateurs de taille élevée, ainsi il donne^[10] :

${\displaystyle {\frac {5}{121}}={\frac {1}{25}}+{\frac {1}{757}}+{\frac {1}{763309}}+{\frac {1}{873960180913}}+{\frac {1}{1527612795642093418846225}},}$

plutôt que :

${\displaystyle {\frac {5}{121}}={\frac {1}{33}}+{\frac {1}{121}}+{\frac {1}{363}}}$.

En revanche, l'algorithme de Fibonacci permet de comparer facilement deux fractions par ordre lexicographique de leurs développements égyptiens^[10].

Exemple

On veut le développement de ${\displaystyle {\frac {3}{16}}}$ :

Étape	Résultat
0	${\displaystyle {\frac {3}{16}}}$ (avec ${\displaystyle \left\lceil {\frac {16}{3}}\right\rceil =6}$)
1	${\displaystyle {\frac {1}{6}}+\left({\frac {3}{16}}-{\frac {1}{6}}\right)}$
Résultat	${\displaystyle {\frac {1}{6}}+{\frac {1}{48}}}$

Algorithme de Golomb

On souhaite écrire la fraction ${\displaystyle {\frac {a}{b}}<1}$ comme somme de fractions égyptiennes. Sans perte de généralité, on peut supposer que ${\displaystyle a}$ et ${\displaystyle b}$ sont premiers entre eux. Le théorème de Bachet-Bézout permet d'affirmer qu'il existe deux entiers naturels premiers entre eux ${\displaystyle r}$ et ${\displaystyle s}$ tels que ${\displaystyle r<s<b}$ et ${\displaystyle as=1+br}$. De tels nombres peuvent être obtenus en utilisant l'algorithme d'Euclide étendu. En divisant chaque membre par ${\displaystyle bs}$ on obtient donc ${\displaystyle {\frac {a}{b}}={\frac {1}{bs}}+{\frac {r}{s}}}$.

L'algorithme de Golomb est l'algorithme récursif suivant^[10],[16] :

procédure Golomb${\displaystyle \left({\frac {a}{b}}\right)}$
      Si ${\displaystyle a=1}$ : 
            Renvoyer ${\displaystyle {\frac {a}{b}}}$
      Sinon :
            Déterminer ${\displaystyle r}$ et ${\displaystyle s}$ tels que ${\displaystyle r<s<b}$ et ${\displaystyle as=1+br}$
            Renvoyer ${\displaystyle {\frac {1}{bs}}}$ + Golomb${\displaystyle \left({\frac {r}{s}}\right)}$
fin-procédure

Terminaison

L'algorithme de Golomb termine car la suite des numérateurs ${\displaystyle r}$ est une suite d'entiers strictement décroissante et minorée par 1. L'algorithme s'achève donc en un nombre fini d'étapes.

Correction

À l'issue de chaque étape, on a égalité entre ${\displaystyle {\frac {a}{b}}}$ et une somme de fractions égyptiennes et d'une autre fraction. Lorsque l'algorithme termine, on a donc égalité entre ${\displaystyle {\frac {a}{b}}}$ et une somme de fractions égyptiennes. L'algorithme est donc correct.

Conséquence théorique

Pour toute fraction ${\displaystyle {\frac {a}{b}}}$, il existe un développement en fractions égyptiennes dont tous les dénominateurs sont inférieurs ou égaux à ${\displaystyle b(b-1)}$. C'est en particulier le cas du développement obtenu avec l'algorithme de Golomb^[10].

Exemple

On veut le développement de ${\displaystyle {\frac {3}{16}}}$ :

Étape	Résultat
0	${\displaystyle {\frac {3}{16}}}$
1	${\displaystyle {\frac {1}{176}}+{\frac {2}{11}}}$ (avec ${\displaystyle 3\times 11=2\times 16+1}$)
2	${\displaystyle {\frac {1}{176}}+{\frac {1}{66}}+{\frac {1}{6}}}$ (avec ${\displaystyle 2\times 6=11\times 1+1}$)
Résultat	${\displaystyle {\frac {1}{6}}+{\frac {1}{66}}+{\frac {1}{176}}}$

Algorithme d'Erdős et Bleicher

Erdős et Bleicher ont proposé d'introduire le produit des k premiers nombres premiers ${\displaystyle \pi _{k}}$ comme intermédiaire de calcul, car ce sont des nombres pratiques. La fraction dont on cherche le développement égyptien n'est plus ${\displaystyle {\frac {a}{b}}}$ mais ${\displaystyle {\frac {a\pi _{k}}{b\pi _{k}}}}$. L'algorithme qu'ils proposent est alors^[10] :

procédure Erdős-Bleicher${\displaystyle \left({\frac {a}{b}}\right)}$
      Déterminer ${\displaystyle k}$ tel que ${\displaystyle \pi _{k-1}<b\leq \pi _{k}}$
      Choisir un entier ${\displaystyle r}$ tel que ${\displaystyle \pi _{k}\left(1-{\frac {1}{k}}\right)\leq r\leq \pi _{k}\left(2-{\frac {1}{k}}\right)}$
      Déterminer l'entier ${\displaystyle s}$ tel que ${\displaystyle a\pi _{k}=bs+r}$
      Choisir une représentation de ${\displaystyle s}$ et ${\displaystyle r}$ comme sommes de diviseurs de respectivement ${\displaystyle \pi _{k}}$ et ${\displaystyle b\pi _{k}}$
      Renvoyer la somme des fractions simplifiées obtenues

Conséquence théorique

Les sorties possibles de cet algorithme permettent de majorer le plus grand dénominateur du développement (voir infra)^[10].

Exemple

On veut le développement de ${\displaystyle {\frac {3}{16}}}$ :

Étape	Résultat
0	${\displaystyle 2\times 3<16\leq 2\times 3\times 5}$ donc ${\displaystyle k=3}$
1	On choisit par exemple[note 6] ${\displaystyle r=42}$ et ${\displaystyle s=3}$
2	On a ${\displaystyle {\frac {3}{16}}={\frac {3\times 30}{16\times 30}}={\frac {90}{16\times 30}}={\frac {3\times 16}{16\times 30}}+{\frac {42}{16\times 30}}}$
3	On écrit ${\displaystyle {\frac {3\times 16}{16\times 30}}+{\frac {32+10}{16\times 30}}}$
Résultat	Après simplification ${\displaystyle {\frac {3}{16}}={\frac {1}{10}}+{\frac {1}{15}}+{\frac {1}{48}}}$

Cas où le dénominateur est une puissance de deux

Lorsque le dénominateur ${\displaystyle b}$ est une puissance de deux, on peut trouver un développement de ${\displaystyle {\frac {a}{b}}={\frac {a}{2^{n}}}}$ grâce à l'écriture binaire de ${\displaystyle a=a_{n-1}2^{n-1}+a_{n-1}2^{n-1}+\dots +a_{0}}$ (où les ${\displaystyle a_{0},\dots ,a_{n-1}}$ valent tous 0 ou 1)^[10]. Le développement obtenu est alors ${\displaystyle {\frac {a}{2^{n}}}={\frac {a_{0}}{2^{n-1}}}+{\frac {a_{1}}{2^{n-2}}}+\dots +{\frac {a_{n-1}}{2}}}$.

Exemple

On veut le développement de ${\displaystyle {\frac {3}{16}}}$. On a ${\displaystyle 3=2^{1}+2^{0}}$ donc ${\displaystyle {\frac {3}{16}}={\frac {1}{16}}+{\frac {2}{16}}={\frac {1}{16}}+{\frac {1}{8}}}$.

Application

Dans le cas où le dénominateur de ${\displaystyle {\frac {a}{b}}}$ n'est pas une puissance de deux, on peut adapter l'algorithme précédent en déterminant le développement de ${\displaystyle {\frac {2^{k}\times a}{2^{k}\times b}}}$ où ${\displaystyle 2^{k}}$ est la plus petite puissance de deux supérieure à ${\displaystyle b}$^[10] :

procédure${\displaystyle \left({\frac {a}{b}}\right)}$
         Déterminer l'entier ${\displaystyle k}$ tel que ${\displaystyle 2^{k-1}<b\leq 2^{k}}$
         Écrire ${\displaystyle {\frac {a}{b}}={\frac {2^{k}\times a}{2^{k}\times b}}={\frac {bs}{2^{k}\times b}}+{\frac {2^{k}\times a-bs}{2^{k}\times b}}}$ et tel que ${\displaystyle 2^{k}\times a-bs<2^{k}}$
         Déterminer la décomposition binaire de ${\displaystyle s}$ et ${\displaystyle 2^{k}\times a-bs}$
         Simplifier les fractions des deux sommes et retourner le résultat
fin-procédure

Ainsi si on veut obtenir un développement égyptien de ${\displaystyle {\frac {2}{5}}}$ on multiplie le numérateur et le dénominateur par ${\displaystyle 8=2^{3}}$ :

${\displaystyle {\frac {2}{5}}={\frac {2\times 8}{5\times 8}}={\frac {16}{40}}={\frac {5\times 2}{40}}+{\frac {6}{40}}={\frac {1}{4}}+{\frac {4+2}{40}}={\frac {1}{4}}+{\frac {1}{10}}+{\frac {1}{20}}}$

Avec cette méthode, le plus grand dénominateur du développement obtenu est inférieur à ${\displaystyle b^{2}}$ et le nombre de terme est de l'ordre de ${\displaystyle \log b}$ termes^[10].

Comparatif

Pour la fraction ${\displaystyle {\frac {3}{16}}}$, les algorithmes précédents donnent les développements égyptiens suivants :

Algorithme	Résultat
Méthode élémentaire	${\displaystyle {\frac {3}{16}}={\frac {1}{16}}+{\frac {1}{17}}+{\frac {1}{18}}+{\frac {1}{272}}+{\frac {1}{273}}+{\frac {1}{306}}+{\frac {1}{74256}}}$
Algorithme de Fibonacci	${\displaystyle {\frac {3}{16}}={\frac {1}{6}}+{\frac {1}{48}}}$
Algorithme de Golomb	${\displaystyle {\frac {3}{16}}={\frac {1}{6}}+{\frac {1}{66}}+{\frac {1}{176}}}$
Algorithme d'Erdős-Bleicher[note 7]	${\displaystyle {\frac {3}{16}}={\frac {1}{10}}+{\frac {1}{15}}+{\frac {1}{48}}}$
Décomposition binaire	${\displaystyle {\frac {3}{16}}={\frac {1}{8}}+{\frac {1}{16}}}$

Les fractions égyptiennes dans la vie courante

Avec ce partage, chacun reçoit la même quantité de gâteau : 1/6 + 1/48 = 3/16.

Les fractions égyptiennes peuvent avoir un intérêt pratique dans la vie courante lorsqu'il s'agit de partager en parts égales une ressource. Prenons l'exemple d'un groupe d'amis qui dispose de trois gâteaux identiques et veut les partager équitablement. Si le groupe est constitué de 15 personnes, la répartition est facile : on coupe chaque gâteau en 5 parts, et chacun reçoit une part. Mais comment faire s'il y a 16 convives?

Il y a plusieurs solutions offertes par les fractions égyptiennes, les plus simples étant :

• couper chaque gâteau en 6, ce qui fait 18 parts ; en distribuer 16, puis couper en 8 les 2 parts restantes et les distribuer. Chaque convive à reçu autant de gâteau, et la distribution correspond à avoir utilisé le développement égyptien 3/16= 1/6+1/48 qui est celui donné par l'algorithme de Fibonacci;
• couper chaque gâteau en 8, ce qui fait 24 parts ; en distribuer 16, puis couper les 8 restantes en 2, et les distribuer. Chaque convive à reçu autant de gâteau, et la distribution correspond à avoir utilisé le développement égyptien 3/16= 1/8+1/16 qui est celui donné par la décomposition binaire.