  Let $(F_n)$ be the sequence of Fibonacci numbers and, for each positive
integer $k$, let $\mathcal{P}_k$ be the set of primes $p$ such that $\gcd(p -
1, F_{p - 1}) = k$. We prove that the relative density
$\text{r}(\mathcal{P}_k)$ of $\mathcal{P}_k$ exists, and we give a formula for
$\text{r}(\mathcal{P}_k)$ in terms of an absolutely convergent series.
Furthermore, we give an effective criterion to establish if a given $k$
satisfies $\text{r}(\mathcal{P}_k) > 0$, and we provide upper and lower bounds
for the counting function of the set of such $k$'s. As an application of our
results, we give a new proof of a lower bound for the counting function of the
set of integers of the form $\gcd(n, F_n)$, for some positive integer $n$. Our
proof is more elementary than the previous one given by Leonetti and Sanna,
which relies on a result of Cubre and Rouse.
