Exercice 1 — Énoncé — Olympiades 2010 Lyon

Sujet

Algorithme et fractions égyptiennes

Soit \(a\) et \(b\) deux nombres entiers strictement positifs. Il existe un unique couple ( \(q ; r\) ) tel que :

\[ \left\{\begin{array}{l} a=b q+r \\ 0 \leqslant r

\(q\) s'appelle le quotient de \(a\) par \(b\); on le note \(E\left(\frac{a}{b}\right)\).
\(r\) s'appelle le reste de la division de \(a\) par \(b\); on le note \(\bmod (a, b)\).
On appelle fraction égyptienne une fraction de la forme \(\frac{1}{n}\) avec \(n \in \mathbf{N} *\). Le but de ce problème est de prouver que tout nombre rationnel compris entre 0 et 1 se décompose en la somme de fractions égyptiennes dont les dénominateurs sont tous distincts, et de trouver une telle décomposition.

Vérifier que

\[ \frac{4}{5}=\frac{1}{2}+\frac{1}{4}+\frac{1}{20} \]

(a) Quelle est la plus grande fraction égyptienne \(\frac{1}{n}\) plus petite que \(\frac{4}{5}\) ?
(b) Démontrer que \(n=E\left(\frac{5}{4}\right)+1\).
(c) Quelle est la plus grande fraction égyptienne \(\frac{1}{m}\) plus petite que \(\frac{4}{5}-\frac{1}{2}\) ?
(d) Retrouver alors la décomposition de la première question.
On suppose que \(1

\[ \frac{x}{y}=\frac{1}{E\left(\frac{y}{x}\right)+1}+\frac{x-\bmod (y, x)}{y \times\left(E\left(\frac{y}{x}\right)+1\right)}(F) \]

(a) En utilisant la formule précédente, décomposer \(\frac{2}{3}\) en somme de deux fractions égyptiennes.
(b) Décomposer \(\frac{5}{7}\) en somme de trois fractions égyptiennes.
4. (a) Démontrer que la formule ( \(F\) ) permet de décomposer toute fraction \(\frac{x}{y}\) avec \(1 (b) Démontrer que toutes les fractions égyptiennes ainsi trouvées sont distinctes.