A positive integer $n$ is called egyptian if there exists a strictly increasing sequence $0<a_1<a_2<\dots<a_k=n$ of integers with last term $n$ such that \[\frac{1}{a_1}+\frac{1}{a_2}+\dots+\frac{1}{a_k}=1.\](a) Determine if $n=72$ is egyptian. (b) Determine if $n=71$ is egyptian. (c) Determine if $n=72^{71}$ is egyptian.
Problem
Source: Italy MO 2024 P3
Tags: number theory, number theory proposed, egyptian fractions
15.05.2024 22:20
Isn’t the sum strictly less than n, for n>1?
15.05.2024 22:29
R8kt wrote: Isn’t the sum strictly less than n, for n>1? No $1/1 + 1/2 + 1/3 ... $ approaches infinity.
15.05.2024 22:35
Tintarn wrote: A positive integer $n$ is called egyptian if there exists a strictly increasing sequence $0<a_1<a_2<\dots<a_k=n$ of integers with last term $n$ such that \[\frac{1}{a_1}+\frac{1}{a_2}+\dots+\frac{1}{a_k}=n.\](a) Determine if $n=72$ is egyptian. (b) Determine if $n=71$ is egyptian. (c) Determine if $n=72^{71}$ is egyptian. In the original problem the sum was \[\frac{1}{a_1}+\frac{1}{a_2}+\dots+\frac{1}{a_k}=1\]
15.05.2024 22:39
(a) $72$ is egyptian as we can take $a_1=2$, $a_2=4$, $a_3=8$, $a_4=9$ and $a_5=72$ and note that \[\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\frac{1}{9}+\frac{1}{72}=1\] (b) Suppose $71$ is egyptian. Then there exist $a_1,\ldots,a_{k-1}$ such that \[\frac{1}{a_1}+\cdots+\frac{1}{a_{k-1}}+\frac{1}{71}=1\iff\frac{1}{a_1}+\cdots+\frac{1}{a_{k-1}}=\frac{70}{71}\]But then 71 divides $\operatorname{lcm}(a_1,\ldots,a_{k-1})$ and since $71$ is prime $71\,|\, a_i$ for some $i$. This is a contradiction as $a_i<71$ for all $i\le k-1$. $\square$ (c) We will prove by induction that $72^k$ is egyptian for all $k$ (actually this can be extended to $x^k$ for any egyptian $x$). $k=1$ follows from point (a). Suppose $72^k$ is egyptian. Then there exist $a_1,\ldots,a_i$ such that \[\frac{1}{a_1}+\cdots+\frac{1}{a_i}+\frac{1}{72^k}=1\qquad\text{(1)}\]Note that \[\frac{1}{72^{k}}\left(\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\frac{1}{9}+\frac{1}{72}\right)=\frac{1}{72^k}\]So we can rewrite (1) as: \[\frac{1}{a_1}+\cdots+\frac{1}{a_i}+\frac{1}{2\cdot 72^k}+\frac{1}{4\cdot 72^k}+\frac{1}{8\cdot 72^k}+\frac{1}{9\cdot 72^k}+\frac{1}{72^{k+1}}=1\]Of course all the new terms will be different from $a_1,\ldots,a_i$ since they are all $>72^k$. This proves that $72^{k+1}$ in egyptian, which closes the induction. $\square$
24.01.2025 03:40
$(a)$ $72$ is egyptian as we can take $a_1=2$, $a_2=3$, $a_3=9$, $a_4=24$ and $a_5=72$ and \[\frac{1}{2}+\frac{1}{3}+\frac{1}{9}+\frac{1}{24}+\frac{1}{72}=1\] $(b)$ Suppose $71$ exists as an increasing sequence such that \[ \sum_{i=1}^k \frac{1}{a_i} = 1. \]At some point, the summation can be written as \[ \frac{71}{71} = \frac{70 + 1}{71} = \frac{70}{71} + \frac{1}{71} = 1. \]The $70$ must be represented as a sum such that the factors of $71$ are involved, since $a_i$ must form a monotonically increasing sequence. However, $71$ has no factors except $1$ and $71$, because $71$ is a prime number. Therefore \[\Rightarrow\Leftarrow\] $(c)$ same as @above