A primality criterion based on a Lucas' congruence

Abstract

Let $p$ be a prime. In 1878 É. Lucas proved that the congruence $$\left(\genfrac{}{}{0ex}{}{p-1}{k}\right)\equiv (-1{)}^k(\mathrm{mod}p)$$ holds for any nonnegative integer $k\in \{0,1,\dots ,p-1\}$. The converse statement was given in Problem 1494 of {\it Mathematics Magazine} proposed in 1997 by E. Deutsch and I.M. Gessel. In this note we generalize this converse assertion by the following result: If $n>1$ and $q>1$ are integers such that $$\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)\equiv (-1{)}^k(\mathrm{mod}q)$$ for every integer $k\in \{0,1,\dots ,n-1\}$, then $q$ is a prime and $n$ is a power of $q$.

arXiv comment6 pages