Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

How to prove that $p-1$ is squarefree infinitely often, where $p$ is prime?

I had thought of using Dirichlet's theorem on arithmetic progressions. The number of squareful values of $p-1$ less than or equal to $n$ is bounded by $\sum_{q}{\pi_{q^2,1}(n)}$, each term $\pi_{q^2,1}(n) \approx \frac{\pi(n)}{q \cdot (q-1)}$, and $\sum_{q}{\frac{1}{q \cdot (q-1)}} \lt 1$. But using for example this statement of Dirichlet's theorem, the possibility is open that the error in each approximation for $\pi_{q^2,1}(n)$ may continue to increase with $q$, and since the sum runs up to $\sqrt{n}$, this argument is invalid.

Is there a more refined version of Dirichlet's theorem that can be used to circumvent this issue? Or an entirely different way to prove this statement?

share|cite|improve this question
If you're willing to accept a certainly-true-but-unproved hypothesis, there are infinitely many primes $q$ such that $p=2q+1$ is prime, and those $p$ will work. – Gerry Myerson Jun 3 '12 at 4:53
I'm hoping for an unconditional proof (or else a reference to the problem being open). Infinity of safe primes is open and implies it but I don't know why this should be as hard. Are you saying RH implies an infinity of safe primes? I hadn't heard of this and I looked for a reference on Google but couldn't find one. However, I can see that RH implies that $p-1$ is squarefree infinitely often if the error is independent of $q$. I'm not very familiar with the proof of Dirichlet's theorem (I looked at it but found it quite intimidating) so I don't know if this is true. – Dan Brumleve Jun 7 '12 at 3:24
The "certainly-true-but-unproved hypothesis" I had in mind was not that of Riemann, but of Dickson; see, e.g.,'s_conjecture. – Gerry Myerson Jun 7 '12 at 5:51
For what it's worth, these primes are tabulated at, but no other information is given there. – Gerry Myerson Jun 7 '12 at 5:58
up vote 8 down vote accepted

There is a more refined version of Dirichlet's theorem which is immensely useful in these types of problems. It's called the Bombieri-Vinogradov theorem, which says roughly that the error term in Dirichlet's theorem cannot be very large for many values of $q$ simultaneously. While we can't bound any individual error term by $O(n^{1/2+\epsilon})$ (such a bound would be equivalent to a form of RH), we can get this level of control if we average over many values of $q$.

More precisely, let $E(q)$ denote the error $\left|\pi_{q^2,1}(n) - \frac{\pi(n)}{q(q-1)}\right|$ in Dirichlet's theorem. Then a simple consequence of Bombieri-Vinogradov is that for some constant $B > 0$, $$\sum_{q < n^{1/4} \ \log^{-B} n} E(q) \ll \frac{n}{\log^2n}.$$

Therefore the error terms for $q \le n^{1/4}\ \log^{-B} n$ cannot accumulate to exceed the $\Omega(n/\log n)$ difference between $\pi(n)$ and $\sum\limits_{q\text{ prime}} \frac{\pi(n)}{q(q-1)}$, exactly as you had hoped. The only moduli remaining are $n^{1/4} \ \log^{-B} n \le q \le \sqrt{n}$, but these are very easily controlled using the trivial bound $\pi_{q^2,1}(n) \le \frac{n}{q^2}$ (there aren't many numbers congruent to $1\!\!\pmod{q^2}$ when $q$ is large).

A slightly more general application of Bombieri-Vinogradov should be able to produce the asymptotic result cited in @GerryMyerson's answer.

EDIT — Had the wrong upper bound for $q$, since the modulus is $q^2$, not $q$.

EDIT 2012/06/13: The asymptotic is probably not as immediate as I thought; it would require some subtlety with regard to the number of primes $q$ we can sieve out.

share|cite|improve this answer

It appears that a density result for these primes was given by Mirsky, with a proof appearing in a paper by Moree and Hommerson. Section 6.2.1, Theorem 2 (page 17) says if $r$ is a non-zero integer, $k$ an integer greater than 1, $H$ any positive number, then the number of primes $q$ up to $x$ such that $q-r$ is $k$-free is $$\prod_{p\nmid r}\left(1-{1\over p^{k-1}(p-1)}\right){\rm Li}(x)+O\left({x\over\log^Hx}\right)$$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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