Every prime p is a p-adic nonresidue for some prime

History

This appeared as a problem in the International Mathematical Olympiad in 2003, as problem 6.

Statement

Suppose $p$ is a prime number. Then, there exists a prime $q$ such that the congruence:

$n^{p}\equiv p{\pmod {q}}$

has no solution.

Related facts

• Every integer is a quadratic residue for infinitely many primes
• Every integer that is not a perfect square is a quadratic nonresidue for infinitely many primes
• Every prime is the smallest quadratic nonresidue for infinitely many primes

Facts used

1. Congruence condition on prime divisor of cyclotomic polynomial evaluated at an integer

Proof

Given: A prime number $p$.

To prove: There exists a prime $q$ such that $n^{p}\equiv p{\pmod {q}}$ has no solution.

Proof: Consider the $p^{th}$ cyclotomic polynomial evaluated at $p$.

$\Phi _{p}(p)={\frac {p^{p}-1}{p-1}}=1+p+p^{2}+\dots p^{p-1}$.

1. Every prime divisor of $\Phi _{p}(p)$ is $1$ modulo $p$: By fact (1), any prime divisor of $\Phi _{p}(p)$ either divides $p$ or is congruent to $1$ modulo $p$. Since $p$ is prime, a prime divisor that divides $p$ must be equal to $p$; however, $p$ itself does not divide $\Phi _{p}(p)$, since $\Phi _{p}(p)\equiv 1{\pmod {p}}$. Thus, any prime divisor of $\Phi _{p}(p)$ is congruent to $1$ modulo $p$.
2. There is a prime divisor $q$ of $\Phi _{p}(p)$ such that $p$ divides $q-1$ but $p^{2}$ does not divide $q-1$: On the other hand, since $\Phi _{p}(p)\equiv p+1{\pmod {p^{2}}}$, there must be at least one prime divisor of $\Phi _{p}(p)$ that is not congruent to $1$ modulo $p^{2}$. Let $q$ be such a prime divisor. Then, $p$ divides $q-1$ but $p^{2}$ does not divide $q-1$.
3. The order of $p$ modulo $q$ equals $p$: Consider the order of $p$ modulo $q$. Since $p^{p}\equiv 1{\pmod {q}}$, this order is either $1$ or $p$. If the order is $1$, then $p\equiv 1{\pmod {q}}$, and in particular, $p>q$, contradicting our finding that $q\equiv 1{\pmod {p}}$. Thus, the order of $p$ modulo $q$ must be $p$.
4. $p$ is not a $p^{th}$ power modulo $q$: Now, since $p$ divides $q-1$, and the multiplicative group modulo $q$ is cyclic, an element $a$ is a $p^{th}$ power modulo $q$ if and only if $a^{(q-1)/p}\equiv 1{\pmod {q}}$. In particular, $p$ is a $p^{th}$ power modulo $q$ if and only if $p^{(q-1)/p}$ \equiv 1 \pmod q</math>. But the latter happens only if $p$ (the order of $p$ modulo $q$) divides ${\frac {q-1}{p}}$, which is equivalent to $p^{2}$ dividing $q-1$, which we assume does not happen. Thus, $p$ is not a $p^{th}$ power modulo $q$.