<s>[INST] Fractions in Ancient Egypt In ancient Egypt, fractions were written as sums of fractions with numerator 1. For instance,$ \frac{3}{5}=\frac{1}{2}+\frac{1}{10}$. Consider the following algorithm for writing a fraction $\frac{m}{n}$ in this form$(1\leq m < n)$: write the fraction $\frac{1}{\lceil n/m\rceil}$ , calculate the fraction $\frac{m}{n}-\frac{1}{\lceil n/m \rceil}$ , and if it is nonzero repeat the same step. Prove that this algorithm always finishes in a finite number of steps.
Note:if $ n\in \mathbf{Z} $ and $n-1<x\leq n ,  \lceil x\rceil=n$
 [/INST] We proceed by induction on $m\in \Bbb{N}$.
Base Case: When $m=1$, $\dfrac{m}{n}$ is already in the desired form, so terminate.
Induction Hypothesis: Assume that for all $m \in \{1,...,k\}$ (where $k \geq 1$), the algorithm will terminate when its input is $\dfrac{m}{n}$.
It remains to prove the claim true for $m=k+1$. After one step of the algorithm, we obtain the new fraction:
$$
\dfrac{k+1}{n}-\dfrac{1}{\left\lceil \frac{n}{k+1} \right\rceil}
= \dfrac{\left\lceil \frac{n}{k+1} \right\rceil(k+1)-n}{\left\lceil \frac{n}{k+1} \right\rceil n}
$$
Now observe that:
$$ \begin{align*}
\left\lceil \frac{n}{k+1} \right\rceil(k+1)-n
&= \left( \left\lfloor \frac{n-1}{k+1} \right\rfloor+1 \right)(k+1) -n \\
&\leq \left( \frac{n-1}{k+1} +1 \right)(k+1) -n \\
&= (n-1)+(k+1) -n \\
&= k
\end{align*} $$
Hence, by the induction hypothesis, the algorithm must terminate. This completes the induction.
</s>