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$ Commented Dec 14, 2013 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$ Commented Dec 14, 2013 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$ Commented Dec 14, 2013 at 11:32
  • $\begingroup$ For what it's worth, greatest prime dividing $n$ is tabulated at oeis.org/A006530 $\endgroup$ Commented Dec 14, 2013 at 11:35
  • $\begingroup$ No, no context and noone has posted some solution or anything. The title just says "Hard numbertheoretical problem". $\endgroup$
    – Parseval
    Commented Dec 14, 2013 at 11:37

2 Answers 2


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$ Commented Dec 17, 2013 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
    Commented Dec 17, 2013 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$ Commented Dec 18, 2013 at 7:06
  • $\begingroup$ Yes, that's nice. I would transfer all my upvotes to this answer if I could! $\endgroup$
    – TonyK
    Commented Dec 18, 2013 at 9:21
  • $\begingroup$ @Feanor of Noldor: Thanks for clarification, I'll look into this solution after work! $\endgroup$
    – Parseval
    Commented Dec 18, 2013 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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .