Fix an integer $a$. By Fermat's little theorem we know that $a^{p - 1} \equiv 1 \bmod p$ for all prime numbers $p$ which do not divide $a$.
I would like to prove that for any positive integers $a$ (not divisible by $p$) and $d$ there exist infinitely many prime numbers $p$ such that $p \equiv 1 \bmod d$ and $a^{(p-1)/d} \equiv 1 \bmod p$.
I do not know if this is really true, but I suspect so. For $d = 2$ I am able to prove the statement: just take all the infinitely many prime $p$ such that $a$ is a square modulo $p$, so that $a^{(p-1)/2} \equiv 1 \bmod p$ by Euler's criterion.
Thanks for any advice.
It is true: Let $p_1$ be a prime divisor of $1^d-a$, and inductively $p_{n+1}$ a prime divisor of $(p_1\cdots p_n)^d-a$. Then $a$ is a $d$th power modulo the pairwise distinct $p_k$.
(Note that, by induction, no prime $p_k$ divides $a$. To make sure everyhing goes fine in the first step, you could also start with $(a+1)^d-a$.)