Summary: Let $N_{a,b}(x)$ count the number of primes $p\le x$ with $p$ dividing $a^k+b^k$ for some $k\ge 1$. It is known that $N_{a,b}(x)\sim 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.

11N37, 11N69, 11R45

primitive root, chebotarev density theorem, Dirichlet density