Find all pairs of positive integers (a,b) such that a!+b!=ab+ba.
Problem
Source: MEMO 2015, problem T-7
Tags: factorial, Diophantine equation, number theory, Exponential equation
randomusername
28.08.2015 22:51
Without loss of generality, a≤b. If a=1, then b!+1=b+1 gives b!=b, which clearly implies b∈{1,2}. The resulting pairs (1,1), (2,1), (1,2) indeed are solutions. From now on, let's assume a,b≥2.
Because of AM-GM, for every integer n≥2, we have
(n!)1/n<1+2+⋯+nn=n+12,
so n!<(n+12)n (equality cannot hold in the estimate).
This shows that if a=b, then a!=aa, while a!<(a+12)a≤aa gives us a contradiction. From now on, assume 2≤a<b.
Now, for b>a≥2,
a!+b!<(a+12)a+(b+12)b≤ba+ab,
if a≥b+12. (Obviously, a+12≤b.) This leaves us the case a≤b2.
In the latter case, let p be some prime divisor of a. Then since 2a is a factor of b!a!, p cannot divide b!a!+1, and thus
vp(a!+b!)=vp(a!)<ap−1≤a,
by Legendre's formula.
On the other hand, taking the equation modulo p gives us p∣ba, so p∣b. Hence, pa divides the RHS, and so vp(a!+b!)≥a. This gives a contradiction.
Hence the solutions are (1,1), (2,1) and (1,2).
gethd
01.09.2015 12:26
a=b⟹a!=aa
⟺a=1
(since 1⋅2⋯a<a⋅a⋯a for a≥2).
Wlog a>b. Two cases:
1) gcd. Let p\mid \gcd(a,b), b=pn.
Then (pm)!+(pn)!=(pm)^{pn}+(pn)^{pm} with m>n.
(See 1st page here for what \upsilon_p(a) means).
\upsilon_p\left((pn)!\right)<\upsilon_p\left((pm)!\right).
\upsilon_p\left(\text{LHS}\right)=\upsilon_p\left((pn)!\right)=\lfloor\frac{pn}{p}\rfloor+\lfloor\frac{pn}{p^2}\rfloor+\cdots
<n+\frac{n}{p}+\cdots
=\frac{pn}{p-1}\le pn\le \upsilon_p\left(\text{RHS}\right)
Contradiction.
2) \gcd(a,b)=1. Let a=b+k, k>0, \gcd(b,k)=1.
(b+k)!+b!=(b+k)^b+b^{b+k}, so
(Binomial theorem may help you see this)
b\mid k^b\iff b=1\implies (a,b)=(2,1).
Answer: \{(1,1),(1,2),(2,1)\} is the set of solutions.
rkm0959
29.08.2016 08:58
If a=b, a!=a^a so (1,1). If a>b, work modulo b. We have b|a^b, so if (a,b)=1, we have b=1 and now a!=a. Therefore, we have (2,1). If gcd(a,b) \not= 1, let p|gcd(a,b). Set a=pu and b=pv. Left. The v_p value is just v_p((pv)!) = \frac{pv-s_p(v)}{p-1}. Right. The v_p value of (pu)^{pv} + (pv)^{pu} is at least pv. Clearly, \frac{pv-s_p(v)}{p-1} < \frac{pv}{p-1} \le pv, so the v_p of both sides are different. yay So (1,1),(2,1),(1,2)
reveryu
13.01.2017 01:58
@randomusername what about v_p(a!+b!)= a (p=2) then a=2^k
MathematicalArceus
13.10.2024 21:19
The answers are (1,1),(1,2),(2,1).
Me
We are given:
a!+b! = a^b+b^a
using \pmod{b} gives us that b^a \equiv 0 \pmod{a} which gives us p \mid b \implies p \mid a. Now let p \mid b be a prime. We by the properties of \nu_p get:
\nu_p(a!+b!) \le \frac{b}{p-1} \le b \le \nu_p(a^b+b^a)
which means \nu_p(b!) = b \implies b is a prime or 1. Putting it back yields the results stated above.
L_13832
For a,b\leq 2 we have \boxed{(a,b)=(1,1),(2,1),(1,2)}.
WLOG a>b>2, so we have b\mid a^b, now take p such that p\mid b.
The LHS can be simplified to \left(\frac{a!}{b!}+1\right)b!, also because p\mid a we get p\mid \frac{a!}{b!}, these 2 conditions inturn give us that p\mid b\implies p\mid a.
Due to all this simplification all we need to check is \nu_p(b!) which is less than \frac{b}{p-1}<b.
Looking at the RHS we have \nu_p{(a^b+b^a)}\geq b, so we have a contradiction.
The ideas are similar but the mode of execution is different