# Infinitely many primes such that $a^{(p-1)/d} \equiv 1 \bmod p$

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.

• What is the quantifier applied on $a$ in your theorem (i.e., is it $\exists{a}$ or $\forall{a})$? – barak manos Sep 15 '16 at 15:05
• Any fixed $a$, or some fixed $a$? (same question as before, to be honest). – barak manos Sep 15 '16 at 15:08
• For all $a$, for all $d$, there exist infinitely many $p$.such that.... – Aravind Sep 15 '16 at 15:08
• It suffices to prove that infinitely many primes divide one of the numbers in $2^d-a,3^d-a,4^d-a,\ldots$. – Aravind Sep 15 '16 at 15:13
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$.)