I don't even have an idea of how to start working on this one:

Let $p(n)$ denote the greatest prime number that divides $n.$ Show that there exists infinitely many positive integers $m$ such that $$p(m-1)<p(m)<p(m+1).$$

  • 2
    $\begingroup$ Can you provide some context, e.g., where you found this problem? $\endgroup$ – Greg Martin Dec 14 '13 at 9:31
  • $\begingroup$ Was it presented as a solved problem? an unsolved problem? There's always some context. Did anyone say anything about it? $\endgroup$ – Gerry Myerson Dec 14 '13 at 11:29
  • 1
    $\begingroup$ Conjecturally, there are infinitely many $m$ such that $m-1$ is 3 times a prime, $m$ is twice a prime, and $m+1$ is a prime. But I don't think we are anywhere near proving such a conjecture. $\endgroup$ – Gerry Myerson Dec 14 '13 at 11:32
  • $\begingroup$ For what it's worth, greatest prime dividing $n$ is tabulated at oeis.org/A006530 $\endgroup$ – Gerry Myerson Dec 14 '13 at 11:35
  • $\begingroup$ No, no context and noone has posted some solution or anything. The title just says "Hard numbertheoretical problem". $\endgroup$ – Parseval Dec 14 '13 at 11:37

For briefer notation let $n \in G$, iff $p(n-1) < p(n) < p(n+1)$ (G is for "good"). Also, say that $n \in P$ iff $p(n) > p(n-1),p(n+1)$ (P is for "peak"). The key to the solution is the following simple observation:

Observation: If $n \in P$ then either $n^2 \in G$ or $n^2 \in P$.

Proof: Suppose that $p(n) > p(n-1),p(n+1)$ and $n^2 \not \in G$. Because $n^2-1 = (n-1)(n+1)$, we have that $p(n^2) = p(n) > p(n^2-1)$. Thus, the only way for $n^2 \not \in G$ is if $p(n^2) > p(n^2+1)$. Then clearly $n^2 \in P$. $\square$

We want to prove that $G$ is infinite. For a proof by contradiction, suppose that $G$ is finite. Because $\limsup p(n) = + \infty$, we can select arbitrarily large $n_0$ with $p(n_0)>p(n_0-1)$. If $n_0 > \max G$ (so in particular $n_0 \not \in G$), then $p(n_0) > p(n_0+1)$ and hence $n_0 \in P$.

Let $n_1:= n_0^2$, $n_2 = n_1^2$, and generally $n_{i+1} = n_i^2$ (so in closed form $n_i = n_0^{2^i}$). Because of the above observation, and because $n_0^2 \not \in G$, we have $n_1 = n_0^2 \in P$. Likewise, $n_2 = n_1^2 \in P$, and inductively $n_i \in P$ for all $i$.

Let $p_0 = p(n_0)$. Clearly, $p(n_i) = p_0$ for all $i$. In paricular, $p_0 > p(n_i+1)$ for all $i$. Let $m_i := n_i+1$, and note that $m_{i+1} = (m_i-1)^2+1$. Thus, we have $m_{i+1} \equiv 2 \pmod{m_i}$, $m_{i+2} \equiv 2 \pmod{m_i}$ and generally $m_{j} \equiv 2 \pmod{m_i}$ for $j > i$. Thus, $m_i$ do not share any prime factors, except for $2$. Because $m_i$ are obviously larger than $2$ and are not divisible by $4$, we see that $p(m_i) > 2$ all take different values for different $i$. At the same time, $p(m_i) < p_0$ by construction. Thus, we arrive at a contradiction proving the initial claim.

  • $\begingroup$ Very nice! It might be clearer that $m_j\equiv2(\mod m_i)$ for $j>i$ because $(m_j-1)=(m_i-1)^{2^{j-i}}$, and that the $m_i$ have no prime factors in common and so will eventually have to run out of prime factors $<p_0$. $\endgroup$ – Einar Rødland Dec 17 '13 at 19:44
  • $\begingroup$ What exactly do you mean by G and P? N belongs to good? good what? Belongs to peak? peak what? $\endgroup$ – Parseval Dec 17 '13 at 20:38
  • $\begingroup$ @Parseval: $G \subset \mathbb{N}$ is the set of those $n \in \mathbb{N}$ for which it is true that $p(n-1) < p(n) < p(n+1)$, and $P\subset \mathbb{N}$ is the set of those $n$ with $p(n-1) < p(n)$ and $p(n+1) < p(n)$. The words "good" and "peak" are related to the intuitions I had for these sets, as in "$n$ is good for the purpose of proving the claim" or "$n$ is the number at which $p(\cdot)$ has a peak". However, in principle $P$ and $G$ are just some sets I chose to define... $\endgroup$ – Jakub Konieczny Dec 18 '13 at 7:06
  • $\begingroup$ Yes, that's nice. I would transfer all my upvotes to this answer if I could! $\endgroup$ – TonyK Dec 18 '13 at 9:21
  • $\begingroup$ @Feanor of Noldor: Thanks for clarification, I'll look into this solution after work! $\endgroup$ – Parseval Dec 18 '13 at 10:20

If $q$ and $2q+1$ are both prime, with $q > 3$, then $p(2q-1)$ must be less than $q$. This is because one of the three consecutive integers $2q-1,2q,2q+1$ must be divisible by $3$, and we know that $2q$ and $2q+1$ are not. So $3 | (2q-1)$, thus $p(2q-1) \le (2q-1)/3 < q$. So we have the increasing sequence:

$$p(2q-1) < q$$ $$p(2q) = q$$ $$p(2q+1) = 2q+1$$

Such primes $q$ are called Sophie Germain primes, and it is conjectured (though not proven) that there are an infinite number of them.

Edited to add:

And if $2^n+1$ is prime, but $2^{n+1}+1$ is not, then we have the increasing sequence:

$$p(2^{n+1}) = 2$$ $$3 \le p(2^{n+1}+1) < 2^n$$ $$p(2^{n+1}+2) = 2^n+1$$

If $2^n+1$ is prime, then $n$ must be a power of two, and $2^n+1$ is called a Fermat prime. Again, whether there are an infinite number of Fermat primes is an open problem.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.