Is this Egyptian fractions algorithm the same as the greedy algorithm? How to prove it?

Question

I was thinking about possible new algorithms for Egyptian fractions expansion. We know that for any $p,q,m>0$:

$$\frac{p}{q}>\frac{p}{q+m}$$

Here we assume $p<q$ and are coprime.

Now it would make sense to find the smallest $m$ such that:

$$\mod(q+m,p)=0$$

Then we represent the initial fraction as:

$$\frac{p}{q}=\frac{p}{q+m}+\frac{pm}{q(q+m)}$$

Getting everything in lowest terms we obtain:

$$\frac{p_0}{q_0}=\frac{1}{a_0}+\frac{p_1}{q_1}$$

Here $a_0=(q_0+m_0)/p_0$ (an integer) and we repeat the process for $p_1$ and $q_1$.

---

Experimenting with Mathematica (and pen and paper of course) I noticed a very curious fact - this algorithm gives the exact same expansions as the greedy algorithm! But why? And if it's true, how do we prove it?

Here is the Mathematica code I used. To speed up the process for large denominators and numerators I numerically check FractionalPart instead of using Mod, so far there were no errors related to this approximation.

x=18/23;
p0=Numerator[x];
q0=Denominator[x];
S=0;
While[p0>1&&q0<10^21,
M=Catch[Do[If[FractionalPart[(q0+k)/p0]<10^(-35),Throw[k]],{k,1,q0}]];
p1=Numerator[M p0/(q0(q0+M))];
q1=Denominator[M p0/(q0(q0+M))];
S+=p0/(q0+M);
Print[StandardForm[p0/(q0+M)],"                  ",StandardForm[M p0/(q0(q0+M))],"                  ",M];
p0=p1;
q0=q1]
If[p0==1,S+=p0/q0];
N[(x-S)/x,10]

Answer 1

It is the greedy algorithm. If

$$k-1 < \frac{q}{p} \leqslant k,$$

then $(k-1)p < q \leqslant kp$, and the smallest $m$ such that $q+m \equiv 0 \pmod{p}$ is $kp - q$, thus

$$\frac{p}{q+m} = \frac{p}{kp} = \frac{1}{k}$$

where

$$k = \biggl\lceil\frac{q}{p}\biggr\rceil.$$