Denote by $P(n)$ the greatest prime divisor of $n$. Find all integers $n\geq 2$ for which \[P(n)+\lfloor\sqrt{n}\rfloor=P(n+1)+\lfloor\sqrt{n+1}\rfloor\]
Problem
Source: Baltic Way 2015
Tags: polynomial, algebra, number theory
MathStudent2002
08.11.2015 19:10
If $\lfloor \sqrt n \rfloor = \lfloor \sqrt{n+1}\rfloor$, then $P(n) = P(n+1)$, contradiction, as $\text{GCD}(n,n+1) = 1$.
Thus $\lfloor\sqrt n \rfloor < \lfloor\sqrt{n+1}\rfloor$, or $n+1 = a^2$ for some $a$.
Then $P(a^2-1) = P(a^2)+1$, or $P(a^2-1) = P(a)+1$. But $P(a^2-1) ,P(a)$ are primes, so $P(a^2-1) = 3, P(a) = 2$, so $a$ is a power of $2$, so let $a = 2^m$, we have $$P(4^m-1) = 3$$
But then $P(2^m-1) \le 3, P(2^m+1) \le 3$, and $2\mid 2^m\pm 1$ if and only if $a = 1$, but then $n=0$, which is impossible, thus $2^m-1 = 1, 2^m+1 = 3$, or $m=1$, or $a = 2$, which gives us $\boxed{n=3}$
A-Thought-Of-God
10.11.2020 13:43
Nice Problem.
We divide the solution in several parts:
Case : When $n=k^2,$ we have $$P(k^2)+k=P(k^2+1)+k \Rightarrow k^2\equiv k^2+1 \pmod{p}$$where $p$ is prime, which is a contradiction. $\square$
Case : When $n+1=k^2,$ then $$P(k^2-1)+(k-1)=P(k^2)+k\implies P(k^2-1)=P(k^2)+1$$which means $P(k^2-1),P(k^2-1)-1$ are both prime. Consequently, $$P(k^2-1)=3~\text{and}~ P(k^2)=2 \Rightarrow k=2^i~\text{and}~k^2-1=2^r\cdot 3^s$$where $i\ge 1$ and $s\ge 1,$ notice that this forces $r=0$. Hence $$4^i-1=3^s \implies i=s=1$$which is Catalan's Theorem/Conj. This gives $k=2\Rightarrow n=3$. $\square$
Case : When $n=k^2+\ell$ where $0<\ell<2k$. This gives $$P(k^2+\ell)=P(k^2+\ell+1) \Rightarrow k^2+\ell \equiv k^2+\ell+1 \pmod{q}$$where $q$ is a prime, which is a contradiction. $\square$
Finally, we have only single solution $n=3,$ as desired.
Kimchiks926
12.11.2020 18:41
We begin with rewriting original relation as follows: $$ \lfloor\sqrt{n}\rfloor - \lfloor\sqrt{n+1}\rfloor\ = P(n+1) - P(n) $$It is easy to see that $\lfloor\sqrt{n}\rfloor - \lfloor\sqrt{n+1}\rfloor\ $ is $0$ or $-1$. It can't be $0$, since then we have that $n+1$ and $n$ have the same largest prime divisor of $p$, which implies that $p \mid n+1 - n = 1$,which is clearly contradiction. So we know that $P(n+1)-P(n) = -1$. Observe that it is impossible that both $n$ and $n+1$ has odd largest prime divisor, because the $P(n+1) - P(n)$ is even , which is clearly contradiction. If $P(n) = 2$, then $P(n+1) = 1$, which is clearly impossible. This implies that $n+1 = 2^x$ and that $n = 2^z 3^y$. Observe that $z =0$ thus we are left to solve equation: $$ 3^y+1 = 2^x $$in positive integers. Looking at both sides $\pmod 4$ yields that $x$ is even. This implies that: $$ 3^y = (2^{\frac{x}{2}} -1)(2^{\frac{x}{2}} + 1) $$But this impossible that $2^{\frac{x}{2}} -1$ and $2^{\frac{x}{2}} + 1$ are powers of $3$. Consequently $n=3$ and we are done.
Aimingformygoal
01.06.2021 14:30
Nice problem!
Firstly, the given condition that $P(n)+\lfloor\sqrt{n}\rfloor=P(n+1)+\lfloor\sqrt{n+1}\rfloor \implies n+1$ is a square, this is evident since if $n+1$ is not a square, then $\lfloor\sqrt{n}\rfloor=\lfloor\sqrt{n+1}\rfloor$ which implies $P(n)=P(n+1)$, which is clearly a contradiction.
Thus, $\lfloor\sqrt{n}\rfloor-\lfloor\sqrt{n+1}\rfloor=1 \implies P(n)=P(n+1)+1$. Now, we make two cases to finish the problem.
Case 1 : $n$ is even.
In this case, $n+1$ is odd, thus $P(n+1)$ is odd $\implies P(n+1)+1$ is even. Hence, $P(n)=2 \implies P(n+1)=1$, which is absurd and thus no solution when $n$ is even.
Case 2 : $n$ is odd.
In this case, $P(n)$ is odd $\implies P(n+1)$ is even $\implies P(n+1)=2 \implies n+1=2^m$ for some $m$, but since $n$ is a square $\implies m$ is even. Hence, $P(n)=3$, if and only if $n=3$, since when $m \geq 4$, then $n$ has a prime divisor greater than 3.
Hence, the only solution is $n=3$ $\blacksquare$
hakN
01.06.2021 15:37
It can be checked by hand that for $n\leq 10$, only solution is $n=3$.
Now assume $n \geq 11$.
We have $P(n) - P(n+1) = \lfloor\sqrt{n+1}\rfloor\ - \lfloor\sqrt{n}\rfloor\ \in \{0,1\}$.
Since $\gcd{(n,n+1)} = 1$, it can't be $0$, if it is $1$, then we must have $P(n+1) = 2$ and $P(n) = 3$.
So, $n = 2^k - 1 = 3^m$ for some $k,m\in \mathbb{Z^+}$. Taking mod $3$ we see that $k$ is even and then factoring & checking cases yield $n=3$, we are done.
rafaello
14.08.2021 00:35
Let $\lfloor \sqrt{n}\rfloor =r$, thus $r\leq \sqrt{n}< r+1$. Furthermore we have and $r^2<r^2+1\leq n+1<(r+1)^2+1<(r+2)^2$, thus either $\lfloor \sqrt{n+1}\rfloor =r$ or $\lfloor \sqrt{n+1}\rfloor =r+1$. If $\lfloor \sqrt{n+1}\rfloor =r$, then we must have $P(n)=P(n+1)$, which is impossible, as $n$ and $n+1$ do not share any prime divisors. Thus, we must have $\lfloor \sqrt{n+1}\rfloor =r+1$. Hence, we conclude that $n+1=(r+1)^2$ and our equation takes the following form: $$P(r(r+2))=1+P(r+1)^2).$$Now the only primes that differ by $1$ are $2,3$, we must have $P(r(r+2))=3$ and $P((r+1)^2)=2$. We conclude that $r+1=2^l$ and $r(r+2)=3^s$. Furthermore, $4^l-3^s=1$. By Catalan's conjecture, there are no solutions if $l,s\geq 2$. Therefore, $l=s=1$ and hence $r=1\implies \boxed{n=3}$. We are done.