http://www.mathlinks.ro/Forum/viewtopic.php?search_id=1220620362&t=2005

Both solutions there seem wrong to me. Does someone have a correct solution?

See http://www.mathlinks.ro/Forum/viewtopic.php?t=172856

Rust (in that topic) wrote: 1. $ P(x)$ is not decrease, therefore exist $ x$, suth that $ P(x - 1) < P(x)$ (for example x is any odd prime). If $ P(x + 1) > P(x)$ it give solution for one. If $ P(x + 1) < P(x)$ ($ P(x + 1)\not = P(x)$), then $ P(x^2 - 1) < P(x^2)$. If $ P(x^2 + 1) > P(x)$ we have solutione for one $ n = x^2 - 1$. If $ P(x^{2^l} + 1) < P(x) \ \forall l < k$ and ${ P(x^{2^k} + 1} > P(x)$ work $ n = x^{2^k}$. Because odd prime divisor $ P(x^{2^k} + 1) > 2^{k} > x$ if $ k > log_2 x$, then we find suth k for all x. 2. If $ S_k = P(2^k - 1)$ is not monotonik, exist k, suth that $ P(2^{k - 1} - 1) = P(2^k - 2) > P(2^k - 1) > P(2^k) = 2$. Hmm... let me try to understand that. Since $ P(x)$ is not decreasing, there is are infinitely many $ x$ with $ P(x - 1) < P(x)$, obviously (all odd primes). If $ P(x + 1) > P(x)$ then we're done, so assume by contraposition that $ P(x) > P(x + 1)$, so by assumption $ P(x^2 - 1) < P(x^2)$. Again if $ P(x^2 + 1) > P(x)$ we're done, otherwise we have by assumption $ P(x^4 + 1) < P(x) = P(x^4)$. Continuing like that we get either a valid $ n = x^{2^k}$ or we get $ P(x^{2^k} + 1) < P(x)$ for all $ k$. So far I get it. But then you finish the contradiction by claiming $ P(x^{2^k} + 1) > 2^{k}$. Why is this?

If odd prime $ p|x^{2^k}+1$, then (x,p)=1 and minimal period x mod p is $ T_p=2^{k+1}$, therefore $ 2^{k+1}|p-1$ or $ p>2^{k+1}>2^k$.

This was posted in another topic, I thought it was relevant here. mavropnevma wrote: This is grobber's proof from one of the posts in the topics under the link given above. Peter seems to think it's wrong, but with some clarifications I will show it's right. grobber wrote: Let $ p>2$ be a prime, and let $ n_k=p^{2^k}-1$. We have $ P\left(n_k+1\right)=p$. We look at the sequence $ \left(n_k+2\right)\ \left\{k\geq 1\right\}$. We can see that any 2 distinct terms have 2 as their greatest common divisor, because for $ i<j$ we have $ \left(p^{2^j}+1\right)-2 = \left(p-1\right)\left(p+1\right)\left(p^2+1\right) ...\left(p^{2^i}+1\right) ...\left(p^{2^{j-1}}+1\right)$. Since none of the terms of the sequence considered is divisible by 4, it means that the sequence $ P\left(n_k+2\right)$ contains arbitrarily large primes. Let $ k$ be the smallest integer for which $ P\left(n_k+2\right) > p$. Since $ n_k=\left(p-1\right)\cdot\left(p+1\right)\cdot n_1\cdot n_2\cdot ...\cdot n_{k-1}$ and all prime divisors of the number on the right are $ <p$, it means that $ P\left(n_k\right)<p=P\left(n_k+1\right)<P\left(n_k+2\right)$, and such a number $ n_k$ can be found for any prime $ p$. Let me first state Kobayashi's Theorem: If the set of prime divisors of the terms of an unbound sequence $(a_n)_{n\geq 1}$ is finite, then the set of prime divisors of the terms of any translate $(a_n + t)_{n\geq 1}$, for $t \in \mathbb{Z}^*$, is infinite. With us, since the terms of the sequence $(n_k + 1 = p^{2^k})_{k\geq 1}$ have only $p$ as a prime factor, it follows the set of prime divisors of the terms of the sequence $(n_k + 2)_{k\geq 1}$ is infinite. grobber is actually proving this using Pólya's trick in showing Fibonacci numbers are pairwise coprime. Let $ k$ be the smallest integer for which $ P\left(n_k+2\right) > p$. Now we'll fix a typo in grobber's proof: in fact we have $ n_k=\left(p-1\right)\cdot\left(p+1\right)\cdot (n_1 +2)\cdot (n_2 + 2)\cdot ...\cdot (n_{k-1} + 2)$, so $P(n_k) < p = P(n_k + 1) < P(n_k + 2)$.

I found basically the same proof; just consider the sequence $p^{2^k}$. But when we need to show that $P(p^{2^k} + 1)$ gets arbitrarily large, I (am slightly ashamed to admit that I) invoked Stormer's Theorem (http://en.wikipedia.org/wiki/St%C3%B8rmer's_theorem), where mavropnevma used Kobayashi's Theorem, and where grobber, I believe, did the right thing in finding an easy, elementary proof (Polya's trick). By the way, this proof method leads to the the interesting statement that for every odd prime $p$ there exists exactly one positive integer $k$ for which we have $P(p^{2^k} - 1) < P(p^{2^k}) < P(p^{2^k} + 1)$. The fact that so far this method has been the only method posted, makes me wonder if a different easy argument can be found for this problem.

Take $n=2^k$,and notice that the sequence ${p(2^k+1)}$ is not monotone increasing,And the rest is simple.

daoxun wrote: Take $n=2^k$,and notice that the sequence ${p(2^k+1)}$ is not monotone increasing,And the rest is simple. I found the"notice that" is not quite easy to prove...I'll think a solution for it afterwards...

@above Let $n = 2^k$ for some integer $k$. In your solution it ultimately came down to showing that there are an infinite number of integers $k$ such that $p(2^k + 1) > p(2^{k - 1} + 1)$. Suppose that number is finite and let $k$ be the last of such numbers. So $$p(2^k + 1) > p(2^{k + 1} + 1) > p(2^{k + 2} + 1) > ...$$By Zsigmondy's theorem, there exists another prime factor of $2^k + 1$ but doesn't appear in the factorization of $2^i + 1$ for $i < k$. Hence the number of prime factors is infinite and unbounded in the sequence $\{2^i + 1\}$ for $i \ge k$. But $p(2^k + 1)$ is clearly bounded, so there must exist an $i$ such that $p(2^i + 1) > p(2^k + 1)$ for $i > k$. Hence the fact must hold that there are an infinite number of integers $k$ such that $p(2^k + 1) > p(2^{k - 1} + 1)$. (Note that $\gcd(2^k + 1, 2^{k + 1} + 1) = 1$ since $2^{k + 1} + 1 = 2(2^k + 1) - 1$)