1
$\begingroup$

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.

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

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$.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.