Luận văn Hệ số của đa thức chia đường tròn

,d<n Φd(−x) =Φn(−x). Vậy ta được điều phải chứng minh. Kết quả của Định lí 1.2.12 cho thấy rằng, đối với bài toán đánh giá hệ số, thay vì xét hệ số của tất cả các đa thức chia đường tròn thì ta chỉ cần xét hệ số của các đa thức Φn(x) với n là số lẻ. Ví dụ, để xác định đa thức chia đường tròn Φ2n(x) với n lẻ lớn hơn 1, chúng ta chỉ cần tìm đa thức chia đường tròn Φn(x). 11 Ví dụ 1.2.13. Hãy xác định đa thức chia đường tròn Φ42(x). Trước hết ta xác định đa thức Φ21(x). Theo Hệ quả 1.2.8 thì ta có Φ21(x) =Φ3.7(x) = Φ3 ( x7 ) Φ3(x) = x14+ x7+1 x2+ x+1 = x12− x11+ x9− x8+ x6− x4+ x3− x+1 Vì Φ42(x) =Φ21(−x) nên ta có Φ42(x) = x12+ x11− x9− x8+ x6− x4− x3+ x+1. 1.3 Tính chất thuận nghịch của đa thức chia đường tròn Quan sát các hệ số của Φ21(x) và Φ42(x) chúng ta thấy các hệ số của chúng đối xứng nhau qua hệ số của đơn thức x6 nên chúng là các đa thức thuận nghịch. Từ đó xuất hiện một câu hỏi đặt ra là có phải mọi đa thức chia đường tròn đều là đa thức thuận nghịch không. Trước khi trả lời câu hỏi này chúng ta nhắc lại định nghĩa và một vài tính chất của hàm Mo¨bius. Định nghĩa 1.3.1. Hàm Mo¨bius µ : Z+→{−1,0,1} được định nghĩa như sau µ (n) =  1 nếu n= 1, (−1)k nếu n= p1p2...pk với pk là các số nguyên tố phân biệt, 0 nếu có số nguyên tố p sao cho p2 là ước của n. Từ định nghĩa chúng ta thấy rằng µ là hàm nhân. Tức là, với m,n là các số nguyên dương bất kì và nguyên tố cùng nhau, ta có µ(mn) = µ(m).µ(n). Bổ đề 1.3.2. Cho n là số nguyên dương. Khi đó ∑ d|n µ(d) = { 1 nếu n= 1. 0 nếu n≥ 2. Chứng minh. Với n = 1 thì ước dương duy nhất của n là 1. Do đó, theo định nghĩa hàm Mo¨bius ta có ∑ d|n µ(d) = µ(1) = 1. 12 Cho n≥ 2. Ta đặt T là tích tất cả các số nguyên tố p là ước của n, tức là T = ∏ p|n p. Chú ý rằng nếu q là ước của n có chứa thừa số bình phương thì µ(q) = 0. Do đó ta có thể bỏ những chỉ số q như thế ra khỏi tổng. Do đó ta có ∑ d|n µ(d) =∑ d|T µ(d). Gọi p là một ước nguyên tố bất kỳ của T . Chú ý rằng mỗi ước của T là một ước d của Tp hoặc là dp với d là ước của T p . Vì thế từ tính chất hàm nhân của µ ta có ∑ d|T µ(d) =∑ d|Tp (µ(d)+µ(pd)) =∑ d|Tp (µ(d)+µ(p)µ(d)) =∑ d|Tp (µ(d)+(−1)1µ(d)) =∑ d|Tp (µ(d)−µ(d)) = 0. Ta có điều phải chứng minh. Trong số học chúng ta đã biết nếu f là hàm nhân thì F(n) = ∑ d|n f (d) cũng là hàm nhân. Từ Bổ đề trên ta có một kết quả quan trọng của hàm Mo¨bius, đó là công thức thuận nghịch sau đây. Mệnh đề 1.3.3. Ký hiệu Z+ là tập các số nguyên dương. Cho hai hàm số F, f : Z+→ Z+ sao cho F(n) = ∑ d|n f (d). Khi đó, ta có f (n) =∑ d|n µ(d)F (n d ) . Chứng minh. Theo giả thiết ∑ d|n µ(d)F (n d ) =∑ d|n ( µ(d)∑ t| nd f (t) ) . 13 Vì mọi ước t của n/d đều là ước của n nên ta có ∑ d|n µ(d)∑ t| nd f (t) =∑ t|n f (t) ∑ d|n,t| nd µ(d). Dễ thấy rằng với hai ước t và d của n, số d là ước của n/t khi và chỉ khi t là ước của n/d. Do vậy, ∑ t|n f (t) ∑ d|n,t| nd µ(d) =∑ t|n f (t)∑ d|nt µ(d). Theo Bổ đề 1.3.2, nếu n/t = 1 tức là t = n thì ∑ d|nt µ(d) = 1. Và nếu n/t ≥ 2 thì ∑ d|nt µ(d) = 0. Vì vậy, ta có ∑ t|n f (t)∑ d|nt µ(d) = f (n). Mệnh đề được chứng minh. Luật thuận nghịch cho tích được phát biểu như sau. Mệnh đề 1.3.4. Giả sử F, f : Z+ → Z+ là hai hàm số thỏa mãn điều kiện F(n) = ∏ d|n f (d). Khi đó ta có f (n) =∏d|nF (n d )µ(d). Chứng minh. Chứng minh của mệnh đề này tương tư như chứng minh củaMệnh đề 1.3.3 trong đó mỗi tổng được thay bằng tích và mỗi phép nhân liên quan đến hàm µ được thay bởi lũy thừa của hàm đó. Giả sử t là ước của nd . Theo giả thiết ta có F(n) = ∏ t| nd f (t). Suy ra ∏ d|n F (n d )µ(d) =∏ d|n ( ∏ t| nd f (t) )µ(d) . 14 Vì mọi ước t của n/d đều là ước của n nên ta có: ∏ d|n F (n d )µ(d) =∏ d|n ( ∏ t| nd f (t) )µ(d) =∏ t|n f (t) ∑d|n,t| nd µ(d) . Chú ý rằng nếu d và t đều là ước của n thì d là ước của n/t khi và chỉ khi t là ước của n/d. Do vậy, ta có ∏ d|n F (n d )µ(d) =∏ d|n ( ∏ t| nd f (t) )µ(d) =∏ t|n f (t) ∑d|n,t| nd µ(d) =∏ t|n f (t)∑d|nt µ(d). Vì thế theo Mệnh đề 1.3.2 nếu n/t = 1 tức là t = n thì ∑ d|nt µ(d) = 1. Và nếu n/t ≥ 2 thì ∑ d|nt µ(d) = 0. Do đó ∏ d|n F (n d )µ(d) =∏ d|n ( ∏ t| nd f (t) )µ(d) =∏ t|n f (t) ∑d|n,t| nd µ(d) =∏ t|n f (t)∑d|nt µ(d) = f (n), Mệnh đề được chứng minh. Hàm Mo¨bius được sử dụng để nghiên cứu đa thức chia đường tròn do tính chất sau đây Mệnh đề 1.3.5. Với mọi số nguyên dương n, Φn(x) =∏ d|n (xn/d−1)µ(d) =∏ d|n (xd−1)µ(n/d). Chứng minh. Vì xn−1=∏d|nΦd(x) nên áp dụng Mệnh đề 1.3.4 ta được ngay điều phải chứng minh. Định lí sau đây về tính thuận nghịch của đa thức chia đường tròn là kết quả chính của tiết này. 15 Định lý 1.3.6. Nếu n> 1 thì Φn(x) là đa thức thuận nghịch. Chứng minh. Ta sẽ chứng minh Φn(x) = xϕ(n)Φn (1 x ) . Ta xét Φn ( 1 x ) =∏ d|n ( 1 xd −1 )µ( nd ) =∏ d|n ( 1− xd )µ( nd ) .∏ d|n ( 1 xd )µ( nd ) Khi đó ta có, x∑d|n d.µ( n d ).Φn ( 1 x ) =∏ d|n (−1)µ( nd ) ( xd−1 )µ( nd ) = (−1)∑d|n µ( nd )∏ d|n ( xd−1 )µ( nd ) =Φn(x). Mà ∑d|nd.µ (n d ) = ϕ (n), ta được điều phải chứng minh. 1.4 Áp dụng Đa thức chia đường tròn có nhiều ứng dụng thú vị. Nội dung của phần này sẽ trình bày ứng dụng của đa thức chia đường tròn trong việc tìm cấp của một phần tử, xét ước nguyên tố của một số nguyên dương và chứng minh một trường hợp đặc biệt của Định lý Zsigmondy. Nội dung của tiết này được viết dựa theo tài liệu [1]. 1.4.1 Giá trị của đa thức chia đường tròn và cấp của phần tử Định nghĩa 1.4.1. Cho n > 1 và a là số nguyên dương, (a,n) = 1. Khi đó số nguyên dương k nhỏ nhất thỏa mãn ak ≡ 1 (mod n) được gọi là cấp của a modulo n. Kí hiệu là k = ordn (a). Ví dụ, ta có (2,7) = 1 và 23 ≡ 1 (mod 7) vì vậy ord7 (2) = 3. Cấp có liên hệ chặt chẽ với ước của các giá trị Φn(a) của các đa thức chia đường tròn. Trước khi phát biểu rõ ràng kết quả mô tả mối liên hệ này, ta cần hai kết quả chuẩn bị sau. 16 Bổ đề 1.4.2. Cho m,n là các số nguyên dương phân biệt và p là số nguyên tố. Giả sử tồn tại số nguyên a sao cho p|Φn(a) và p|Φm(a), khi đó p|mn. Chứng minh. Luôn tồn tại đa thức f (x) có hệ số nguyên thỏa mãn xmn−1=Φm(x)Φn(x) f (x) Đặt Φn(x) = g(x)(x−a)+Φn(a), Φm(x) = h(x)(x−a)+Φm(a), với g(x) , h(x) là các đa thức với hệ số nguyên. Khi đó xmn−1= [g(x)(x−a)+Φn(a)] [h(x)(x−a)+Φm(a)] f (x) Lấy đạo hàm hai vế tại x= a, ta được mn.amn−1 = g(a)Φm(a) f (a)+h(a)Φn(a) f (a)+Φn(a)Φm(a) f ′ (a) Vì p là ước của Φn(a) và Φm(a) nhưng p không là ước của a nên từ đẳng thức trên ta suy ra p là ước của mn. Ta được điều phải chứng minh. Hệ quả 1.4.3. Cho m,n là các số nguyên dương và p là số nguyên tố. Giả sử tồn tại số nguyên a để p|Φn(a) và p|Φm(a), khi đó tồn tại số nguyên s sao cho n= psm. Chứng minh. Đặtm= pα .m0,n= pβ .n0, trong đó α,β ,n0,m0 là các số tự nhiên và (m0, p) = (n0, p) = 1. Nếu α = 0 thì Φm0(a)≡Φm(a)≡ 0 (mod p). Nếu α ≥ 1, thì ta có ( Φm0(a) )pα ≡Φm0 (apα)≡Φm(a).Φm0 (apα−1)≡ 0 (mod p). 17 Suy ra Φm0(a)≡ 0 (mod p). Do đó, ta luôn có p|Φm0(a). Chứng minh tương tự, ta được p|Φn0(a). Nếu m0,n0 phân biệt thì p|m0n0 nhưng vì (m0n0, p) = 1 nên m0 = n0. Vậy m= psn với s= α−β . Ta được điều phải chứng minh. Định lý 1.4.4. Cho số nguyên tố p và số nguyên dương n sao cho (n, p) = 1. Cho a là một số nguyên bất kỳ. Khi đó p|Φn(a) khi và chỉ khi ordp(a) = n. Chứng minh. Ta sẽ chứng minh bằng quy nạp theo n. Với n = 1, hiển nhiên ta có p|Φ1(a) = a− 1 khi và chỉ khi ordp(a) = 1. Giả sử định lí đúng với mọi số nguyên dương nhỏ hơn n. Nếu p|Φn(a) thì p|an−1, đặt ordp(a) = m, ta có m≤min{n, p−1}. Giả sử m< n, theo giả thiết quy nạp suy ra p|Φm(a), do đó p|mn, điều này mâu thuẫn với (mn, p) = 1, cho nên m= n. Ngược lại, nếu ordp(a) = n thì p|an−1 và n|p−1, khi đó tồn tại số nguyên dương d là ước của n sao cho p|Φd(a), với d ≤ n ≤ p−1. Giả sử d < n, theo giả thiết quy nạp suy ra n = ordp(a) = d, mâu thuẫn với giả thiết. Vậy định lí đã được chứng minh. Từ định lí trên ta có thể xét các ước nguyên tố của Φn(a) qua hệ quả sau. Hệ quả 1.4.5. Cho số nguyên tố p và số nguyên dương n sao cho (n, p) = 1. Khi đó, với mọi số nguyên a thỏa mãn p|Φn(a) thì p≡ 1(mod n). Định nghĩa 1.4.6. Cho n> 1, a là số nguyên dương và (a,n) = 1. Khi đó, nếu ϕ(n) = ordn (a) thì a được gọi là một căn nguyên thủy modulo n. Kết quả của bổ đề sau đây sẽ là công cụ để chứng minh rằng mọi số nguyên tố p luôn tồn tại căn nguyên thủy modulo p. Bổ đề 1.4.7. Cho số nguyên tố p. Cho đa thức P(x) có bậc n với hệ số nguyên P(x) = anxn+an−1xn−1+ ...+a1x+a0 Giả sử tồn tại n+1 số nguyên b0, b1, ..., bn thỏa mãn đồng thời các điều kiện (i) bi 6= b j (mod p), 0≤ i 6= j ≤ n; 18 (2) P(bi)≡ 0 (mod p), 0≤ i≤ n. Khi đó ai ≡ 0 (mod p), 0≤ i≤ n. Chứng minh. Ta chứng minh theo phương pháp quy nạp. Nếu P(x) là đa thức hằng thì bổ đề hiển nhiên đúng. Giả sử bổ đề đúng với mọi đa thức hệ số nguyên có bậc nhỏ hơn n. Xét đa thức P(x) ∈ Z[x] với degP(x) = n, khi đó tồn tại đa thức Q(x) ∈ Z[x] với degQ(x)< n thỏa mãn P(x) = an n−1 ∏ i=0 (x−bi)+Q(x) . Suy ra Q(bi)≡ 0(mod p) , 0≤ i≤ n−1 Theo giả thiết quy nạp, suy ra các hệ số của Q(x) chia hết cho p, do đó an n−1 ∏ i=0 (bn−bi) = P(bn)−Q(bn)≡ 0(mod p)⇒ an ≡ 0(mod p) Khi đó, đa thức K (x) = P(x)− anxn = an−1xn−1 + ...+ a1x+ a0 thỏa mãn K (bi) ≡ 0(mod p) , 0 ≤ i ≤ n− 1. Do đó theo giả thiết quy nạp, ta suy ra ai ≡ 0(mod p) với mọi 0≤ i≤ n. Định lý 1.4.8. (Tồn tại căn nguyên thủy modulo p) Với mọi số nguyên tố p, luôn tồn tại số nguyên a sao cho ordp(a) = p−1. Chứng minh. Tồn tại đa thức T (x) ∈ Z[x] sao cho xp−1−1=Φp−1(x)T (x). Giả sử với mọi t ∈ {1,2, ..., p−1} thì Φp−1(t) không chia hết cho p, khi đó T (t)≡ 0(mod p) , 0≤ i≤ p−1 Vì degT (x)< p−1, nên theo bổ đề trên, suy ra các hệ số của T (x) chia hết cho p, do đó −1=Φp−1(0)≡ 0(mod p) . Mâu thuẫn trên suy ra tồn tại t0 ∈ {1,2, ..., p−1} sao choΦp−1(t0) chia hết cho p. Suy ra ordp(t0) = p−1. 19 1.4.2 Định lý Zsigmondy Định lí Zsigmondy là một trong những định lí quan trọng của của số học, có liên quan đến việc xét ước nguyên tố của các biểu thức có dạng an± bn, trong đó a,b,n là các số nguyên thỏa mãn (a,b) = 1, a > b ≥ 1,n > 1. Trong phần này, chúng ta sẽ đề cập đến một trong những ứng dụng của đa thức chia đường tròn là chứng minh trường hợp đặc biệt của định lí khi a> b= 1,n> 1. Trước hết chúng ta xét các bổ đề sau liên quan đến đa thức chia đường tròn. Bổ đề 1.4.9. Cho các số nguyên a,n > 1. Giả sử tất cả các ước nguyên tố của Φn(a) là các ước của n. Khi đó, chỉ xảy ra các trường hợp (i) n= 2,a= 2t−1 với t ≥ 2; (ii) Φn(a) = p là một số nguyên tố lẻ và n= ps.k với k = ordp(a),s≥ 1. Chứng minh. Nếu p là số nguyên tố sao cho p|Φn(a) thì (a, p) = 1. Ta đặt k = ordp(a), suy ra k|p−1, do đó (k, p) = 1. Suy ra p|Φn(a) và tồn tại số nguyên dương s thỏa mãn n = ps.k. Giả sử q là số nguyên tố sao cho q 6= p và q|Φn(a). Khi đó, ta cũng có n = qt .h với t là số nguyên dương và h = ordq(a). Vì n= ps.k= qh.t nên q|k, p|h, tuy nhiên k|p−1 và h|q−1 nên suy ra q≤ p−1 và p≤ q−1. Mâu thuẫn này suy ra Φn(a) chỉ có ước nguyên tố duy nhất là p. Trường hợp 1.Nếu p lẻ, đặt c= n p = ps−1k,ac= b+1 suy ra k|c nên p|ac−1= b. Ta có an−1 ac−1 = (b+1)n−1 b = p ∑ i=2 Cipb i−1+ p≡ p(mod p2) Vậy vp (an−1) = vp (ac−1)+1. Mặt khác, ta có xn−1=Φn(x).∏ d|c Φd(x). ∏ d|k,d 6=k Φpsd(x) = (xc−1) .Φn(x). ∏ d|k,d 6=k Φpsd(x). Do đó vp (an−1)≥ vp (Φn(a))+ vp (ac−1)≥ vp (ac−1)+1. 20 Vậy suy ra vp (Φn(a)) = 1, nên Φn(a) = p. Trường hợp 2. Nếu p= 2, suy ra a là số lẻ và 2 là ước nguyên tố duy nhất của Φn(a). Ta có k= ord2(a) = 1, suy ra n= 2s với s≥ 1, do đó Φn(a) =Φ2s(a) = a2 s−1 +1> 2. Nếu s≥ 2 thìΦn(a)≡ 2(mod4) nênΦn(a) có ít nhất một ước nguyên tố lẻ, điều này mâu thuẫn với nhận xét trên. Vậy s = 1,n = 2, suy ra Φn(a) = a+ 1 = 2t với t ≥ 2.Do đó, a= 2t−1. Bổ đề 1.4.10. Cho số nguyên a > 1,n = psk với plà số nguyên tố và ,k là các số nguyên dương thỏa mãn (k, p) = 1. Đặt l = ap s−1 , khi đó Φn(a)> ( lp−2 (l−1))ϕ(k) Chứng minh. Vì Φn(x) không có nghiệm thực lớn hơn 1 và lim x→+∞Φn(x) = +∞ nên Φn(x)> 0 với mọi x> 1. Khi đó, ta có Φn(a) = |Φn(a)|= ∣∣∣∣Φk(lp)Φk(l) ∣∣∣∣ Hơn nữa, |Φn(lp)|= ∏ 1≤ j≤k ( j,k)=1 ∣∣∣lp− ε jk ∣∣∣≥ (lp−1)ϕ(k) và |Φn(l)|= ∏ 1≤ j≤k ( j,k)=1 ∣∣∣l− ε jk ∣∣∣≤ (lp+1)ϕ(k) Dấu bằng trong hai bất đẳng thức trên không đồng thời xảy ra, do đó Φn(a)> ( lp−2 (l−1))ϕ(k). Kết quả chính của phần này là trường hợp đặc biệt của Định lý Zsigmondy 21 được phát biểu trong hai định lý sau. Định lý 1.4.11. Cho các số nguyên a,n> 1. Khi đó tồn tại số nguyên tố q là ước số của an−1 nhưng không phải là ước số của ai−1 với mọi số nguyên dương i< n, trừ các trường hợp (i) n= 2,a= 2t−1 với t ≥ 2; (ii) n= 6,a= 2. Chứng minh. Giả sử phản chứng, khi đó mọi ước nguyên tố p của Φn(a) đều thỏa mãn ordp(a) 6= n, suy ra p|n. Ta có Trường hợp 1. Với n= 2 thì a= 2t−1, t ≥ 2. Trường hợp 2. VớiΦn(a)= p là số nguyên tố lẻ và n= psk với k = ordp(a),s≥ 1. Khi đó, ta đặt l = ap s−1 ≥ 2, ta có p> ( lp−2 (l−1))ϕ(k) ≥ lp−2 ≥ 2p−2. Vì p là số nguyên tố lẻ nên bất đẳng thức trên chỉ đúng khi p = 3. Khi đó l = 2,ϕ(k) = 1 nên a = 2,s = 1,k = 1 hoặc k = 2. Suy ra n = 3 hoặc n = 6. Nhưng Φ3(a) = a2+a+1> 3 nên n= 6,a= 2. Định lý 1.4.12. Cho các số nguyên a,n > 1. Khi đó tồn tại số nguyên tố q là ước của an+1 nhưng không phải là ước của ai+1 với mọi số nguyên dương i< n, trừ trường hợp n= 3,a= 2. Chứng minh. Ta xét a2n− 1 khi đó tồn tại số nguyên tố q là ước của a2n− 1 nhưng q không là ước của ai−1 với mọi số nguyên dương i< n, trừ trường hợp 2n= 6,a= 2 (trường hợp 2n= 2 không xảy ra vì n> 1) tức là n= 3,a= 2. Ngoài ra, vì q|a2n−1= (an−1)(an+1), nhưng q không là ước của an−1 nên q|an+1, do đó định lí được chứng minh. 1.4.3 Một số bài toán khác Bài toán 1.4.13. Cho số nguyên dương n. Chứng minh rằng số 22n+22n−1+1 có ít nhất n ước nguyên tố phân biệt. 22 Lời giải. Ta có 22n+22n−1+1=Φ3 ( 22 n−1) = ∏ d|2n−1 Φ3d(2) Ta lại có Φ3d(2)> 1 với mọi ước nguyên dương d của 2n−1, do đó Φ3d(2) chứa ít nhất một ước nguyên tố. Mặt khác nếu p là ước chung củaΦ3d1(2) vàΦ3d2(2) với d1,d2 là các ước nguyên tố phân biệt của 2n−1. Suy ra p|d1d2 nên p = 2. Điều này mâu thuẫn vì Φ3d(2) là số lẻ. Vậy tất cả các ước nguyên tố của Φ3d(2) là phân biệt, như vậy ta được điều phải chứng minh. Bài toán 1.4.14. Cho số nguyên dương n> 1 và p1, p2, ..., pn là các số nguyên tố phân biệt lớn hơn 3. Chứng minh rằng 2p1p2...pn+1 có ít nhất 22 n−1 ước số phân biệt. Lời giải. Ta có 2p1p2...pn+1=Φ2 (2p1p2...pn) = ∏ d|p1p2...pn Φ2d(2). Chia 2n ước của p1p2...pn thành 2 tập hợp A và B, trong đó tập A gồm tất cả các số là tích một số chẵn các số nguyên tố trong các số p1, p2, ..., pn và tập B gồm tất cả các số là tích một số lẻ các số nguyên tố trong p1, p2, ..., pn. Khi đó |A| = |B| = 2n−1. Nếu p là ước chung của Φ2s(2), Φ2t(2) với s > t và s, t ∈ A thì ta có s= pkt với k ≥ 1. Điều này mâu thuẫn với định nghĩa s và t, suy ra với d ∈ A thì các ước nguyên tố của các số Φ2d(2) phân biệt. Vậy 2p1p2...pn+1 có ít nhất 22 n−1 ước số phân biệt. Sau đây ta có danh sách một số bài tập đề nghị. Bài tập 1. Cho số nguyên tố p và n,k là các số nguyên dương. Chứng minh rằng, nếu (p,n) = 1 thì Φpkn(x) = Φn ( xp k) Φn ( xpk−1 ) . Bài tập 2. Cho các số nguyên dương m,n thỏa mãn (m,n) = 1. Khi đó chứng minh rằng Φn (xm) = ∏ d|m Φdn(x). Bài tập 3. Hãy xác định đa thức chia đường tròn Φ1024(x). Bài tập 4. Hãy phân tích đa thức f (x) = x10+x5+1 thành tích của các đa thức có hệ số nguyên. Bài tập 5. Chứng minh rằng tồn tại vô số số nguyên dương n sao cho tất cả các ước nguyên tố của n2+n+1 không lớn hơn √ n. 23 Bài tập 6. Cho số nguyên a> 1, n= psk với p là số nguyên tố và s,k là các số nguyên thỏa mãn (k, p) = 1. Đặt l = ap s−1 , chứng minh rằng ( lp−1 l+1 )ϕ(k) <Φn(a)< ( lp+1 l−1 )ϕ(k) . Bài tập 7. Tìm tất cả các số nguyên dương x,y và số nguyên tố p sao cho px−1= 2y(p−1). Bài tập 8. Tìm bộ số nguyên dương (x,r, p,n) trong đó n,r> 1 và p là số nguyên tố thỏa mãn xr−1= pn. Bài tập 9. Tìm các số nguyên dương x,y và số nguyên tố p thỏa mãn px− yp = 1. 24 Chương 2 Hệ số của đa thức chia đường tròn Φn(x) Trong chương này chúng ta sẽ sử dụng các tính chất cơ bản của đa thức chia đường tròn trong chương trước để tìm hiểu các hệ số của các đa thức này. Nội dung chính của chương này xoay quanh câu hỏi khi nào tất cả các hệ số của Φn(x) nằm trong tập {−1,0,1}. Để làm việc này, chúng tôi sẽ lần lượt xét trường hợp n là tích của hai số nguyên tố lẻ, n là tích của ba số nguyên tố lẻ. Các kết quả chính của chương được tham khảo từ các tài liệu [8, 7, 3]. 2.1 Hệ số của đa thức Φpq(x) Để tìm hiểu các tính chất của hệ số của đa thức Φpq(x), chúng ta cần sử dụng một số bổ đề sau Bổ đề 2.1.1. Cho p,q là các số nguyên tố phân biệt. Khi đó (1) Φp(x) = xp−1+ xp−2+ ...+ x+1; (2) Φp(xq) =Φpq(x).Φp(x); (3) (xpq−1).Φpq(x) =Φp(xq).Φq(xp).(x−1). Chứng minh. Chúng ta có Φ1(x) = x−1 và xn−1= ∏ d|n Φd(x) 25 (1) Ta có Φp(x) = xp−1 ∏ d|p,d<p Φd(x) = xp−1 x−1 = xp−1+ xp−2+ ...+ x+1. (2) Theo Hệ quả 1.2.8 ta có Φp(xq) =Φpq(x).Φp(x). Tương tự ta cũng có Φq(xp) =Φpq(x).Φq(x). (3) Ta có xpq−1=∏ d|pq Φd(x) =Φpq(x).Φp(x).Φq(x).Φ1(x) Nhân cả hai vế của đẳng thức trên với Φpq(x) ta được (xpq−1)Φpq(x) = [Φpq(x).Φp(x)] . [Φpq(x).Φq(x)] .Φ1(x) Theo (2) ta suy ra được (xpq−1)Φpq(x) =Φp (xq) .Φq (xp) .(x−1) . Từ (2) và (3) của bổ đề này chúng ta thấy rằng degΦpq(x) =−deg(xpq−1)+degΦp(xq)+degΦq(xp)+1 =−pq+ p(q−1)+q(p−1)+1 = (p−1)(q−1)< pq. Bổ đề 2.1.2. Nếu p,q là các số nguyên tố phân biệt thì hệ số của đa thức Φq(xp).Φp(xq) thuộc tập hợp {0;1}. 26 Chứng minh. Ta có Φq(xp) = xp.(q−1)+ xp.(q−2)+ ...+ xp+1 Φp(xq) = xq.(p−1)+ xq.(p−2)+ ...+ xq+1 Nhân vế với vế của hai biểu thức trên ta được Φq(xp).Φp(xq) = (xp.(q−1)+ ...+ xp+1).(xq.(p−1)+ ...+ xq+1) = ∑ 0≤m<q 0≤n<p xmp+nq. Giả sử ở vế phải của biểu thức trên có hai phần tử có cùng số mũ. Tức là ta có mp+ nq = m′p+ n′q với 0 ≤ m < m′ < q. Khi đó (m−m′) p = (n′−n)q, mà (p,q) = 1 nên q là ước của m−m′. Nhưng 0<m−m′ < q, do đó điều này là vô lí. Vậy trong vế phải của biểu thức trên có p.q số hạng phân biệt. Vậy ta được điều phải chứng minh. Sử dụng kết quả của hai bổ đề trên chúng ta có thể chứng minh được kết quả sau đây của Migotti về hệ số của đa thức Φpq(x). Định lý 2.1.3 (Migotti). Nếu p,q là các số nguyên tố phân biệt thì các hệ số của Φpq(x) thuộc {−1;0;1}. Chứng minh. Với p,q là các số nguyên tố phân biệt thì ta có (xpq−1) .Φpq(x) =Φp (xq) .Φq (xp) .(x−1) . Theo Bổ đề 2.1.2 thì các hệ số của Φp (xq) .Φq (xp) thuộc {0;1} vì vậy các hệ số của xΦp (xq) .Φq (xp) cũng thuộc {0;1} và các hệ số của −Φp (xq) .Φq (xp) thuộc {−1;0}. Suy ra các hệ số của đa thức Φp (xq) .Φq (xp) .(x−1) thuộc {−1;0;1}. Giả sử Φpq(x) = amxm+am−1xm−1+ ...+a1x+a0. 27 Khi đó (xpq−1) .Φpq(x) =amxm+pq+am−1xm−1+pq+ ...+a0.xpq −amxm−am−1xm−1− ...−a1x−a0. Vì (xpq−1) .Φpq(x) =Φp (xq) .Φq (xp) .(x−1) và có các hệ số thuộc {−1;0;1} nên ai và −ai thuộc {−1;0;1} với i = 0,1,2, ...,m. Suy ra ai thuộc {−1;0;1} với i= 0,1,2, ...,m. Vậy ta được điều phải chứng minh. Hệ quả 2.1.4. (1) Nếu p,q là các số nguyên tố lẻ thì Φ2pq(x) có các hệ số thuộc {−1;0;1} . (2) Cho p,q là hai số nguyên tố phân biệt, α,β là các số nguyên dương. Khi đó, Φpαqβ (x) có các hệ số thuộc {−1;0;1} . Chứng minh. (1) Theo Định lí 1.2.12 ta có Φ2pq(x) = Φpq(−x) mà Φpq(x) có các hệ số thuộc tập {−1;0;1}. Suy ra, Φ2pq(x) có các hệ số thuộc tập {−1;0;1} . (2) Chúng ta có Φpαqβ (x) =Φ(pα−1qβ−1)(pq)(x) =Φpq ( xp α−1qβ−1 ) . Mà Φpq(x) có các hệ số thuộc {−1;0;1} cho nên Φpαqβ (x) cũng có các hệ số thuộc {−1;0;1} . Định lí sau đây sẽ cho chúng ta biết với những giá trị nào của k thì apq(k) =−1 hoặc apq(k) = 1 hoặc apq(k) = 0. Định lý 2.1.5. (Lam - Leung) (xem [8]) Cho r và s là các số nguyên không âm sao cho có duy nhất một cách viết (p−1)(q−1) = rp+ sq. Khi đó ta có: Φpq(x) = ( r ∑ i=0 xip )( s ∑ j=0 x jq ) − ( q−1 ∑ i=r+1 xip )( p−1 ∑ j=s+1 x jq ) x−pq Cho 0≤ k ≤ (p−1)(q−1) thì: (1) apq(k) = 1 nếu và chỉ nếu k = ip+ jq với i ∈ [0;r], j ∈ [0;s]; 28 (2) apq(k) =−1 nếu và chỉ nếu k+ pq= ip+ jq với i ∈ [r+1;q−1], j ∈ [s+1; p−1]; (3) apq(k) = 0 trong những trường hợp còn lại. Chứng minh. Chúng ta có ϕ(pq) = (p−1)(q−1). Theo giả thiết ϕ(pq) có thể biểu diễn duy nhất dạng (p−1)(q−1)= rp+sq với r,s là các số nguyên không âm. Khi đó thì r ≤ q−2, s≤ p−2. Bây giờ chúng ta sẽ chứng minh Φpq(x) = ( r ∑ i=0 xip )( s ∑ j=0 x jq ) − ( q−1 ∑ i=r+1 xip )( p−1 ∑ j=s+1 x jq ) x−pq. Giả sử ε = e 2pii pq với ε là một căn nguyên thủy bậc pq của đơn vị. Khi đó εq và ε p lần lượt là nghiệm của Φp(x) và Φq(x). Ta có Φq (ε p) = q−1 ∑ i=0 (ε p)i = 0 nên r ∑ i=0 (ε p)i =− q−1 ∑ r+1 (ε p)i, Φp (εq) = p−1 ∑ j=0 (εq) j = 0 nên s ∑ j=0 (ε p) j =− p−1 ∑ s+1 (εq) j. Nhân vế với vế của hai biểu thức trên ta được( r ∑ i=0 (ε p)i ) . ( s ∑ j=0 (εq) j ) = ( q−1 ∑ i=r+1 (ε p)i ) . ( p−1 ∑ j=s+1 (εq) j ) Biến đổi biểu thức bằng cách chuyển vế, ta được( r ∑ i=0 (ε p)i ) . ( s ∑ j=0 (εq) j ) − ( q−1 ∑ i=r+1 (ε p)i ) . ( p−1 ∑ j=s+1 (εq) j ) = 0 Do đó ε là nghiệm của đa thức f (x) = ( r ∑ i=0 (xp)i ) . ( s ∑ j=0 (xq) j ) − ( q−1 ∑ i=r+1 (xp)i ) . ( p−1 ∑ j=s+1 (xq) j ) .x−pq Vì ( r ∑ i=0 (xp)i ) . ( s ∑ j=0 (xq) j ) là đa thức monic có bậc là rp+sq= (p−1)(q−1) 29 với hệ số nguyên và đa thức ( q−1 ∑ i=r+1 (xp)i ) . ( p−1 ∑ j=s+1 (xq) j ) .x−pq cũng là đa thức monic có bậc (r+1)(q−1)+ (s+1)(p−1)− pq = (p−1)(q−1)−1 với hệ số nguyên nên f (x) là đa thức monic bậc (p−1)(q−1) = ϕ (pq) và có hệ số nguyên. Nếu ε ′ là một căn nguyên thủy bậc pq của đơn vị thì tương tự như trên ta cũng chứng minh được nó là nghiệm của f (x). Như vậy f (x) là đa thức monic, có hệ số nguyên, có bậc ϕ(pq) và mọi căn nguyên thủy bậc pq của đơn vị đều là nghiệm của f (x). Do đó f (x) =Φpq(x). Chúng ta thấy, nếu i, i′ ∈ [0;q−1] , j, j′ ∈ [0; p−1] và ip+ jq = i′p+ j′q hoặc ip+ jq = i′p+ j′q− pq thì q|(i− i′) và p|( j− j′). Như vậy i = i′, j = j′. Vậy khi thực hiện phép nhân vế phải của đa thức f (x) sẽ không có hai phần tử cùng bậc. Do f (x) =Φpq(x) nên ta có: (1) apq(k) = 1 nếu và chỉ nếu k = ip+ jq với i ∈ [0;r], j ∈ [0;s]; (2) apq(k) =−1 nếu và chỉ nếu k+ pq= ip+ jq với i ∈ [r+1;q−1], j ∈ [s+1; p−1]; (3) apq(k) = 0 trong những trường hợp còn lại. Hệ quả 2.1.6. Cho p< q. Các hệ số khác 0 của đa thứcΦpq(x) thay phiên nhau nhận các giá trị −1 và 1. Ở Chương 1 chúng ta đã khẳng định được các hệ số của đa thức chia đường tròn đối xứng nhau qua hệ số trung tâm. Vậy liệu chúng ta có thể xác định được hệ số trung tâm của đa thức Φpq(x) hay không? Hệ quả sau đây sẽ cho chúng ta câu trả lời. Hệ quả 2.1.7. Cho p< q. Đặt l = (p−1)(q−1) 2 . Hệ số trung tâm của Φpq(x) là apq (l) = (−1)r. Chứng minh. Nếu p= 2 thì ta cóΦ2q(x)=Φq(−x) như vậy a2q(l)= (−1)l.aq(l) mà aq(l) = 1 nên a2q(l) = (−1)l. Chúng ta đã biết rp+ sq= (p−1)(q−1) và s ≤ p− 2. Suy ra r = q−12 . Mặt khác ta có l = (2−1)(q−1)2 = q−12 , do đó l = r. Như vậy a2q(l) = (−1)r, r = l = q−12 . 30 Nếu 2< p< q khi đó r,s có cùng tính chẵn lẻ. Chúng ta xét hai trường hợp sau đây. Trường hợp r,s chẵn thì l = (p−1)(q−1)2 = r 2 p+ s 2q với r 2 ∈ [0;r] , s2 ∈ [0;s] , theo Định lí 2.1.5 thì ta có apq(l) = 1= (−1)r vì r chẵn. Trường hợp r và s lẻ, chúng ta có thể viết l+ pq= (p−1)(q−1)2 = r+q 2 p+ s+p 2 q. Vì r ≤ q−2 và s≤ p−2 nên r+q2 ∈ [r+1;q−1] , s+p2 ∈ [s+1; p−1]. Như vậy ta có l = r+q2 p+ s+p 2 q− pq với r+q2 ∈ [r+1;q−1] , s+p2 ∈ [s+1; p−1] nên theo Định lí 2.1.5 ta có apq(l) = −1 = (−1)r vì r lẻ. Vậy ta được điều phải chứng minh. 2.2 Hệ số của đa thức Φn(x) với n nhỏ Từ Định lí 2.1.3 và các kết quả trong Chương 1, ta có thông tin về hệ số của các đa thức Φn(x) trong trường hợp n nhỏ. Mệnh đề 2.2.1. Nếu số nguyên dương n có nhiều nhất hai ước nguyên tố lẻ thì các hệ số của Φn(x) nhận một trong các giá trị −1,0,1. Nói riêng, khẳng định luôn đúng đối với n< 105. Chứng minh. Để chứng minh mệnh đề ta xét các trường hợp sau đây. Trường hợp 1: nếu n= p là số nguyên tố, khi đó Φn(x) =Φp(x) = xp−1+ xp−2+ ...+ x+1, có các hệ số đều bằng 1. Trường hợp 2: n = pq, với p,q là các số nguyên tố lẻ phân biệt. Khẳng định là nội dung của Định lí 2.1.3. Trường hợp 3: n = 2pq, với p,q là các số nguyên tố lẻ phân biệt. Khẳng định được suy ra từ Định lý 1.2.12 và Định lí 2.1.3. Trường hợp 4: n= 2α pβqγ , với p,q là các số nguyên tố lẻ phân biệt, còn α,β ,γ là các số nguyên dương. Khi đó, ta có Φ2α pβqγ (x) =Φ(2α−1pβ−1qγ−1)(2pq)(x) =Φ2pq ( x2 α−1pβ−1qγ−1 ) . 31 Vì vậy, Φ2α pβqγ (x) cũng có các hệ số thuộc {−1;0;1}. Do đó