Determine all pairs $ (x,y)$ of positive integers satisfying the equation \[ x!+y!=x^{y}.\]
Problem
Source: MEMO Individual Competition, Question 4
Tags: induction, number theory proposed, number theory
25.09.2007 02:46
i think this is the unique solution, but dont have a good proof. $ 2!+2!=2^{2}$ , $ 2!+3!=2^{3}$
25.09.2007 03:10
Image not found
25.09.2007 17:15
Case 1: $ x,y\in\{1,2\}$ Clearly $ x=1 , y=1$ produce no solution. $ x=2$ yields $ y>1$ and from $ 1+\frac{y!}{2}=2^{y-1}$ we determine the solutions $ y\in\{2,3\}$, since for $ y>3$ the LHS is odd. The remaining case $ y=2$ gives $ x!+2=x^{2}$, i.e. division by $ x$ is only possible for $ x\in\{1,2\}$, which has been covered. Case 2: $ 2<x\leq y$ From $ (x-1)!\left(1+\frac{y!}{x!}\right)=x^{y-1}$ we see that $ (x-1)!$ divides $ x^{y-1}$. Therefore, $ x$ cannot be a prime and all prime divisors $ \{p_{i}\}_{i\in I}$ smaller than $ x$ must divide $ x$. Since $ 1+\prod_{i\in I}p_{i}$ is again a prime, we conclude $ x=\prod_{i\in I}p_{i}$. Hence, any $ p_{i}$ can only occur with multiplicity 1 in $ (x-1)!$ and we must have $ 1=1+\frac{y!}{x!}$, a contradiction. Case 3: $ 2<y< x$ From the original equation we know that all prime divisors of $ x$ must divide $ y!$ On the other hand, we have $ y!\left(1+\frac{x!}{y!}\right)=x^{y}$, in particular, all prime divisors of $ y!$ divide $ x$, i.e. $ x,y!$ have all their prime divisors $ \{q_{j}\}_{j\in J}$ in common, but $ 1\not=1+\frac{x!}{y!}\equiv 1\bmod q_{j}$, i.e $ x$ must be divisible by additional prime divisors, a contradiction.
25.09.2007 19:28
Assume $ x = y$. Than, $ 2x! = x^{x}$. We can easyly prove using induction that if $ x > 2$, $ 2x! < x^{x}$. If $ x\leq 2$, $ x = y = 2$. Assume $ x > y$. Again we can prove by induction that $ x!+y! < x^{y}$. Let $ x < y$. $ x!(1+\frac{y!}{x!}) = x^{y}$, or $ (x-1)!(1+\frac{y!}{x!}) = x^{y-1}$. As $ y > x$, $ y!$ is divisble by $ x!$. So, $ x^{y-1}$ is divisible by $ (x-1)$, but as $ gcd(x;x-1)=1$, $ gcd(x^{y-1};x-1) = 1$. It follows that $ x = 2$. $ 2+y! = 2^{y}$. If $ y\leq 3$, $ y = 3$. If $ y\geq 4$, we can easyly prove that $ 2+y! > 2{y}$. So, the only solutions are the pairs $ (x,y) = (2,2)$ and $ (x,y) = (2,3)$.
25.09.2007 21:45
i had a bit different aproach. u find the solutions $ (2,2)$ and $ (2,3)$ and than assume $ x,y > 2$ which means that $ x$ has to bo even $ x = 2a$ now if $ x\leq y$ than $ x-1|x!+y!$ but $ x-1$ clearely isn't a devisor of $ x^{y}$ for $ x > 2$ what leads to contradiction so assume $ x > y$ lemma: let $ p$ be the largest prime number such that $ p\leq n$. than $ p|n!$ but $ p^{2}$ doesn't devide $ n!$ proof: follows by induction from Berdtrand's postulate (there is a prime number p such that $ n < p < 2n$ for every $ n > 1$ let $ q$ be the largest prime nubmer smaller or equal to $ y$ or in other words the largest prime devisor of $ y!$ if $ q > a$ we come to contradiction since $ q|x!+y!$ while $ q$ doesn't devide $ x^{y}$ because $ x$ and consequently $ x^{y}$ cannot have a prime devisor larger than $ a$ if $ q\leq a$ than $ 2q\leq2a = x$ and by using the lemma we can conclude that $ q|y!$ while $ q^{2}|y!$ isn't true and that $ (x(x-1)...(y+1)+1)=1 modq$ since one of numbers $ x,x-1,...y+1$ has to devide q. this means that $ q|x!+y!$ while $ q^{2}|x!+y!$ isn't true what leads to conclusion that $ q|x^{y}$ and since $ q$ is a prime number $ q^{y}|x^{y}$ where $ y > 2$ which is imposible because $ q^{2}$ doesnt devide $ x!+y! = x^{y}$. contradiction.
25.09.2007 23:13
I also solved it with Bertrand (it's quite straight-forward imho)... Lets assume that $ x,y\geq 2$ because all other cases are boring. Let $ p$ be the largest prime number $ \leq\min(x,y)$. Then by Bertrand's postulate, $ \min(x,y) < 2p$. Since $ p\leq x$ and $ p\leq y$, we have that $ p\mid x!+y!$ and thus $ p\mid x$. If $ x\geq 2p$, then we must also have $ y\geq 2p$ (since otherwise $ p^{2}\nmid x!+y!$ but $ p^{2}\mid x^{y}$), contradicting $ \min(x,y)<2p$. Thus, $ x < 2p$ and hence, $ x = p$. However, since $ x,y\geq 2$, $ x!+y!$ and hence also $ x$ are even, so $ x = 2$ and thus, $ y! = 2(2^{y-1}-1)$, so $ y\leq 3$. It follows that the only solutions are $ (2,2)$ and $ (2,3)$.
26.09.2007 11:48
Ok. Very nice solution.
27.09.2007 17:41
Jure the frEEEk wrote: so assume $ x > y$ lemma: let $ p$ be the largest prime number such that $ p\leq n$. than $ p|n!$ but $ p^{2}$ doesn't devide $ n!$ proof: follows by induction from Berdtrand's postulate (there is a prime number p such that $ n < p < 2n$ for every $ n > 1$ let $ q$ be the largest prime nubmer smaller or equal to $ y$ or in other words the largest prime devisor of $ y!$ if $ q > a$ we come to contradiction since $ q|x!+y!$ while $ q$ doesn't devide $ x^{y}$ because $ x$ and consequently $ x^{y}$ cannot have a prime devisor larger than $ a$ if $ q\leq a$ than $ 2q\leq2a = x$ and by using the lemma we can conclude that $ q|y!$ while $ q^{2}|y!$ isn't true and that $ (x(x-1)...(y+1)+1) = 1 modq$ since one of numbers $ x,x-1,...y+1$ has to devide q. this means that $ q|x!+y!$ while $ q^{2}|x!+y!$ isn't true what leads to conclusion that $ q|x^{y}$ and since $ q$ is a prime number $ q^{y}|x^{y}$ where $ y > 2$ which is imposible because $ q^{2}$ doesnt devide $ x!+y! = x^{y}$. contradiction. actually we dont even need all this at all if $ x>y$ than $ x!+y!=y!(x(x-1)...(y+1)+1)$ and obiously $ gdc(x(x-1)...(y+1)+1,x)=1$ therefore $ x(x-1)...(y+1)+1$ cant devide $ x^{y}$
27.11.2011 08:02
if$y\ge x$then$x!|x^y$ hence all prine divisors of $x!$ are that of x,but by Bertrand theorem,when $x>2$there is a prime between p between x and $\frac{2}{x}$thenp|x!,but p|x,contradiction. so $x=1 or 2$yielding solutions $(2,2)(2,3)$ otherwice y<x.then all prime solutions of y! are divisors of x.then$y\le\frac{x}{2}$(otherwice,(\frac{x}{2}+1 or \frac{x+1}{2},x)=1$,contradiction!) but then it's easy to prove $x!+y!>x^y$(actually,x!>x^{\frac{x}{2}}).contradiction.