Abstract

Let N_{a,b}(x) count the number of primes p ≤ x with p dividing a^{k} + b^{k} for some k ≥ 1. It is known that N_{a,b}(x) ∼ c(a, b)x/ log x for some rational number c(a, b) that depends in a rather intricate way on a and b. A simple heuristic formula for N_{a,b}(x) is proposed and it is proved that it is asymptotically exact, i.e., has the same asymptotic behavior as N_{a,b}(x). Connections with Ramanujan sums and character sums are discussed.