Research PapersNo Access

A primality criterion based on Lucas’ congruence

Romeo Meštrović

Romeo Meštrović

Maritime Faculty, University of Montenegro, Dobrota 36, 85330 Kotor, Montenegro

E-mail Address: romeo@ac.me

Search for more papers by this author

https://doi.org/10.1142/S1793042116500834Cited by:1 (Source: Crossref)

Abstract

Let $p$ be a prime. Back in 1878, Lucas proved that the congruence

(p - 1 k) \equiv (- 1) k (mod p) <math display="block" altimg="eq-00002.gif"><mrow><mfenced separators="" open="(" close=")"><mrow><mtable style="text-align:axis" equalrows="false" equalcolumns="false" class="array"><mtr><mtd class="array" columnalign="center"><mi>p</mi><mo stretchy="false" class="MathClass-bin">-</mo><mn>1</mn></mtd></mtr><mtr><mtd class="array" columnalign="center"><mi>k</mi></mtd></mtr></mtable></mrow></mfenced><mo class="MathClass-rel">\equiv</mo><msup><mrow><mo class="MathClass-open" stretchy="false">(</mo><mo stretchy="false" class="MathClass-bin">-</mo><mn>1</mn><mo class="MathClass-close" stretchy="false">)</mo></mrow><mrow><mi>k</mi></mrow></msup><mspace width="0.3em"></mspace><mo class="MathClass-open" stretchy="false">(</mo><mo class="MathClass-op">mod</mo><mspace width="0.3em"></mspace><mi>p</mi><mo class="MathClass-close" stretchy="false">)</mo></mrow></math>

holds for any nonnegative integer

$k \in {0, 1, \dots, p - 1}$ . The converse statement was given in Problem 1494 of Mathematics Magazine proposed in 1997 by Deutsch and Gessel. In this note, we generalize this converse assertion as follows: If

$n > 1$ and

$q > 1$ are integers such that

(n - 1 k) \equiv (- 1) k (mod q) <math display="block" altimg="eq-00006.gif"><mrow><mfenced separators="" open="(" close=")"><mrow><mtable style="text-align:axis" equalrows="false" equalcolumns="false" class="array"><mtr><mtd class="array" columnalign="center"><mi>n</mi><mo stretchy="false" class="MathClass-bin">-</mo><mn>1</mn></mtd></mtr><mtr><mtd class="array" columnalign="center"><mi>k</mi></mtd></mtr></mtable></mrow></mfenced><mo class="MathClass-rel">\equiv</mo><msup><mrow><mo class="MathClass-open" stretchy="false">(</mo><mo stretchy="false" class="MathClass-bin">-</mo><mn>1</mn><mo class="MathClass-close" stretchy="false">)</mo></mrow><mrow><mi>k</mi></mrow></msup><mspace width="0.3em"></mspace><mo class="MathClass-open" stretchy="false">(</mo><mo class="MathClass-op">mod</mo><mspace width="0.3em"></mspace><mi>q</mi><mo class="MathClass-close" stretchy="false">)</mo></mrow></math>

for every integer

$k \in {0, 1, \dots, n - 1}$ , then

$q$ is a prime and

$n$ is a power of

$q$ .

Keywords:

AMSC: 11A51, 11A07, 05A10, 11B65

References

1. T.-X. Cai and A. Granville, On the residues of binomial coefficients and their products modulo prime powers, Acta Math. Sinica 18(2) (2002) 277–288. Crossref, Google Scholar
2. E. Deutsch and I. M. Gessel, Problem 1494, Math. Mag. 70(2) (1997) 143–144. Google Scholar
3. L. E. Dickson, The History of the Theory of Numbers, Vol. 1 (Chelsea Publishing, New York, 1966). Google Scholar
4. C. F. Gauss, Disquisitiones Arithmeticae (Fleischer, Leipzig, 1801). Crossref, Google Scholar
5. H. W. Gould and W. E. Greig, A Lucas triangle primality criterion dual to that of Mann–Shanks, Fibonacci Quart. 23(1) (1985) 66–69. Web of Science, Google Scholar
6. A. Granville, Arithmetic properties of binomial coefficients. I. Binomial coefficients modulo prime powers, in Organic Mathematics, CMS Conference Proceedings, Vol. 20 (American Mathematical Society, Providence, RI, 1997), pp. 253–276. Google Scholar
7. É. Lucas, Théorie des fonctions numérique simplement périodiques, Amer. J. Math. 1(2) (1878) 184–240. Crossref, Google Scholar
8. H. B. Mann and D. Shanks, A necessary and sufficient condition for primality, and its source, J. Combin. Theory Ser. A 13(1) (1972) 131–134. Crossref, Google Scholar
9. R. Meštrović, A note on the congruence $(\begin{matrix} n d \\ m d \end{matrix}) \equiv (\begin{matrix} n \\ m \end{matrix}) (mod q)$ , Amer. Math. Monthly 116(1) (2009) 75–77. Crossref, Web of Science, Google Scholar
10. R. Meštrović, Wolstenholme’s theorem: Its generalizations and extensions in the last hundred and fifty years (1862–2012), preprint (2011); arXiv:1111.3057v2 [math.NT]. Google Scholar
11. R. Meštrović, An extension of Babbage’s criterion for primality, Math. Slovaca 63(6) (2013) 1179–1182. Crossref, Web of Science, Google Scholar
12. R. Mestrović, Lucas’ theorem: Its generalizations, extensions and applications (1878–2014), preprint (2014); arXiv:1409.3820v1 [math.NT]. Google Scholar
13. P. A. Piza, Fermat coefficients, Math. Mag. 27(3) (1954) 141–146. Google Scholar