Theorem: Condition for 3 over n producing 3 Egyptian Fractions using Greedy Algorithm when 2 Sufficient

Consider proper fractions of the form $\dfrac 3 n$ expressed in canonical form.
Let Fibonacci's Greedy Algorithm be used to generate a sequence $S$ of Egyptian fractions for $\dfrac 3 n$.
Then $S$ consists of $3$ terms, where $2$ would be sufficient {{iff}} the following conditions hold:
:$n \equiv 1 \pmod 6$
:$\exists d: d \divides n$ and $d \equiv 2 \pmod 3$

Proof:
By Upper Limit of Number of Unit Fractions to express Proper Fraction from Greedy Algorithm, $S$ consists of no more than $3$ terms.
Suppose $n$ has our desired property.
Since $\dfrac 3 n$ is proper, $n \ge 4$.
Since $\dfrac 3 n$ is in canonical form, $3 \nmid n$.
We also have that $S$ consists of at least $2$ terms.
Consider the case $n = 3 k - 1$.
:$\dfrac 3 n = \dfrac 1 k + \dfrac 1 {k \paren {3 k - 1} } \quad$ as $\ceiling {\dfrac n 3} = \ceiling {k - \dfrac 1 3} = k$
Fibonacci's Greedy Algorithm produces $2$ terms only.
hence it must be the case that $n = 3 k - 2$.
{{qed|lemma}}
We have:
:$\dfrac 3 n = \dfrac 1 k + \dfrac 2 {k \paren {3 k - 2} } \quad$ as $\ceiling {\dfrac n 3} = \ceiling {k - \dfrac 2 3} = k$
If $k$ is even, $\dfrac 1 {\paren {k / 2} \paren {3 k - 2} }$ is an Egyptian fraction.
Then Fibonacci's Greedy Algorithm would produce $2$ terms only.
hence it must be the case that $k$ is odd.
This happens {{iff}} $n$ is odd.
{{qed|lemma}}
We have shown that for Fibonacci's Greedy Algorithm to produce $3$ terms, $n$ must be odd and $n = 3 k - 2$.
By Chinese Remainder Theorem, these conditions can be merged into:
:$n \equiv 1 \pmod 6$
We need find when Fibonacci's Greedy Algorithm gives minimum terms.
Write:
{{begin-eqn}}
{{eqn | l = \frac 3 n
      | r = \frac 1 x + \frac 1 y
}}
{{eqn | r = \frac {x + y} {x y}
}}
{{end-eqn}}
Since $\dfrac 3 n$ is in canonical form, $x y \divides n$.
By Divisor of Product, we can find $p, q \in \N$ such that:
:$p \divides x$, $q \divides y$
:$p q = n$
Rewrite:
{{begin-eqn}}
{{eqn | l = \frac 3 n
      | r = \frac 1 {p a} + \frac 1 {q b}
}}
{{eqn | r = \frac {q b + p a} {p q a b}
}}
{{eqn | ll= \leadsto
      | l = p a + q b
      | r = 3 a b
}}
{{eqn | ll= \leadsto
      | l = p
      | r = \frac {b \paren {3 a - q} } a
}}
{{end-eqn}}
If $\exists d: d \divides n$ and $d \equiv 2 \pmod 3$, set $q = 1$ and $a = \dfrac {d + 1} 3$.
Then $p = n$ and $b = \dfrac {a n} {3 a - 1} = \dfrac {n \paren {d + 1} } {3 d}$, which is a solution:
:$\dfrac 3 n = \dfrac 3 {n \paren {d + 1} } + \dfrac {3 d} {n \paren {d + 1} }$
{{qed|lemma}}
Now suppose $d$ does not exist.
Then any divisor of $n$ is equivalent to $1 \pmod 3$.
Hence $q \equiv 1 \pmod 3$.
Thus $3 a - q \equiv 2 \pmod 3$.
Let $r = \gcd \set {3 a - q, a}$.
We have:
:$a \divides b \paren {3 a - q} = b r \paren {\dfrac {3 a - q} r}$
Thus:
:$\dfrac a r \divides b \paren {\dfrac {3 a - q} r}$
By Integers Divided by GCD are Coprime:
:$\dfrac a r \perp \dfrac {3 a - q} r$
Finally, by Euclid's Lemma:
:$\dfrac a r \divides b$
Hence $\dfrac {3 a - q} r, \dfrac {b r} a \in \Z$, and $p = \paren {\dfrac {3 a - q} r} \paren {\dfrac {b r} a}$.
Thus we also have:
:$\dfrac {3 a - q} r \divides p \divides n$
:$r = \gcd \set {q, a} \divides q \divides n$
Hence:
:$\dfrac {3 a - q} r \equiv 1 \pmod 3$
:$r \equiv 1 \pmod 3$
Taking their product:
{{begin-eqn}}
{{eqn | l = 3 a - q
      | r = \frac {3 a - q} r \times r
}}
{{eqn | o = \equiv
      | r = 1 \times 1
      | rr = \pmod 3
}}
{{eqn | o = \equiv
      | r = 1
      | rr = \pmod 3
}}
{{end-eqn}}
which is a contradiction.
Therefore $n$ cannot be expressed as the sum of $2$ Egyptian fractions.
Hence the result.
{{qed}}
Category:Fibonacci's Greedy Algorithm
Category:Egyptian Fractions
lkbiny67byhfdimpr3o1qt6xwno8ec4