© Hindawi Publishing Corp. A GENERALIZATION OF A NECESSARY AND SUFFICIENT CONDITION FOR PRIMALITY DUE TO VANTIEGHEM

We present a family of congruences which hold if and only if a natural number n is prime. 2000 Mathematics Subject Classification: 11A51, 11A07. The subject of primality testing has been in the mathematical and general news re-cently, with the announcement [1] that there exists a polynomial-time algorithm to determine whether an integer p is prime or not. There are older deterministic primality tests which are less efficient; the classical example is Wilson’s theorem, that (n−1)!≡−1modn (1) if and only if n is prime. Although this is a deterministic algorithm, it does not provide a workable primality test because it requires much more calculation than trial division. This note provides another family of congruences satisfied by primes and only by primes; it is a generalization of previous work. They could be used as examples of primality tests for students studying elementary number theory. In Guy [3, Problem A17], the following result due to Vantieghem [4] is quoted as follows. Theorem 1 (Vantieghem [4]). Let n be a natural number greater than 1. Then n is prime if and only if n−1∏ d=1 1−2d)≡nmod(2n−1). (2) In this note, we will generalize this result to obtain the following theorem. Theorem 2. Letm and n be natural numbers greater than 1. Then n is prime if and only if n−1∏ d=1 1−md)≡nmodm n−1 m−1. (3) We note that these congruences are also much less efficient than trial division. Proof. We follow the method of Vantieghem, using a congruence satisfied by cy-clotomic polynomials. 3890 L. J. P. KILFORD Lemma 3 (Vantieghem). Letm be a natural number greater than 1 and let Φm(X) be themth cyclotomic polynomial. Then m∏ d=