Prove that the function $f : \mathbb{N}\longrightarrow \mathbb{Z}$ defined by $f(n) = n^{2007}-n!$, is injective.
Problem
Source: Romanian TST 4 2007, Problem 1
Tags: function, inequalities, floor function, factorial, number theory proposed, number theory
20.06.2007 06:34
f is injective if f(a) = f(b) implies a = b Suppose $n^{2007}-n!=m^{2007}-m!$ and $n\geq m+1$ Then $n^{2007}-m^{2007}=m!\left(n\cdot(n-1)\cdots (m+1)+1\right)$ It only remains to show that this solution under the constraints has no solutions, which is intuitively obvious. Indeed, this implies $n^{2007}=am!+m^{2007}$. Clearly, we only need to investigate when $m$ is prime Thus $n^{2007}=p[a(bp-1)+p^{2006}]$ for some $a,b$ natural by Wilson's So $n=cp$ and with bounding there is gross inequality so solution (Wilson's is unecessary )
20.06.2007 09:45
me@home sorry but I think that the only you proved is that m and n have the same prime divisors , which in fact is trivial .
20.06.2007 22:41
Could smeone post a complete solution? Even if this was the first problem it proved to be almost 'the hardest' of the paper. It was a tricky one and most of us were tented to spend a lot of time on it.
22.06.2007 16:37
This problem is from BMO'07 shortlist (proposed by Serbia). Here is the complete solution: Suppose that for some $x>y$ we have $x^{2007}-x!=y^{2007}-y!$. We shall distinguish two cases: First case: $y\leq 2007$. There are no solutions for $y=1$: indeed, the equation becomes $x^{2007}=x!$; since $\gcd(x-1,x^{2007})=1$, we must have $x=2$ which is impossible. Thus, we assume $y>1$. Let $\mbox{d}_{p}(n)$ denote the greatest degree of $p$ dividing $n$. Rewrite the given equation as $x\,!-y\,!=x^{2007}-y^{2007}$ and consider any prime divisor $q$ of $y$. Since $q$ divides $x\,!$ and $y\,!$, it must divide $x^{2007}$, so $q\mid x$. Thus $\mbox{d}_{q}(x\,!)> \mbox{d}_{q}(y\,!)$, which implies $\mbox{d}_{q}(x\,!-y\,!)= \mbox{d}_{q}(y\,!)$. On the other hand, we have $q^{2007}\mid x^{2007}-y^{2007}$, so we must have $2007\leq \mbox{d}_{q}(y\,!)$ whenever $q\mid y$. However, this is impossible since $\mbox{d}_{q}(y\,!)=\left\lfloor\frac{y}{q}\right\rfloor+\left\lfloor\frac{y}{q^{2}}\right\rfloor+\ldots<y\leq 2007.$ Second case: $x,y\geq 2007$. Every prime $p$ less than $2007$ divides $x^{2007}-y^{2007}$. Now if $\gcd(p-1,2007)=1$, there is a positive integer $r$ such that $2007r\equiv1$ (mod $p-1$). Therefore $x\equiv x^{2007r}\equiv y^{2007r}\equiv y$ (mod $p$), i.e. $p\mid x-y$ whenever $p$ is a prime and $\gcd(p-1,2007)=1$. In particular, this holds for $p=1997$ or $2003$ (which are prime); hence $x-y\geq 1997\cdot 2003$, so $x-y>2007$. But we now have $x\,!-y\,!> \left(x(x-1)\cdots(x-2007)-1\right)y\,!> x(x-1)\cdots (x-2006)\cdot 2007\,!>x^{2007},$ where the last inequality follows from the inequalities $(x-k)(k+1)\geq x$ for $k=0,\dots,2006$. We reached a contradiction again.
22.06.2007 18:35
Thank you for the solution . Very nice problem . Could you post the Shortlist of the BMO 2007 ?
23.06.2007 18:06
silouan wrote: Thank you for the solution . Very nice problem . Could you post the Shortlist of the BMO 2007 ? I don't have it. I just know problems proposed by Serbia.
29.08.2009 17:31
28.12.2009 18:26
Oops, change the second to last sentence to this
08.01.2011 20:42
Goblin wrote: $\mbox{d}_{q}(x\,!)> \mbox{d}_{q}(y\,!)$, which implies $\mbox{d}_{q}(x\,!-y\,!)= \mbox{d}_{q}(y\,!)$.On the other hand, we have $q^{2007}\mid x^{2007}-y^{2007}$, so we must have $2007\leq \mbox{d}_{q}(y\,!)$ whenever $q\mid y$. Second case: $x,y\geq 2007$. Every prime $p$ less than $2007$ divides $x^{2007}-y^{2007}$. Now if $\gcd(p-1,2007)=1$, there is a positive integer $r$ such that $2007r\equiv1$ (mod $p-1$). Therefore $x\equiv x^{2007r}\equiv y^{2007r}\equiv y$ (mod $p$), i.e. $p\mid x-y$ whenever $p$ is a prime and $\gcd(p-1,2007)=1$. In particular, this holds for $p=1997$ or $2003$ (which are prime); hence $x-y\geq 1997\cdot 2003$, so $x-y>2007$. But we now have $x\,!-y\,!> \left(x(x-1)\cdots(x-2007)-1\right)y\,!> x(x-1)\cdots (x-2006)\cdot 2007\,!>x^{2007},$ where the last inequality follows from the inequalities $(x-k)(k+1)\geq x$ for $k=0,\dots,2006$. We reached a contradiction again. Anyone who can explain?
06.09.2012 05:10
Ah!! a nice problem..... Suppose $f(x) = f(y)$, with $x>y$. First we discuss the case $y<2008$ Clearly, there are no solutions for $y = 0$ or $y = 1$, so assume $y>1$. Denote by $v_p(n)$ the exponent of the prime $p$ in the factorization of n. For $x!-y! = x^{2007}-y^{2007}$, and $q$ a prime divisor of $y$, it must be that $q$ divides $x$. Thus $v_q (x!)>v_q (y!)$, hence $v_q(x! - y!) = v_q(y!)$. On the other hand, we have $q^{2007}|x^{2007} - y^{2007}$, so we must have $2007\leqq_q(y!)$. However, this is impossible, since $v_q(y!) =<\frac {y}{a-1}\leq2007.$ For the case $y > 2007$, every prime $p < 2007$ divides $x! - y! = x^{2007} - y^{2007}$. If $gcd(p-1,2007)=1$, there exists a positive integer $r$ such that $2007r = 1 (mod p - 1)$. Therefore, $x = x^{2007 r} = y^{2007r} = y (mod p)$==> $p|x - y$. In particular, this holds for $p = 23$ and $101$, hence $x - y \geq23 . 101 = 2323 > 2008.$ But then we have $x! - y! > (x(x - 1) . . . (x - 2007) - 1)y! > x(x - 1) . . . (x - 2006) . 2007! > x^2007$ , where the last inequality follows from $(x - k)(k + 1) > x,$ for $k = 1,2,.. . ,2006,$ A contradiction.
26.08.2022 00:06
Quote: Solve in positive integers $x^{2007}-y^{2007}=x!-y!.$ Claim: The answer is all $(x,y)$ such that $x=y,$ which is easily verified. Proof: Without loss of generality, let $x>y.$ We consider two cases, when $y \leq 2007$ and when $y >2007.$ For the former, when we have $y=1$ then $x^{2007}=x!,$ from which it is obvious that $x=1.$ For $y>1$ consider a prime $p$ such that $p \mid y.$ Then from $x>y$ we have $p \mid y!, y^{2007}, x!.$ Taking the equation $\pmod{p}$ implies $p \mid x^{2007},$ so $p \mid x.$ It follows \[\nu_p(x^{2007}-y^{2007})=\nu_p(x!-y!)=\nu_p\left(y!(\tfrac{x!}{y!}-1)\right)=\nu_p(y!)+\nu_p\left(\tfrac{x!}{y!}-1\right).\]Furthermore, notice $\tfrac{x!}{y!}=x(x-1)\cdots(y+1)\equiv 0 \pmod{p},$ so the last equation above is equal to $\nu_p(y!).$ It is easy to see $2007 \leq \nu_p(x^{2007}-y^{2007}),$ so we have the inequality $2007 \leq \nu_p(y!).$ However, notice then by Legendre's Formula \[2007 \leq \nu_p(y!)=\sum_{i=1}^{\infty} \left \lfloor \frac{y}{p^i} \right\rfloor<\sum_{i=1}^{\infty} \frac{y}{p^{i}}=\frac{y/p}{1-1/p}=\frac{y}{p-1} \leq y,\]contradicting the original assumption of $y\leq 2007.$ Thus there are no other solutions in this case. It suffices now to consider $y>2007.$ Note there is a factor of $y!$ in the right hand side of the equation, so $x^{2007}-y^{2007}$ has a factor of $y!,$ that is, all primes $p<2007$ divide into $x^{2007}-y^{2007}.$ Consider primes $p<2007$ satisfying $\gcd(p-1, 2007)=1.$ Either we have $p \mid x$ or $p \nmid x.$ For the former case, we obviously have $p \mid y,$ from the established conditions. For the latter, by Fermat's Little theorem, $x^{p-1} \equiv 1 \pmod{p}.$ Taking the original equation $\pmod{p},$ it follows $x^{2007} \equiv y^{2007} \pmod{p},$ and since $p \nmid x,$ we must also have $p \nmid y.$ Applying Fermat's Little Theorem again gives $y^{p-1} \equiv 1 \pmod{p}.$ Hence $x^{p-1}-y^{p-1} \equiv 0 \pmod{p}.$ Recall the following well known lemma: Lemma: For integers $a>b>0$ satisfying $\gcd(a,b)=1,$ we have \[\gcd(a^m-b^m, a^n-b^n)=a^{\gcd(m,n)}-b^{\gcd(m,n)},\]for integers $0 \leq m<n.$ Proof: An argument employing iteration of the Euclidean Algorithm finishes. With this lemma in mind, we return to the original problem. As $\gcd(p-1, 2007)=1,$ it follows \[\gcd(x^{2007}-y^{2007}, x^{p-1}-y^{p-1})=x-y.\]Furthermore $p$ divides both $x^{2007}-y^{2007}$ and $x^{p-1}-y^{p-1},$ and since their $\gcd$ is $x-y,$ it follows $p \mid x-y$ in this case as well. Therefore, every prime $p<2007$ satisfying $\gcd(p-1, 2007)=1$ divides into $x-y.$ In particular, we see $p=23$ and $p=2003$ are primes that divide into $x-y,$ so $x-y \geq 23 \cdot 2003 >2007.$ Hence $x>y+2007.$ However, this implies \begin{align*} x!-y!=y!(\tfrac{x!}{y!}-1)&>y!(x(x-1)\cdots(x-2007)-1) \\ &>2007!(x(x-1)\cdots(x-2007)-1) \\ &>2007!x(x-1)\cdots(x-2006). \end{align*}We now prove that for every $n \in [1,2006],$ we have $(x-n)(n+1)>x.$ Indeed, expanding the inequality gives $xn+x-n^2-n>x,$ so $xn>n^2+n=n(n+1),$ so $x>n+1,$ which is obvious. Therefore, the inequality reduces to $x!-y!>x^{2007},$ a contradiction. After exhausting all cases, the only solutions must be $x=y.$
12.08.2024 18:56
I think this works