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).$$
$\begingroup$
$\endgroup$
6
-
2$\begingroup$ Can you provide some context, e.g., where you found this problem? $\endgroup$– Greg MartinDec 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$– Gerry MyersonDec 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$– Gerry MyersonDec 14, 2013 at 11:32
-
$\begingroup$ For what it's worth, greatest prime dividing $n$ is tabulated at oeis.org/A006530 $\endgroup$– Gerry MyersonDec 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$– ParsevalDec 14, 2013 at 11:37
|
Show 1 more comment
2 Answers
$\begingroup$
$\endgroup$
5
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.
answered Dec 17, 2013 at 19:21
-
$\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$ 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$– ParsevalDec 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$ Dec 18, 2013 at 7:06
-
$\begingroup$ Yes, that's nice. I would transfer all my upvotes to this answer if I could! $\endgroup$– TonyKDec 18, 2013 at 9:21
-
$\begingroup$ @Feanor of Noldor: Thanks for clarification, I'll look into this solution after work! $\endgroup$– ParsevalDec 18, 2013 at 10:20
$\begingroup$
$\endgroup$
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.
