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 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 memberskofEnwithkWe 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.? 21.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). With1.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,d1.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?rnSinceφ(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: 41.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+ 13x2+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, c8-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 P1(x) =?
d|m(xdpk-1)μ(m/d)= Φm(xpk), P2(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.? 61.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 apply1.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. LetP(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, soP(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 p2, 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 c1= 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). With1.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).
8Proof. 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)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 theLemma,
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 by1.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=n0n1asin 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