IJMMS 2004:70, 3889–3892 PII. S0161171204403226 http://ijmms.hindawi.com
© Hindawi Publishing Corp.
A GENERALIZATION OF A NECESSARY AND SUFFICIENT CONDITION FOR PRIMALITY DUE TO VANTIEGHEM
L. J. P. KILFORD Received 10 March 2004
We present a family of congruences which hold if and only if a natural numbernis 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 integerpis prime or not.
There are older deterministic primality tests which are less efficient; the classical example is Wilson’s theorem, that
(n−1)!≡ −1 modn (1)
if and only ifnis 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, ProblemA17], the following result due to Vantieghem [4] is quoted as follows.
Theorem1(Vantieghem [4]). Letnbe a natural number greater than1. Thennis 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.
Theorem2. Letmandnbe natural numbers greater than1. Thennis prime if and only if
n−1 d=1
1−md
≡nmodmn−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
Lemma3(Vantieghem). Letmbe a natural number greater than1and letΦm(X)be themth cyclotomic polynomial. Then
m (d,m)=d=11
X−Yd
≡Φm(X)modΦm(Y ) inZ[X,Y ]. (4)
Proof ofLemma3. We can write m
(d,m)=d=11
X−Yd
−Φm(X)=f0(Y )+f1(Y )X+f2(Y )X2+···. (5)
(Here thefiare polynomials overZ.)
Letζbe a primitivemth root of unity. Now, ifY=ζ, then we see that the left-hand side of this expression is identically 0 inX.
This implies that thefiare zero at everyζand everyi. Therefore, we havefi(Y )≡ 0 modΦm(Y ), which is enough to prove the lemma.
Suppose that the natural numberninTheorem 2is prime. Letp:=n. We have that Φp(X)=Xp−1+Xp−2+···+X+1. Therefore, if we setm=pinLemma 3, we find that
p−1
d=1
X−Yd
≡Xp−1+Xp−2+···+X+1 mod
Yp−1+···+1
. (6)
We now setX=1 andY=m, to get
p−1 d=1
1−md
≡pmodmp−1
m−1 . (7)
This proves that ifpis prime, then the congruence holds.
We now prove the converse, by supposing that the congruence (3) holds, and thatp is not prime. Thereforepis composite, and hence has a smallest prime factorq. We writep=q·a; nowq≤a, and alsop≤a2.
Now we have thatma−1 dividesmp−1 andma−1 divides the productp−1 d=1(md− 1). By combining this with the congruence (3) inTheorem 2, this implies that(ma− 1)/(m−1)dividesp. Therefore we have
2a−1≤ma−1
m−1 ≤p≤a2. (8)
The inequality 2a−1≤a2forcesato be either 2 or 3; this means thatp∈ {4,6,9}and m∈ {2,3}; one can check by hand that the congruence does not hold in this case, so we have provedTheorem 2.
Guy also asks if there is a relationship between the congruence given by Vantieghem and Wilson’s theorem. The following theorem gives an elementary congruence similar to that of Vantieghem between a product over integers and a cyclotomic polynomial. It is in fact equivalent to Wilson’s theorem.
A GENERALIZATION OF A NECESSARY AND SUFFICIENT CONDITION... 3891 Theorem4. Letmbe a natural number greater than2. Define the productF(X)by
F(X):=
m−1 i=1 (i,m)=1
(X−i−1)+1. (9)
Thenmis prime if and only if
Φm(X)≡F(X)modm. (10) Proof ofTheorem4. Firstly, we prove that ifmis not prime, the congruence (10) inTheorem 4does not hold.
Recall thatφ(m)is defined to be Euler’s totient function; the number of integers in the set{1,...,m}which are coprime tom.
The coefficient ofXφ(m)−1inF(X)is given by the sum
−
m−1
(i,m)=i=11
(i+1)= −φ(m)−
m−1
(i,m)=i=11
i. (11)
We find that the following congruence holds:
−φ(m)− m−
1 (i,m)=i=11
i≡ −φ(m)modm. (12)
This follows from the following identity:
m−1 i=1 (i,m)=1
i=mφ(m)
2 . (13)
Becausem >2,φ(m)is divisible by 2, the sum on the left-hand side of (12) is a multiple ofm. We now use some theorems to be found in a paper by Gallot [2, Theorems 1.1 and 1.4].
Theorem5. Letpbe a prime andma natural number.
(1) The following relations between cyclotomic polynomials hold:
Φpm(x)=
Φm
xp
ifp|m, Φm
xp
Φm(x) ifpm.
(14)
(2) Ifm >1, then
Φn(1)=
p ifnis a power of a primep,
1 otherwise. (15)
3892 L. J. P. KILFORD
From these results, we see that if mis not a prime power, we then haveΦn(1)≡ 1 modm, andF(1)is given by
1+
m−1 i=1 (i,m)=1
(−i). (16)
We see that this is not congruent to 1 modmbecause the product is over thoseiwhich are coprime tom, so the product does not vanish modulom.
Ifmis a prime powerpn, then we see fromTheorem 5thatΦpn(x)=Φp(xpn−1); in particular, we see that the coefficient ofxφ(pn)−1is 0, which differs from the coefficient ofxφ(pn)−1inF(X).
Therefore, ifmis not prime, then the congruence does not hold. We now show that ifmis prime, the congruence holds.
Ifmis prime, thenΦm(x)=xm−1+xm−2+···+x+1. We consider the polynomials Φm(X+1)andF(X+1). Now, modulomwe have
Φm(X+1)=Xm−1, F(X+1)=
m−1 (i,m)=i=11
(X−i)+1. (17)
Now ifx=0 modm, then we see thatΦm(x+1)≡1 and thatF(x+1)≡1, because the product vanishes.
And if we havex=0, thenΦm(x)=0 and, by Wilson’s theorem,F(0)≡(m−1)!+1≡ 0 modm.
Therefore we have provedTheorem 4.
References
[1] M. Agrawal, N. Kayal, and N. Saxena,PRIMES is in P, preprint, 2002,http://www.cse.iitk.
ac.in/news/primality.html.
[2] Y. Gallot, Cyclotomic polynomials and prime numbers, preprint, 2001, http://perso.
wanadoo.fr/yves.gallot/papers.
[3] R. K. Guy,Unsolved Problems in Number Theory, 2nd ed., ProblemA17. Problem Books in Mathematics, I, Springer-Verlag, New York, 1994.
[4] E. Vantieghem,On a congruence only holding for primes, Indag. Math. (N.S.)2(1991), no. 2, 253–255.
L. J. P. Kilford: The University of Oxford, Mathematical Institute, 24–29 Street Giles’, Oxford OX1 3LB, UK
