[PDF] The cyclotomic polynomials

Note that e(n) = 1 for integers n, e(1 2 ) = −1 and e(s + t) = e(s)e(t) for all s, t remove the factor x − 1 corresponding to k = p D Let n ≥ 3 Denote by E∗ By 1 12, it is enough to show that Φn(1) = 1 for n of the form p1p2 pk, where k ≥ 2  



Previous PDF Next PDF





Some Factorizations of 2±1 and Related Results

the current status of the numbers (10p — l)/9, p prime, of the "original" Mersenne In the present case where N is a primitive factor of 2" — 1 (that is, N is a product of primitive prime factors), we can show that x belongs to a certain arith-



by Using Factors of N ± 1 - American Mathematical Society

2 a large integer TV when a sufficient number of prime factors of N +1 are [7] and then show how these functions may be utilized in the development of the de- 1 p, P\-P2-3Q P\ - 2P,P2 - 4P Ф ^+4=^1^+3 -C2 +22)^+2 +QP1K+1 -Q'K'



[PDF] MERSENNE PRIMES If n ≥ 2 and an − 1 is prime, we call an − 1 a

A Mersenne prime is a prime that can be written as 2 p −1 for some prime p n − 1 always has a factor 2m − 1, and therefore is prime only when We prove one direction of this statement, namely that if Mp sp−2, then Mp is prime



[PDF] proof

Since 2 = 1 and 2 = p, the number 2 is not one of the numbers that divides p Here is another way to prove Theorem I: by contradiction Assume as If a positive integer m is evenly divisible by some integer n > 1, then m+1 is not evenly



[PDF] On the largest prime factors of n and n +1 - Dartmouth Mathematics

$1 Introduction If n22 is an integer, let P(n) denote the largest prime factor of n For every We prove here the Aaron numbers do indeed have density 0 The result Theorem 2 implies that usually f(n)=P(n) and f(n+1)=P(n+1) But Theorem 1



The cyclotomic polynomials

Note that e(n) = 1 for integers n, e(1 2 ) = −1 and e(s + t) = e(s)e(t) for all s, t remove the factor x − 1 corresponding to k = p D Let n ≥ 3 Denote by E∗ By 1 12, it is enough to show that Φn(1) = 1 for n of the form p1p2 pk, where k ≥ 2  



[PDF] On the greatest and least prime factors of n+1 (PDF)

We prove TELT THEOREM 2 For all positive integers n we have 90 1 Pent-+ 1 ) > n+1-0(1)) logn/log log n Furthermore lim sup P(n+1)/n > 2+8 PLE where 8 

[PDF] show that 2^p 1(2p 1) is a perfect number

[PDF] show that 4p^2 20p+9 0

[PDF] show that a sequence xn of real numbers has no convergent subsequence if and only if xn → ∞ asn → ∞

[PDF] show that etm turing reduces to atm.

[PDF] show that every infinite turing recognizable language has an infinite decidable subset.

[PDF] show that every tree with exactly two vertices of degree one is a path

[PDF] show that f is continuous on (−∞ ∞)

[PDF] show that for each n 1 the language bn is regular

[PDF] show that if a and b are integers with a ≡ b mod n then f(a ≡ f(b mod n))

[PDF] show that if an and bn are convergent series of nonnegative numbers then √ anbn converges

[PDF] show that if f is integrable on [a

[PDF] show that if lim sn

[PDF] show that p ↔ q and p ↔ q are logically equivalent slader

[PDF] show that p ↔ q and p ∧ q ∨ p ∧ q are logically equivalent

[PDF] show that p(4 2) is equidistant

The cyclotomic polynomials

Notes by G.J.O. Jameson

1. The definition and general results

We use the notatione(t) =e2πit. Note thate(n) = 1 for integersn,e(12 ) =-1 and e(s+t) =e(s)e(t) for alls, t. Consider the polynomialxn-1. Thecomplexfactorisation is obvious: the zeros of the x n-1 =n? k=1? x-e?kn .(1) One of these factors isx-1, and whennis even, another isx+ 1. The remaining factors can be combined in pairs of the form [x-e(k/n)][x-e(-k/n)] =x2-2xcos2πkn + 1 to give the factorisation into linear and quadraticrealfactors. We will describe a constructive factorisation into polynomials withintegercoefficients, and then present some applications to number theory. We write (a,b) for the gcd ofaand b, and E By definition, the number of members ofEnis Euler"sφ(n). Thecyclotomic polynomialsΦn are defined for alln≥1 by n(x) =? k?En? x-e?kn .(2) (This is the usual notation; be careful to distinguish Φ nandφ(n)!)

It is clear that Φ

nis a monic polynomial (with, apparently, complex coefficients) of degreeφ(n). We note some elementary cases: n= 1:E1={1}, hence Φ1(x) =x-1. n= 2:E2={1}ande(12 ) =-1, hence Φ2(x) =x+ 1. n= 4:E4={1,3}ande(14 ) =i, hence Φ4(x) = (x-i)(x+i) =x2+ 1.

1.1.For primep,

p(x) =xp-1x-1= 1 +x+···+xp-1. 1 Proof. Consider the factorisation ofxp-1 given by (1) (withn=p). To obtain Φp(x), remove the factorx-1 corresponding tok=p.? Letn≥3. Denote byE?nthe memberskofEnwithk φ(n) members. Sincee[(n-k)/n] =e(-k/n), we have the following factorisation of Φn(x) into quadratic real factors: n(x) =? k?E?n[x-e(k/n)][x-e(-k/n)] =? k?E?n(x2-2xcos2πkn + 1).(3)

We deduce some properties of Φ

n(x) as a function of a real variable.

1.2.For alln≥3,

(i)Φn(x)has real coefficients; (ii)Φn(0) = 1; (iii)Φn(x)>0for all realx; (iv)Φn(x)is strictly increasing forx >1; (v) for allx >0,(x-1)φ(n)<Φn(x)<(x+ 1)φ(n). Proof. (i) and (ii) are obvious. For-1< a <1, writefa(x) =x2-2ax+ 1. Then f a(x) = (x-a)2+ (1-a2)>0 for allx, and is strictly increasing forx≥1: hence (iii) and (iv). Also, (x-1)2< fa(x)<(x+ 1)2for allx >0: hence (v).?

1.3PROPOSITION.Letn≥2. Letφ(n) =mandΦn(x) =?m

r=0crxr. Then: (i)Φn(x) =xmΦn(1/x)forx?= 0, Proof. This is trivial forn= 2, so assumen >2. Write cos(2πk/n) =ak. By (3), x mΦn?1x k?E?nx 2?

1-2akx

+1x 2? k?E?n(x2-2akx+ 1) = Φn(x). Hence ?m r=0crxr=?m r=0crxm-r=?m r=0cm-rxrfor allx?= 0, socm-r=crfor eachr.? We now explain how the cyclotomic polynomials provide a factorisation ofxn-1.

1.4LEMMA.Letn=n1d. Then

Proof. By definition, Φd(x) =?

r?Ed[x-e(r/d)]. Nowr/d= (n1r)/nand (r,d) = 1 stated product.? 2

1.5THEOREM.For alln≥1,

x n-1 =? d|nΦ d(x).(4) runs through the divisors ofn, so doesn1=n/d. Hence d|nΦ d(x) =n? k=1[x-e(k/n)] =xn-1.?

1.6COROLLARY.Forn≥2,

?{Φd(x) :d|n,d >1}= 1 +x+···+xn-1. Proof. In (4), divide both sides by Φ1(x) =x-1. The statement follows by continuity atx= 1.? It follows at once from (4) that ifmdividesn, then ?{Φd(x) :d|n, d? |m}=xn-1x m-1.(5) A typical deduction (which will be generalised by later results) is:

1.7.For primep,

pk(x) =yp-1y-1= 1 +y+···+yp-1, wherey=xpk-1. In particular,Φ2k(x) =x2k-1+ 1. Proof. In (5), takem=pk-1andn=pk. The only divisor ofnthat is not a divisor of mispk. The statement follows.? Example. Letp,qbe distinct primes. By 1.5,xpq-1 = Φ1(x)Φp(x)Φq(x)Φpq(x). With

1.1, this gives

pq(x) =(xpq-1)(x-1)(xp-1)(xq-1).(6)

In particular,

2p(x) =xp+ 1x+ 1= 1-x+x2- ···+xp-1.

1.8THEOREM.For alln,Φn(x)has integer coefficients.

Proof. Assume that Φr(x) has integer coefficients for allr < n. By (4),xn-1 = n(x)gn(x), where g n(x) =? d|n,dWrite Φ n(x) =?m r=0crxr(wherem=φ(n)) andgn(x) =?n-m s=0asxs. By the induction hypothesis, eachasis an integer. Also,a0=gn(0) =-1. If any of the coefficientscrare not integers, letckbe the first one that is not. Then the coefficient ofxkin the product n(x)gn(x) isc0ak+c1ak-1+···+ck-1a1-ck, which is not an integer. But this product is x n-1, so this is a contradiction.? Alternative proof. By the division algorithm inZ[x], sincegn(x) is monic, there are polynomialsq(x),r(x), with integer coefficients, such thatxn-1 =q(x)gn(x) +r(x) and eitherr= 0 or degr Hence Φ n(a) is an integer whenais an integer. Also, for positive integersaandn≥2, n(a)≡Φn(0)≡1 moda. Note. It can be shown that Φn(x) is irreducible inZ[x], so that (4) is the complete factorisation ofxn-1 in this ring (e.g. [vdW, p. 160-161]). This is important in Galois theory, but not for the topics considered here.

1.9LEMMA.Ifnis odd, then the elements{n+ 2r:r?En}(considered mod2n)

compriseE2n. Proof. Suppose that (r,n) = 1 and thatddividesn+ 2rand 2n. Thendis odd, since n+ 2ris odd, soddividesn. Henced|2r, sod|r. Sod= 1. Hence (n+ 2r,2n) = 1. If n+ 2r≡n+ 2smod 2n, thenr≡smodn, so the elementsn+ 2r(r?En) are distinct mod 2n. Sinceφ(2n) =φ(n), the statement follows.?

1.10.Ifn≥3is odd, thenΦ2n(x) = Φn(-x).

Proof. Recall thate(12

+t) =-e(t). By the Lemma,

2n(x) =?

r?En? x-e?n+ 2r2n?? r?En? x+e?rn

Sinceφ(n) is even, this equals?

r?En[-x-e(r/n)] = Φn(-x).? Alternatively, one can give an induction proof of 1.10, using 1.5. M¨obius inversion of (4). The expression in (6) can be extended to generaln. Recall that the M¨obius functionμis defined byμ(1) = 1,μ(n) = (-1)kifnis square-free withkprime factors andμ(n) = 0 for othern. The M¨obius inversion theorem states:ifβn=? d|nαdfor alln≥1, thenαn=? d|nβdμ(n/d)forn≥1. By applying this to loganand logbn, we deduce: ifan>0 andbn=? d|nadfor alln, thenan=? d|nbμ(n/d) dfor alln. So (4) can be inverted as follows: 4

1.11THEOREM.For alln≥1andx?=±1,

n(x) =? d|n(xd-1)μ(n/d).(7) Proof. This follows in the way just stated forx >1, since thenxd-1>0 for eachd.

The statement can be rewritten in the form Φ

n(x)Q(x) =P(x), whereP(x) andQ(x) are polynomials. Since it holds forx >1, it holds for all realx.? A variant, valid also whenx= 1, is as follows: letfn(x) = 1 +x+···+xn-1(n≥2) andf1(x) = 1. By M¨obius inversion of 1.6, with Φ1(x) replaced by 1, we have forn≥2: n(x) =? d|nf d(x)μ(n/d).

We can now show that once Φ

nis known for square-free values ofn, it can be derived for othernby a simple substitution.

1.12THEOREM.Letn=pk11pk22...pkrr. Writep1p2...pr=n0andn1=n/n0.

ThenΦn(x) = Φn0(xn1).

Proof. The divisors ofn0are the numbersd=?r

j=1pεj j, with eachεjin{0,1}. Denote this set of divisors byd. Then n0(x) =? d?D(xd-1)μ(n0/d). The divisorseofnthat haveμ(n/e)?= 0 are the numbers?r j=1paj jwithaj≥kj-1 for each j. These are exactly the numbersn1d(d?D), andn/n1d=n0/d. Hence n(x) =? d?D(xn1d-1)μ(n0/d)= Φn0(xn1).?

1.13COROLLARY.Ifpis prime and does not dividem, then

mpk(x) = Φmpk-1(xp) = Φmp(xpk-1). Proof. Letmpk-1=n,mpk=n?and writen=n0n1andn?=n?0n?1as in 1.12. Then n ?0=n0andn?1=pn1. By 1.12, Φn?(x) = Φn(xp). The second equality follows by iteration, or similarly.?

In particular, Φ

4m(x) = Φ2m(x2) (and so is an even function) for anym.

Example. Letp,qbe distinct primes. Then Φpkq(x) = Φpq(y), wherey=xpk-1. In particular, Φ

2pk(x) = (yp+ 1)/(y+ 1). Also, Φ2kq(x) = (yq+ 1)/(y+ 1), wherey=x2k-1.

5 With the results now at our disposal, we can write down Φ n(x) for a selection of values ofn:nΦn(x) 1x-1 2x+ 1

3x2+x+ 1

4x2+ 1

5x4+x3+x2+x+ 1

6x2-x+ 1

8x4+ 1nΦn(x)

9x6+x3+ 1

10x4-x3+x2-x+ 1

12x4-x2+ 1

16x8+ 1

18x6-x3+ 1

20x8-x6+x4-x2+ 1

72x24-x12+ 1

Example. The factorisation ofx6-1 given by (4) is

(x-1)(x+ 1)(x2+x+ 1)(x2-x+ 1).

To determine Φ

n(x) whennhas two or more odd prime factors, one has to calculate coefficients, as in the following example.

Example. Determine Φ15(x). Denote it by?8

r=0crxr. By (6), (c8x8+c7x7+···+c1x+c0)(x3-1)(x5-1) = (x15-1)(x-1). Equating coefficients, we findc0= 1,c1=-1,c2= 0,c3=c0= 1,c4=c1=-1. By 1.3, c

8-r=cr. Hence

15(x) =x8-x7+x5-x4+x3-x+ 1.

Another deduction from 1.11 is the following identity, which turns out to be very useful:

1.14PROPOSITION.Ifpis prime,pdoes not dividemandk≥1, then for allx,

mpk(x) =Φm(xpk)Φ m(xpk-1). Proof. Writempk=n. The divisorsjofnwithμ(n/j)?= 0 are the numbersdpkand dp k-1for divisorsdofm. So Φn(x) =P1(x)P2(x), where P

1(x) =?

d|m(xdpk-1)μ(m/d)= Φm(xpk), P

2(x) =?

d|m(xdpk-1-1)μ(pm/d)=1Φ m(xpk-1), sinceμ(pm/d) =-μ(m/d). The statement is a polynomial identity, valid for all realx.? 6

1.15.Forn≥2,

n(1) =?pifn=pk(pprime,k≥1),

1otherwise.

Proof. The statement forn=pkis clear from 1.7. Otherwise,ncan be expressed as mp kwithp? |mandm >1,k≥1. By 1.14, n(1) =Φm(1)Φ m(1)= 1.? We sketch two alternative proofs, both illuminating. Proof 2. By 1.12, it is enough to show that Φn(1) = 1 fornof the formp1p2...pk, where k≥2. Assume this for lower values ofk. By 1.6,? d|n,d>1Φd(1) =n. Now Φpj(1) =pj, and by hypothesis, these are the only proper divisorsdofnwith Φd(1)?= 1. So the stated product isp1p2...pkΦn(1) =nΦn(1), hence Φn(1) = 1.?

Proof 3. By the variant of 1.11, Φn(1) =?

d|ndμ(n/d), so logΦn(1) =? d|nμ(n/d)logd. A well-known convolution identity equates this to the von Mangoldt function Λ(n), defined by: Λ(pk) = logpfor primepand Λ(n) = 0 for othern.?

Since Φ

n(x) is strictly increasing forx≥1, it follows that Φn(x)>1 for allx >1.

Recall that Φ

n(x) =xmΦn(1/x). By differentiation, one finds that Φ?n(1) =12 mΦn(1).

1.16.For integersa≥1andn≥2,Φn(a)is odd unlessn= 2kandais odd.

Proof. Ifais even, then Φn(a) is odd, since it is congruent to 1 moda. Ifais odd, then Φ n(a)≡Φn(1) mod 2. By 1.15, Φn(1) is odd except whenn= 2k.? We now restate identity (7) in a more specific form, concentrating on square-freen: let n=p1p2...pk, wherep1< p2< ... < pk, withk≥2 andp1≥3 (forp1= 2, then apply

1.10). LetD,Erespectively be the set of products of even and of odd numbers of thepj.

ThenDandEeach have 2k-1members, because?k

r=0(-1)r?k r?= (1-1)k= 0. Let

P(x) =?

d?D(xd-1), Q(x) =? e?E(xe-1).

Then Φ

n(x) equalsP(x)/Q(x) ifkis even andQ(x)/P(x) ifkis odd. We can deduce some information about the first (and last) few coefficients:

1.17.Letn=p1p2...pkas above, and letΦn(x) =?m

r=0crxr. Thenc0= 1and: 7 Proof. LetD?=D\ {1}. The smallest element ofD?isp1p2, so

P(x) = (x-1)?

d?D?(xd-1) = 1-x-xp1p2+p(x), wherep(x) is composed of higher powers ofx. The two smallest elements ofEarep1and p

2, soQ(x) = 1-xp1-xp2+q(x), whereq(x) is composed of higher powers.

Ifkis even, then Φn(x)Q(x) =P(x). By equating coefficients, we obtain the values stated forr < p1, alsocp1=c0= 1 andcp1+1=c1=-1. c r=c0= 1. Also,cp1-cp1-1=-1, socp1= 0, andcp1+1-cp1= 0.? Recall from 1.3 thatcm-r=cr. So, for example, for evenk, Φn(x) is of the form x m-xm-1+xm-p1-xm-p1-1+··· -xp1+1+xp1-x+ 1. The results onc1can be summarised in the formc1=-μ(n), since 1.12 shows that c

1= 0 whennis not square-free. Also, it follows from the original definition thatcm-1=

k?Ene(k/n), so our statement is equivalent to? k?Ene(k/n) =μ(n), a special case of the "Ramanujan sum". Note. From the examples seen so far, one might be led to suppose that the coefficients in Φ n(x) are always 1, 0 or-1. However, none of these examples have more than two distinct prime factors. Forn= 3×5×7 = 105, by solving for coefficients as above, one finds that c 7=-2.

Inequalities forΦn(x).

Recall from 1.2 that forn≥3, Φn(x) lies between (x-1)φ(n)and (x+ 1)φ(n). With

1.14, this gives the following inequality, which looks rather special, but is just what is needed

for the proof of Zsigmondy"s theorem in Section 2.

1.18.Letn=mpk, wherepis prime,k≥1andpdoes not dividem. Letx≥2and

y=xpk-1. Then?yp-1y+ 1?

φ(m)

<Φn(x)φ(m)

Further,Φn(x)>[yp-2(y-1)]φ(m).

8

Proof. By 1.14,

n(x) =Φm(yp)Φ m(y). Now (y-1)φ(m)<Φm(y)<(y+ 1)φ(m), and similarly foryp. The first statement follows. The second statement is derived by noting thatyp-1≥yp-2(y2-1).?

We now investigate the comparison between Φ

n(x) andxm, wherem=φ(n). (Any readers who are more interested in the number-theoretic applications can omit this and move on to section 2.) By 1.2, Φ improved toxmor [x/(x-1)]xm, depending on whether the number of prime factors ofnis even or odd. Since Φ n(x)/xm= Φn(1/x), the statement Φn(x)< xmforx≥2 is equivalent to Φ , and it is rather neater to prove the statement in this second form. We will apply the following simple Lemma to theP(x) andQ(x) introduced above. (1-xn1)(1-xn2)...(1-xnk)>1-xn11-x.

1-(a1+a2+···+ak). Hence the stated product is greater than

1-xn1-xn2- ··· -xnk>1-xn1(1 +x+x2+···) = 1-xn11-x.?

1.20PROPOSITION.Suppose thatnhaskdistinct prime factors. Writeφ(n) =m.

and (x-1)xm-1<Φn(x)< xmforx≥2. and x m<Φn(x)Recall that Φ n(x) isP(x)/Q(x) ifkis even andQ(x)/P(x) ifkis odd. The stated inequalities 9 Since 1?D, we haveP(x)<1-x. Meanwhile, the smallest member ofEisp1≥2, so, by the Lemma,

Q(x)>1-x21-x.

Q(x)-P(x)> x-x21-x=x-2x21-x≥0,

soP(x)< Q(x). Also,Q(x)<1-xp1. Apart from 1, the smallest member ofDisp1p2, so, by the

Lemma,

P(x)>(1-x)?

1-xp1p21-x?

= 1-x-xp1p2. So we will haveP(x)>(1-x)Q(x) ifxp1p2< xp1(1-x), orxp1(p2-1)<1-x. Now p (and in fact Note. Fork= 2, it is easily seen from (6) that 1-x <Φn(x)<1 for allxin (0,1). However, in general the inequalities comparing Φ n(x) with 1 do not extend to (0,1). Indeed, for anyk≥2 (even or odd), we have Φn(1) = 1 and Φ?n(1)>0, so that Φn(x)<1 on some interval (1-δ,1). Meanwhile, forn= 210 = 2×3×5×7, calculation (from (7), assisted by

1.10) shows that Φ

n(0.9)>1.

In particular, 2

m-1<Φn(2)<2mifkis even and 2m<Φn(2)<2m+1ifkis odd. One can deduce a fact that is quoted sometimes: Φ n(2)> nfor allnexcept 1 and 6. This is not really a natural comparison, and we will leave it aside. However, we include the following weaker statement, which can serve as an alternative to 1.18 for the purpose of Zsigmondy"s theorem:

1.21.Letn≥2and letpbe the largest prime factor ofn. ThenΦn(2)≥p, with strict

inequality except whenn= 6. Proof. It is enough to prove the statement for square-freen. For then ifn=n0n1as

in 1.12 (withn1>1), it follows that Φn(2) = Φn0(2n1)>Φn0(2)≥p, since Φn0(x) is strictly

increasing. Ifn=p(prime), then Φp(2) = 2p-1> p. So assume thatn=p1p2...pk, with k≥2 andpthe largestpj. Thenφ(n)≥p-1, so Φn(2)>2p-2, which is greater thanpif p≥5. This leaves only the casen= 2×3 = 6, and we note that Φ6(2) = 3.? 10

2. Prime factorisation ofΦn(a)and number-theoretic applications

We now consider the prime factorisaton of Φ

n(a). We show that it is closely connected to the order ofamodulo these primes. If (a,p) = 1, theorderofamodp, denoted by ord p(a), is the smallestn≥1 such thatan≡1 modp. Recall:ifordp(a) =nandris any positive integer such thatar≡1modp, thenris a multiple ofn. By Fermat"s little theorem, ifpis prime and ordp(a) =n, thenndividesp-1, sop≡1 modn. . It is not hard to determine orders using modular arithmetic. As a background to the following results, we record the values of ord p3 5 7 11 13 17 19 23 29 31 37 41 ord p(2) 2 4 3 10 12 8 18 11 28 5 36 20 ord p(3)-4 6 5 3 16 18 11 28 30 18 8 Example. There is no primepsuch that ordp(2) = 6. For thenpwould have to divide 2

6-1 = 63 = 32×7. However, ord3(2) = 2 and ord7(2) = 3.

We shall see, as an application of cyclotomic polynomials, that this example is quite exceptional (Zsigmondy"s theorem, below). We now start describing the connection. Note first that prime factors of Φ n(a) do not dividea, since Φn(a)≡1 moda.

2.1.Ifpis prime andordp(a) =n, thenpdividesΦn(a).

Proof. Thenpdividesan-1 and does not dividead-1 (so does not divide Φd(a)) for anyd < n. Sincean-1 =? d|nΦd(a), it follows thatpdivides Φn(a).? As a first application, we have the following estimate:

2.2.Leta≥2and letN(n,a)be the number of primespsuch thatordp(a) =n. Then

Without cyclotomic polynomials, one would obtain a similar estimate withnreplacing Primespwith ordp(a) =nare calledZsigmondy factorsof Φn(a) (they are also called primitiveprime factors ofan-1). Note that they satisfyp≡1 modn. We now show that non-Zsigmondy prime factors of Φ n(a) can occur. We will make repeated use of the following elementary lemma on congruences; 11

2.3LEMMA.Suppose thatpis prime anda≡1 modp. Then:

(i)(ap-1)/(a-1) = 1 +a+···+ap-1is a multiple ofp; (ii)ap≡1 modp2; (iii) Ifp≥3, then1 +a+···+ap-1≡pmodp2(so is not a multiple ofp2). Proof. (i), (ii). 1 +a+···+ap-1≡pmodp, so is a multiple ofp. Also,ap-1 = (a-1)(1 +a+···+ap-1), in which both factors are multiples ofp. (iii) Leta=kp+1. By the binomial theorem,ar≡1+rkpmodp2. Hence (sincep-1 is even), p-1? r=0a r≡p+kpp-1? r=0r=p+12 k(p-1)p2≡pmodp2.?

Recall that Φ

p(a) = 1 +a+···+ap-1for primep. So ifa≡1 modp(so that ord p(a) = 1), thenpitself is a factor (but not a Zsigmondy factor) of Φp(a). This remark can be generalised, as follows:

2.4PROPOSITION.Suppose thatpis prime andordp(a) =m. Letn=mpk, where

k≥1. ThenpdividesΦn(a). However, ifn≥3, thenp2does not divideΦn(a). Proof. We use (7). LetDbe the set of divisorsdofmwithμ(m/d)?= 0. The divisors jofnwithμ(n/j)?= 0 aredpkanddpk-1ford?D. Now (m,pt) = 1, somdividesdptonly whend=m. Hence whend < m,pdoes not divideadpt-1. By (7), Φn(a) is of the form b p-1b-1? d?D,d