$a!b!$ multiple of $a! + b!$ implies $3a\geq 2b + 2$

Question

A colleague asked me to show that if $a,b\in\mathbb{N}^*$ are such that $a!b!$ is a multiple of $a! + b!$, then $3a\geq 2b + 2$.

While I could verify this inequality numerically for many solutions $(a,b)$, I did not find anything relevant mathematically. I must say I have never faced such inequalities in arithmetic... The problem is symmetric in $a$ and $b$, and actually I could see that the solutions where all such that $3a\geq 2b + 2$ and $3b\geq 2a + 2$.

Here is a plot of the first solutions $(a,b)$ and the bounds:

The solutions can be generated with the Mathematica code:

Table[If[IntegerQ[a!*b!/(a! + b!)], {a, b}, 
 Unevaluated[Sequence[]]], {a, 1, 100}, {b, 2, 100}]

Answer 1

Assume wlog. that $b\ge a$. Then both $a!b!$ and $a!+b!$ are divisible by $a!$ and $a!+b!\mid a!b!$ implies $1+\frac{b!}{a!}\mid b!$. For $a<k\le b$, $1+\frac{b!}{a!}$ is coprime to $k$. We conclude that $1+\frac{b!}{a!}\mid a!$.

For $1\le k\le b-a$, $k$ has a multiple $qk$ with $a<qk\le b$, hence is again coprime to $1+\frac{b!}{a!}$. We conclude $1+\frac{b!}{a!}\mid \frac{a!}{(b-a) !}$, in particular $$\tag1\frac{b!}{a!}< \frac{a!}{(b-a) !}.$$ By comparing the not cancelled factors in $(1)$ with $a$, we obtain $$ a^{b-a}<a^{2a-b}$$ and hence (for $a>1$) $$\tag2 2b<3a.$$

To improve this, observe that one of $b-a+1, b-a+2$ is not prime (or we are in the trivial case $b=a+1$), hence can be written as product of numbers $<b-a$ and is once again coprime to $1+\frac{b!}{a!}$. This allows us do divide off one more factor on the right of $(1)$, thus leading to $2b<3a-1$ and hence $$ 2b+2\le 3a.$$

Answer 2

$a>b$ implies triviality so let's assume $b>a$. Let $b=a+m$.

We will prove by contradiction by assumes

$$2a+2m+2>3a\implies a < 2m+2 \implies a -m \leq m+1$$

Now

$${a!a!\over a!+a!(a+1)...(a+m)}={a!\over 1+(a+1)...(a+m)}=r$$

$$a!=r+(a+1)...(a+m)$$

Note that ${a\choose m}={a!\over m!(a-m)!}$ so $m!$ | $(a+1)...(a+m)$

(Note: it is the case that $m<a$ because otherwise $r < 1$ and cannot be an integer)

Also because $m!|a!$ we have $m!|r$ so $r >=m!$

Now

$${a!\over 1+(a+1)...(a+m)}=r >=m!$$

$$a! >=m!+m!(a+1)...(a+m)$$

$$(m+1)(m+2)...(a-1)a >=1+(a+1)...(a+m)$$

Note there are $a-m$ numbers on the left and $m$ number on the left.

(1) If $a -m <= m$ then contradiction is proven

(2) If $a-m = m + 1$ then $a = 2m+1$

$$(m+1)(m+2)...(2m)(2m+1) >=1+(2m+2)...(3m+1)$$

Note that we can prove

$${(m+1)(m+2)...(2m+1)\over(2m+2)(2m+3)...(3m)(3m+1)} < 1$$

hence contradiction.

The proof by induction for $m\geq4$:

Base case:

$${5\cdot6\cdot7\cdot8\cdot9\over10\cdot11\cdot12\cdot13} = 0.88 < 1$$

Induction step:

$${(m+2)...(2m+3)\over(2m+4)...(3m)(3m+4)} $$ $$= {(m+1)(m+2)...(2m+1)\over(2m+2)(2m+3)...(3m)(3m+1)}\cdot {(2m+2)^2(2m+3)^2\over(m+2)(3m+2)(3m+3)(3m+4)}<1\cdot1 < 1$$

Notice the polynomial is true because the first coefficient of $m^4$ is $16$ on top and $27$ in bottom. And plug in $m=4$ works so any $m\geq4$ works.

For cases $m\leq 3$ we know ${3a-2\over 2} < b \leq a+3 \implies 2a+6 > 3a-2 \implies a < 8$ so there is only a small finite number of cases to check.

Answer 3

This problem is $2015$ IMO Shortlist Number theory N$2$. Two solutions can be found here on page $66$.

Some solutions can be found, e.g., here on Art of Problem Solving.