Số học thuật toán P2

Chia sẻ: Trần Bá Trung4 | Ngày: | Loại File: PDF | Số trang:60

Thêm vào BST

Báo xấu

244
lượt xem 122
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Số học thuật toán P2 là tài liệu tham khảo, rất hay để các bạn đam mê toán tham khảo, tài liệu bao gồm các kiến thức chuyên sâu về toán. Chúc các bạn học tốt.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Số học thuật toán P2

TRƯỜNG.......................... KHOA…………………… …………..o0o………….. Số học thuật toán
II. Thùc hµnh tÝnh to¸n trªn m¸y §èi víi tÊt c¶ c¸c ch−¬ng, tÝnh to¸n thùc hµnh trªn m¸y tÝnh víi ch−¬ng tr×nh Maple ®−îc b¾t ®Çu b»ng dßng lÖnh: [>with(numtheory); C¸c phÐp to¸n sè häc ( phÐp céng [+], phÐp trõ [-], phÐp nh©n [*], phÐp chia [/], phÐp luü thõa [^], khai c¨n bËc hai [sqrt(.)],...) ®−îc viÕt vµ thùc hiÖn theo thø tù quen biÕt. Lu«n lu«n ghi nhí r»ng cuèi dßng lÖnh ph¶i lµ dÊu chÊm phÈy (;) hoÆc dÊu (:). Muèn thùc hiÖn dßng lÖnh nµo th× ph¶i ®−a con trá vÒ dßng lÖnh ®ã (sau dÊu chÊm phÈy) vµ nhÊn phÝm [Enter]. H·y thùc hiÖn c¸c dßng lÖnh theo ®óng tr×nh tù tr−íc sau, v× mét sè tÝnh to¸n trong c¸c b−íc sau cã thÓ yªu cÇu kÕt qu¶ tõ c¸c b−íc tr−íc. om m II. 1. Thùc hµnh kiÓm tra mét sè lµ sè nguyªn tè §Ó kiÓm tra mét sè n cã ph¶i lµ sè nguyªn tè hay kh«ng ta thùc hiÖn lÖnh nh− sau: o [>isprime(n); .C Sau dÊu (;) Ên phÝm “Enter”. NÕu trªn mµn h×nh hiÖn ra ch÷ “true” th× n lµ sè .C nguyªn tè, nÕu trªn mµn h×nh hiÖn ra ch÷ “false” th× n lµ hîp sè. ThÝ dô: Sè 2546789 cã ph¶i lµ sè nguyªn tè hay kh«ng? thh [>isprime(n); False at a VËy 2546789 kh«ng ph¶i lµ sè nguyªn tè. II. 2. Thùc hµnh t×m −íc chung lín nhÊt nM M §Ó thùc hµnh t×m −íc chung lín nhÊt cña hai sè a vµ b, h·y vµo dßng lÖnh cã có ph¸p nh− sau: [>gcd(a,b); n Sau dÊu (;) Ên phÝm “Enter” th× viÖc t×m −íc chung lín nhÊt sÏ ®−îc thùc hiÖn vµ sÏ V cã ngay kÕt qu¶. V ThÝ dô: T×m −íc sè chung lín nhÊt cña 2 sè 157940 vµ 78864. Thùc hiÖn b»ng c©u lÖnh sau: [> gcd(157940,78800); 20 VËy −íc chung lín nhÊt cña 157940 vµ 78864 lµ 20. II. 3. Ph©n tÝch ra thõa sè nguyªn tè §Ó ph©n tÝch sè n ra thõa sè nguyªn tè ta thùc hiÖn lÖnh sau: 30
[>ifactor(n); Sau dÊu (;) Ên phÝm “Enter” th× viÖc ph©n tÝch n ra thõa sè nguyªn tè sÏ ®−îc thùc hiÖn vµ sÏ cã ngay kÕt qu¶. ThÝ dô: Ph©n tÝch sè 122333444455555666666777777788888888999999999 ra thõa sè nguyªn tè. Ta thùc hiÖn nh− sau: [> ifactor(122333444455555666666777777788888888999999999); om m (3)(12241913785205210313897506033112067347143)(3331) Ta còng cã thÓ dïng lÖnh trªn ®Ó kiÓm tra xem mét sè n cã ph¶i lµ sè nguyªn tè hay o kh«ng II. 4. Thùc hµnh kiÓm tra mét sè lµ sè Carmichael .C .C Ta nhí l¹i §Þnh lÝ 2. 17 nh− sau: §Þnh lÝ 2.17. NÕu n=q1q2...qk, trong ®ã qj lµ c¸c sè nguyªn tè kh¸c nhau tho¶ m·n (qj-1) |(n-1), th× n lµ sè Carmichael. thh Do ®ã ®Ó kiÓm tra xem mét sè n cã ph¶i lµ sè Carmichael hay kh«ng ta thùc hiÖn at theo c¸c b−íc sau: a B−íc 1: Ph©n tÝch n thµnh tÝch c¸c thõa sè nguyªn tè, ta thùc hiÖn b»ng dßng lÖnh: nM [>ifactor(n); M Sau dÊu (;) Ên phÝm “Enter” trªn mµn h×nh sÏ hiÖn ra kÕt qu¶ ph©n tÝch n ra thõa sè nguyªn tè. NÕu n lµ hîp sè vµ cã d¹ng n=q1q2...qk, trong ®ã qj lµ c¸c sè nguyªn tè kh¸c nhau th× thùc hiÖn tiÕp b−íc kiÓm tra thø 2. NÕu kh«ng th× cã thÓ kh¼ng ®Þnh n n kh«ng ph¶i lµ sè Carmichael. V B−íc 2:. Thùc hiÖn c¸c phÐp tÝnh chia (n-1):(qj-1), ta thùc hiÖn b»ng dßng lÖnh sau: V [>(n-1)/(qj-1); Sau dÊu (;) Ên phÝm “Enter” trªn mµn h×nh sÏ hiÖn ra kÕt qu¶ th−¬ng cña phÐp chia. NÕu víi mäi j=1,2, ..., k c¸c th−¬ng t×m ®−îc lµ c¸c sè nguyªn th× ta kh¼ng ®Þnh n lµ sè Carmichael, nÕu kh«ng th× tr¶ lêi kh«ng ph¶i. ThÝ dô 1: Sè 6601 cã ph¶i lµ sè Carmichael hay kh«ng? Thùc hiÖn kiÓm tra nh− sau: [>ifactor(6601); (7)(23)(41) 31
6601 ®−îc ph©n tÝch thµnh c¸c thõa sè nguyªn tè kh¸c nhau, vËy cã thÓ nghi ngê nã lµ sè Carmichel. §Ó kiÓm tra xem nã cã thùc sù lµ sè Carmichel hay kh«ng, ta thùc hiÖn c¸c lÖnh sau: [>(6601-1)/(7-1); 1100 [>(6601-1)/(23-1); 300 [>(6601-1)/(41-1); 165 VËy 6601 lµ sè Carmichael. om m ThÝ dô 2: Sè 6 cã ph¶i lµ sè Carmichael hay kh«ng? Thùc hiÖn kiÓm tra nh− sau: o [>ifactor(6); (2)(3) .C .C [>(6-1)/(2-1); 5 thh [>(6-1)/(3-1); 5 at 2 a VËy 6 kh«ng ph¶i lµ sè Carmichael. nM M ThÝ dô 3: Sè 45 cã ph¶i lµ sè Carmichael hay kh«ng? Thùc hiÖn kiÓm tra nh− sau: n [>ifactor(45); (3)2(5) V V Sè 45 kh«ng tho¶ m·n b−íc thø nhÊt. VËy 45 kh«ng ph¶i lµ sè Carmichael. II. 5. Thùc hµnh kiÓm tra mét sè lµ gi¶ nguyªn tè Cho hai sè nguyªn d−¬ng n, b. §Ó kiÓm tra xem n cã ph¶i lµ sè gi¶ nguyªn tè c¬ së b hay kh«ng ta thùc hiÖn c¸c b−íc nh− sau: B−íc 1: KiÓm tra n lµ hîp sè, ta thùc hiÖn dßng lÖnh: [>isprime(n); 32
Sau dÊu (;) Ên phÝm “Enter”. NÕu trªn mµn h×nh hiÖn ra ch÷ “true” th× n lµ sè nguyªn tè, nÕu trªn mµn h×nh hiÖn ra ch÷ “false” th× n lµ hîp sè. NÕu n lµ sè nguyªn tè th× n kh«ng ph¶i lµ sè gi¶ nguyªn tè c¬ së b. NÕu ng−îc l¹i thùc hiÖn tiÕp b−íc 2. B−íc 2: KiÓm tra ®ång d− thøc bn-b ≡ 0(mod n), thùc hiÖn b»ng dßng lÖnh: [>b&^n-b mod n; Sau dÊu (;) Ên phÝm “Enter” trªn mµn h×nh sÏ hiÖn ra kÕt qu¶. NÕu ®ã lµ sè 0 th× n lµ sè gi¶ nguyªn tè c¬ së b. ThÝ dô1: Sè 561 cã ph¶i lµ sè gi¶ nguyªn tè c¬ së 2 hay kh«ng? Ta thùc hiÖn c¸c lÖnh sau: [>isprime(561); om m false [>2&^561-2 mod 561; o 0 VËy 561 lµ sè gi¶ nguyªn tè c¬ së 2. .C .C ThÝ dô 2: Sè 12241913785205210313897506033112067347143 cã ph¶i lµ sè gi¶ nguyªn tè c¬ së 8 hay kh«ng? Ta thùc hiÖn c¸c lÖnh sau: thh [>ispime(12241913785205210313897506033112067347143); at true a Sè 12241913785205210313897506033112067347143 lµ mét sè nguyªn tè. Do ®ã 12241913785205210313897506033112067347143 kh«ng ph¶i lµ sè gi¶ nguyªn tè nM M c¬ së 8. ThÝ dô 3: Sè 326 cã ph¶i lµ sè gi¶ nguyªn tè c¬ së 3 hay kh«ng? n Ta thùc hiÖn c¸c lÖnh sau: [>isprime(326); V V false [>3&^326-3 mod 326; 6 VËy 326 lµ kh«ng ph¶i lµ sè gi¶ nguyªn tè c¬ së 3. II. 6. Thùc hµnh kiÓm tra mét sè lµ sè gi¶ nguyªn tè m¹nh Cho n lµ sè nguyªn d−¬ng lÎ, b lµ sè nguyªn d−¬ng. §Ó kiÓm tra n cã ph¶i lµ sè gi¶ nguyªn tè m¹nh c¬ së b hay kh«ng ta thùc hiÖn theo c¸c b−íc sau: B−íc 1: KiÓm tra n lµ hîp sè, ta thùc hiÖn b»ng dßng lÖnh: 33
[>isprime(n); Sau dÊu (;) Ên phÝm “Enter”. NÕu trªn mµn h×nh hiÖn ra ch÷ “true” th× n lµ sè nguyªn tè, nÕu trªn mµn h×nh hiÖn ra ch÷ “false” th× n lµ hîp sè. NÕu n lµ sè nguyªn tè th× n kh«ng ph¶i lµ sè gi¶ nguyªn tè m¹nh c¬ së b. NÕu ng−îc l¹i thùc hiÖn tiÕp b−íc 2. B−íc 2: Ph©n tÝch n-1 ra thõa sè nguyªn tè, ta thùc hiÖn b»ng dßng lÖnh: [>ifactor(n-1); Sau dÊu (;) Ên phÝm “Enter” trªn mµn h×nh sÏ hiÖn ra sù ph©n tÝch cña n-1 vµ ta thu ®−îc kÕt qu¶ cã d¹ng n-1=2st, trong ®ã s lµ sè nguyªn d−¬ng, t lµ sè nguyªn d−¬ng lÎ. B−íc 3: KiÓm tra ®ång d− thøc bt-1 ≡ 0(mod n). Vµo lÖnh om m [>b&^t-1 mod n; Sau dÊu (;) Ên phÝm “Enter” trªn mµn h×nh sÏ hiÖn ra kÕt qu¶. NÕu ®ã lµ sè 0 th× n lµ o sè gi¶ nguyªn tè m¹nh c¬ së b, nÕu kÕt qu¶ lµ mét sè kh¸c 0 ta thùc hiÖn tiÕp b−íc 4. j B−íc 4: KiÓm tra c¸c ®ång d− thøc (b 2 t + 1) ≡ 0(mod n) víi j=0,...s-1, ta thùc hiÖn dßng lÖnh: .C .C [>seq (b&^((2^j)t)+1 mod n, j=0..s-1); h Sau dÊu (;) Ên phÝm “Enter” trªn mµn h×nh sÏ hiÖn ra d·y kÕt qu¶. NÕu trong d·y kÕt th qu¶ cã mét sè lµ sè 0 th× n lµ sè gi¶ nguyªn tè m¹nh c¬ së b. at ThÝ dô: Sè 2047 cã ph¶i lµ sè gi¶ nguyªn tè m¹nh c¬ së 2 hay kh«ng? a Thùc hiÖn kiÓm tra nh− sau: nM M [>isprime(2047); false Do ®ã n lµ hîp sè. TiÕp tôc thùc hiÖn lÖnh n [>ifactor(n-1); V V (2)(3)(11)(31) TiÕp tôc thùc hiÖn lÖnh [>2&^(3*11*31)-1 mod 2047; 0 VËy 2047 lµ sè gi¶ nguyªn tè m¹nh c¬ së 2. II. 7. Thùc hµnh biÓu diÔn mét sè d−íi d¹ng ph©n sè liªn tôc 1. BiÓu diÔn sè n d−íi d¹ng ph©n sè liªn tôc theo c¸ch th«ng th−êng víi sè th−¬ng trong biÓu diÔn lµ k, ta dïng lÖnh: [>cfrac(n,k); 34
Sau dÊu (;) Ên phÝm “Enter” trªn mµn h×nh sÏ xuÊt hiÖn kÕt qu¶. ThÝ dô: BiÓu diÔn π d−íi d¹ng ph©n sè liªn tôc theo c¸ch th«ng th−êng víi 6 th−¬ng. Ta thùc hiÖn lÖnh: [> cfrac (Pi,6); 1 3+ 1 7+ 1 15 + 1 1+ om 1 m 292 + 1 1+ 1+... o 2. BiÓu diÔn sè n d−íi d¹ng ph©n sè liªn tôc theo c¸ch ®¬n gi¶n víi sè ch÷ sè trong biÓu diÔn lµ k, ta dïng lÖnh: .C .C [>cfrac(n,k,’quotients’); Sau dÊu (;) Ên phÝm “Enter” trªn mµn h×nh sÏ xuÊt hiÖn kÕt qu¶. ThÝ dô: BiÓu diÔn π d−íi d¹ng ph©n sè liªn tôc theo c¸ch viÕt ®¬n gi¶n víi 100 ch÷ thh sè biÓu diÔn. at Ta thùc hiÖn lÖnh: a [> cfrac (Pi,100,’quotients’); nM M [3,7,15,1,292,1,1,1,2,1,3,1,14,2,1,1,2,2,2,2,1,84,2,1,1, 15,3,13,1,4,2,6,6,99,1,2,2,6,3,5,1,1,6,8,1,7,1,2,3,7,1, 2,1,1,12,1,1,1,3,1,1,8,1,1,2,1,6,1,1,5,2,2,3,1,2,4,4,16, 1,161,45,1,22,1,2,2,1,4,1,2,24,1,2,1,3,1,2,1,1,10,2,...] n 3. BiÓu diÔn sè n d−íi d¹ng ph©n sè liªn tôc theo chu kú tuÇn hoµn, ta dïng lÖnh: [>cfrac(n,’periodic’); V V Sau dÊu (;) Ên phÝm “Enter” trªn mµn h×nh sÏ xuÊt hiÖn kÕt qu¶. ThÝ dô: BiÓu diÔn 31/2 d−íi d¹ng ph©n sè liªn tôc theo chu kú tuÇn hoµn. Ta thùc hiÖn lÖnh: [>cfrac (3^(1/2),'periodic'); 1 1+ 1 1+ 1 2+ 1 1+ 2 +... 35
4. BiÓu diÔn sè n d−íi d¹ng ph©n sè liªn tôc theo chu kú tuÇn hoµn ®¬n gi¶n, ta dïng lÖnh: [>cfrac (n,'periodic','quotients'); Sau dÊu (;) Ên phÝm “Enter” trªn mµn h×nh sÏ xuÊt hiÖn kÕt qu¶. ThÝ dô: BiÓu diÔn 31/2 d−íi d¹ng ph©n sè liªn tôc theo chu kú tuÇn hoµn ®¬n gi¶n. Ta thùc hiÖn lÖnh: [> cfrac (3^(1/2),'periodic','quotients'); [[1], [1, 2]] II. 8. Thùc hµnh t×m ph©n sè héi tô thø k cña mét sè om m §Ó thùc hµnh t×m ph©n sè héi tô thø k cña mét sè n, ta thùc hiÖn theo c¸c lÖnh sau: Buíc 1: BiÓu diÔn n d−íi d¹ng ph©n sè liªn tôc o [> cf:= cfrac(n); Sau dÊu (;) Ên phÝm “Enter” trªn mµn h×nh sÏ xuÊt hiÖn sù biÓu diÔn .C .C B−íc 2: TÝnh ph©n sè héi tô thø k [> nthconver(cf,k); h Sau dÊu (;) Ên phÝm “Enter” trªn mµn h×nh sÏ xuÊt hiÖn ra kÕt qu¶. th Trong qu¸ tr×nh thùc hiÖn ta kh«ng cÇn biÕt kÕt qu¶ hiÖn thÞ ë b−íc 1, do ®ã cã thÓ at thay dÊu (;) b»ng dÊu (:) ë dßng lÖnh ®Çu tiªn ([>cf:=cfrac(n):). Khi ®ã trªn a mµn h×nh sÏ hiÖn ra dÊu nh¾c ([>) ®Ó thùc hiÖn tiÕp lÖnh thø 2. ThÝ dô: TÝnh ph©n sè héi tô thø 5 cña e. nM M Ta thùc hiÖn nh− sau: [> cf:= cfrac(exp(1)); n 1 cf : = 2 + 1 1+ V V 1 2+ 1 1+ 1 1+ 1 4+ 1 1+ 1 1+ 1 6+ 1+... [> nthconver(cf,5); 36
87 32 87 Nh− vËy, ph©n sè héi tô thø 5 cña e lµ . 32 II. 8. Thùc hµnh ®æi c¬ sè 1. §Ó thùc hµnh ®æi mét sè n tõ c¬ 10 sang c¬ sè b ta dïng dßng lÖnh sau: [>convert(n,base,b); Sau dÊu (;) Ên phÝm “Enter” trªn mµn h×nh sÏ hiÖn lªn mét dßng kÕt qu¶. Chó ý r»ng kÕt qu¶ ®−a ra trªn mµn h×nh ®−îc viÕt theo thø tù ng−îc l¹i. om ThÝ dô 1: §æi sè 24564 tõ c¬ sè 10 sang c¬ sè 6. m Ta thùc hµnh nh− sau: [>convert(24564,base,6); o .C .C VËy ta ®−îc sè lµ (305420)6. [0, 2, 4, 5, 0, 3] Chó ý: Trong tr−êng hîp c¬ sè b >10, ta vÉn thùc hiÖn dßng lÖnh ®æi c¬ sè nh− thh b×nh th−êng. Tuy nhiªn, sau khi nhËn ®−îc kÕt qu¶, ®Ó tr¸nh nhÇm lÉn ta thùc hiÖn viÖc ®Æt t−¬ng øng c¸c sè lín h¬n 10 víi c¸c kÝ hiÖu nµo ®ã. Ta xem vÝ dô sau: at ThÝ dô 2: §æi sè 45676 tõ c¬ sè 10 sang c¬ sè 15, trong ®ã ®Æt 10=A, a 11=B,12=C,13=D,14=E. nM Ta thùc hµnh nh− sau: M [>L:=convert(45676,base,6): [>subs(10=A,11=B,12=C,13=D,14=E,L); n V [1, 0, 8, D] V VËy ta ®−îc sè lµ (D801)15. 2. §Ó thùc hµnh ®æi mét sè n tõ c¬ sè a sang c¬ sè b ta dïng dßng lÖnh sau: [> convert(n,base,a,b); Sau dÊu (;) Ên phÝm “Enter” trªn mµn h×nh sÏ hiÖn lªn mét dßng kÕt qu¶. Chó ý r»ng kÕt qu¶ ®−a ra trªn mµn h×nh ®−îc viÕt theo thø tù ng−îc l¹i. ThÝ dô: §æi sè 305420 trong c¬ sè 6 sang c¬ sè 10. Ta thùc hiÖn dßng lÖnh 37
[> convert([0,2,4,5,0,3],base,6,10); [4, 6, 5, 4, 2] VËy ta cã kÕt qu¶ lµ (24564)10 om m o .C .C thh at a nM M n V V 38
Ch−¬ng 3 C¸c hµm sè häc Khi nghiªn cøu c¸c sè nguyªn, ta th−êng lµm viÖc víi c¸c ®¹i l−îng nh−: sè c¸c −íc cña mét sè nguyªn tè cho tr−íc, tæng c¸c −íc cña nã, tæng c¸c luü thõa bËc k cña c¸c −íc,... Ngoµi nh÷ng vÝ dô ®ã cßn cã rÊt nhiÒu hµm sè häc quan träng kh¸c. Trong ch−¬ng nµy, ta chØ xÐt s¬ qua mét vµi hµm quan träng. PhÇn lín cña ch−¬ng ®−îc giµnh cho hµm Euler, lµ mét trong nh÷ng hµm sè häc quan träng nhÊt. §1. §Þnh nghÜa. om m §Þnh nghÜa 3.1. Hµm sè häc tøc lµ hµm x¸c ®Þnh trªn tËp hîp c¸c sè nguyªn d−¬ng. o §Þnh nghÜa 3.2. Mét hµm sè häc f ®−îc gäi lµ nh©n tÝnh nÕu víi mäi n, m nguyªn tè cïng nhau, ta cã f(mn)=f(m)f(n). Trong tr−êng hîp ®¼ng thøc ®óng víi mäi m,n .C (kh«ng nhÊt thiÕt nguyªn tè cïng nhau), hµm f ®−îc gäi lµ nh©n tÝnh m¹nh. .C Nh÷ng vÝ dô ®¬n gi¶n nhÊt vÒ hµm nh©n tÝnh (m¹nh) lµ: f(n)=n vµ f(n)=1. DÔ chøng minh tÝnh chÊt sau ®©y: nÕu f lµ mét hµm nh©n tÝnh, n lµ sè nguyªn d−¬ng h cã khai triÓn thµnh thõa sè nguyªn tè d¹ng n=p1a1p2a2...pkak, th× f(n) ®−îc tÝnh theo th c«ng thøc at f(n)=f(pa1)f(pa2)...f(pak). a nM M §2. Phi hµm Euler. n Trong c¸c hµm sè häc, hµm Euler mµ ta ®Þnh nghÜa sau ®©y cã vai trß rÊt quan träng. §Þnh nghÜa 3.3. Phi- hµm Euler φ (n) lµ hµm sè häc cã gi¸ trÞ t¹i n b»ng sè c¸c sè V V kh«ng v−ît qu¸ n vµ nguyªn tè cïng nhau víi n. VÝ dô. Tõ ®Þnh nghÜa ta cã: φ (1)=1, φ (2)=1, φ (3)=2, φ (4)=2, φ (5)=4, φ (6)=2, φ (7)=6, φ (8)=4 , φ (9)=6, φ (10)=4. Tõ ®Þnh nghÜa trªn ®©y ta cã ngay hÖ qu¶ trùc tiÕp: Sè p lµ nguyªn tè khi vµ chØ khi φ (p)=p-1. NÕu ®Þnh lÝ Fermat bÐ cho ta c«ng cô nghiªn cøu ®ång d− modulo mét sè nguyªn tè, th× Phi-hµm Euler ®−îc dïng ®Ó xÐt ®ång d− modulo mét hîp sè. Tr−íc khi ®i vµo vÊn ®Ò ®ã, ta cÇn mét sè ®Þnh nghÜa sau. 39
§Þnh nghÜa 3.4. HÖ thÆng d− thu gän modulo n lµ tËp hîp φ (n) sè nguyªn sao cho mçi phÇn tö cña tËp hîp nguyªn tè cïng nhau víi n , vµ kh«ng cã hai phÇn tö nµo ®ång d− víi nhau modulo n. Nãi c¸ch kh¸c tõ hÖ thÆng d− ®Çy ®ñ modolo n, ®Ó lËp hÖ thÆng d− thu gän, ta chØ gi÷ l¹i nh÷ng gi¸ trÞ nµo nguyªn tè cïng nhau víi n. VÝ dô. C¸c sè 1,2,3,4,5,6 lËp thµnh hÖ thÆng d− thu gän modulo 7. §èi víi modulo 8, ta cã thÓ lÊy 1,3,5,7. §Þnh lÝ 3.5. NÕu r1,r2,...,r φ ( n ) lµ mét hÖ thÆng d− thu gän modulo n, vµ a lµ sè nguyªn d−¬ng, (a,n)=1, th× tËp hîp ar1,ar2,...,ar φ ( n ) còng lµ hÖ thÆng d− thu gän modulo n. om Chóng t«i dµnh chøng minh ®Þnh lÝ nµy cho ®éc gi¶. m §Þnh lÝ trªn ®©y ®−îc dïng ®Ó chøng minh më réng cña ®Þnh lÝ Fermat bÐ. §Þnh lÝ Euler. NÕu m lµ sè nguyªn d−¬ng vµ a lµ sè nguyªn tè cïng nhau víi n th× o a φ ( m) ≡ 1(mod m). .C Chøng minh. Ta lËp luËn hoµn toµn t−¬ng tù nh− trong ®Þnh lÝ Fermat bÐ. Gi¶ sö .C r1,r2,...,r φ ( m) modulo m, lËp nªn tõ c¸c sè nguyªn d−¬ng kh«ng v−ît qu¸ m vµ nguyªn tè cïng nhau víi m. Theo ®Þnh lÝ 3.5, ar1,ar2,...,a r φ ( m) còng lµ mét hÖ thÆng d− thu h gän. Khi ®ã thÆng d− d−¬ng bÐ nhÊt cña hÖ nµy sÏ lµ tËp hîp r1,r2,..., r φ ( m) s¾p xÕp th theo mét thø tù nµo ®ã. Ta cã: at ar1ar2...a r φ ( m) ≡ r1r2... r φ ( m) (mod m). a Nh− vËy, nM M φ ( m) a r1,r2,...,r φ ( m) ≡ r1r2... r φ ( m) (mod m). Tõ ®ã suy ra ®Þnh lÝ. n §Þnh lÝ Euler cã thÓ dïng ®Ó t×m nghÞch ®¶o modulo m. Ch¼ng h¹n nÕu a vµ m lµ c¸c sè nguyªn tè cïng nhau, ta cã a.a φ ( m) −1 ≡ 1(mod m), tøc lµ a φ ( m) −1 chÝnh lµ nghÞch V V ®¶o cña a modulo m. Tõ ®ã còng suy ra nghiÖm cña ph−¬ng tr×nh ®ång d− tuyÕn tÝnh ax ≡ b(mod m), víi (a,m)=1 lµ x ≡ a φ ( m) −1 b(mod m). §Þnh lÝ 3.6. Phi hµm Euler lµ hµm nh©n tÝnh. Chøng minh. Gi¶ sö m, n lµ hai sè d−¬ng nguyªn tè cïng nhau. Ta cÇn chøng tá r»ng φ (mn)= φ (m) φ (n). Ta s¾p xÕp tÊt c¶ c¸c sè nguyªn d−¬ng kh«ng v−ît qu¸ nm thµnh b¶ng sau: 1 m+1 2m+1 ... (n-1)m+1 2 m+2 2m+2 ... (n-1)m+2 ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 40
r m+r 2m+r ... (n-1)m+r ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... m 2m 3m ... mn Gi¶ sö r lµ sè nguyªn kh«ng v−ît qu¸ m, vµ (m,n)=d>1. Khi ®ã trong hµng thø r kh«ng cã sè nµo nguyªn tè cïng nhau víi mn. V× thÕ ®Ó tÝnh φ (mn), ta chØ cÇn quan t©m c¸c sè trong hµng thø r víi (r,m)=1. C¸c sè trong hµng nµy ®Òu nguyªn tè cïng nhau víi m. MÆt kh¸c dÔ thÊy r»ng c¸c sè trong hµng nµy lËp thµnh mét hÖ thÆng d− ®Çy ®ñ modulo n. Do ®ã cã ®óng φ (n) sè trong hµng nguyªn tè cïng nhau víi n, tøc lµ trong hµng cã φ (n) sè nguyªn tè cïng nhau víi mn. C¶ th¶y cã φ (n) hµng nh− vËy, ®Þnh lÝ ®−îc chøng minh. Nhê tÝnh chÊt nµy ta cã ngay c«ng thøc Phi-hµm Euler. om m §Þnh lÝ 3.7. Gi¶ sö n=p1a1p2a2...pkak lµ ph©n tÝch cña n thµnh thõa sè nguyªn tè. Khi ®ã ta cã: o 1 1 1 φ (n)=n(1- )(1 − )...(1 − ) p1 p2 pk .C .C Chøng minh. Do Phi-hµm Euler lµ hµm nh©n tÝnh nªn ta chØ cÇn chøng minh r»ng, víi mäi sè nguyªn tè p, φ (pk)=pk-pk-1. h ThËt vËy, c¸c sè nguyªn d−¬ng kh«ng v−ît qu¸ pk vµ kh«ng nguyªn tè cïng nhau víi th p ph¶i cã d¹ng sp víi s nguyªn d−¬ng nµo ®ã. Cã ®óng pk-1 sè nh− vËy. Do ®ã, sè c¸c sè kh«ng v−ît qu¸ pk vµ nguyªn tè cïng nhau víi pk ®óng b»ng pk-pk-1. TÝnh chÊt at quan träng sau ®©y cña Phi-hµm th−êng d−îc sö dông vÒ sau. a §Þnh lÝ 3.8. Gi¶ sö n lµ mét sè nguyªn d−¬ng. Khi ®ã nM M ∑ φ (d ) =n d |n trong ®ã tæng ®−îc lÊy theo mäi −íc cña n. n Chøng minh. Ta ph©n c¸c sè nguyªn tõ 1 ®Õn n thµnh tõng nhãm Cd: m ∈Cd khi vµ chØ khi (m,n)=d, tøc lµ khi vµ chØ khi (m/d, n/d)=1. Nh− vËy, sè phÇn tö cña Cd ®óng V V b»ng sè c¸c sè nguyªn kh«ng v−ît qu¸ n/d vµ nguyªn tè cïng nhau víi n/d, tøc lµ b»ng φ (n/d). Ta cã n= ∑ φ (n / d ) d |n Khi d ch¹y qua mäi −íc cña n th× n/d còng ch¹y qua mäi −íc cña n: ®Þnh lÝ ®−îc chøng minh. NhËn xÐt. C¸c tÝnh chÊt cña Phi-hµm Euler ®−îc sö dông ®Ó tÝnh ®ång d− cña nh÷ng luü thõa rÊt lín. Ch¼ng h¹n, ta cÇn tÝnh an mod k, trong ®ã n lµ mét sè nguyªn lín. Gi¶ sö ta cã 41
α α α k= p1 1 p2 2 ... p s s . Khi ®ã a φ ( pi i ≡ 1(mod pi α i ). NÕu N lµ béi chung nhá nhÊt cña c¸c φ ( pi α i ) th× α ) aN ≡ 1(mod k). Do ®ã, viÕt n=Nq+r víi r
F(mn)= ∑ f (d 1 ) f (d 2 ) = ∑ f (d 1 ) ∑ f (d 2 ) =F(n)F(m) d1 |m d 2 |n §Þnh lÝ ®−îc chøng minh. Sö dông ®Þnh lÝ trªn, ta cã c«ng thøc sau ®©y cho c¸c hµm τ (n) vµ σ (n). §Þnh lÝ 3.12. Gi¶ sö n cã ph©n tÝch sau ®©y ra thõa sè nguyªn tè n=p1a1p2a2...pkak. Khi ®ã ta cã: k p aj+1 − 1 σ (n) = ∏ j j=1 pj −1 k τ (n)=(a1+1)(a2+1)...(ak+1)= ∏ (a j + 1) om m j =1 Chóng t«i dµnh chøng minh nµy cho ®éc gi¶. o Do c¸c quan niÖm thÇn bÝ, ng−êi cæ Hy L¹p quan t©m ®Õn c¸c sè nguyªn b»ng tæng tÊt c¶ c¸c −íc d−¬ng thùc sù cña nã. Hä gäi c¸c sè ®ã lµ c¸c sè hoµn h¶o. VÝ dô. .C §Þnh nghÜa 3.13. Sè nguyªn d−¬ng n d−îc gäi lµ sè hoµn h¶o nÕu σ (n)=2n. .C C¸c sè σ (12)=1+2+4+7+14+28=56 6, 28 lµ c¸c sè hoµn h¶o: σ (6)=1+2+3+6=12, h §Þnh lÝ sau ®©y ®−îc biÕt tõ thêi Hy l¹p. th §Þnh lÝ 3.14. Sè nguyªn d−¬ng ch½n n lµ sè hoµn h¶o khi vµ chØ khi n=2m-1(2m-1), at trong ®ã m lµ mét sè nguyªn sao cho m ≥ 2 vµ 2m-1 lµ nguyªn tè. a Chøng minh. Tr−íc tiªn, gi¶ sö r»ng, m cã d¹ng nh− trªn. V× σ lµ hµm nh©n tÝnh, ta cã: σ (n)= σ (2m-1) σ (2m-1). Tõ c«ng thøc cña hµm σ vµ gi¶ thiÕt 2m-1 lµ nguyªn nM M tè, dÔ thÊy r»ng σ (2m-1)=2m-1, σ (2m-1)=2m, vµ do ®ã σ (n)=2n. Ng−îc l¹i, gi¶ sö n lµ sè hoµn h¶o ch½n. ViÕt n=2st, trong ®ã s,t lµ c¸c sè nguyªn d−¬ng, t lÎ, ta ®−îc: n σ (n)= σ (2st)= σ (2s) σ (t)=(2s+1-1) σ (t) V V× n lµ sè hoµn h¶o, σ (n)=2n=2s+1t. V Nh− vËy, 2s+1| σ (t), gi¶ sö σ (t)=2s+1q. Ta cã ®¼ng thøc (2s+1-1)2s+1q=2s+1t, tøc lµ q|t vµ q ≠ t. MÆt kh¸c ta cã: t+q=(2s+1-1)q+q=2s+1q= σ (t) Ta chøng tá r»ng, q=1. ThËt vËy, nÕu ng−îc l¹i, t cã Ýt nhÊt 3 −íc kh¸c nhau lµ 1, t, q, do ®ã σ (t) ≥ t+q+1, m©u thuÉn ®¼ng thøc võa chøng minh. VËy σ (t)=t+1, nghÜa lµ t lµ sè nguyªn tè. §Þnh lÝ ®−îc chøng minh. Nh− vËy ®Ó t×m c¸c sè hoµn h¶o, ta cÇn t×m c¸c sè nguyªn tè d¹ng 2m-1. 43
§Þnh nghÜa 3.15. Gi¶ sö m lµ mét sè nguyªn d−¬ng, khi ®ã Mm=2m-1 ®−îc gäi lµ sè Mersenne thø m. NÕu p lµ sè nguyªn tè, vµ Mp còng nguyªn tè, th× Mp ®−îc gäi lµ sè nguyªn tè Mersenne. VÝ dô. M2,M3,M5,M7 lµ c¸c sè nguyªn tè Mersenne, trong khi M11 lµ hîp sè. Cã nhiÒu ®Þnh lÝ kh¸c nhau dïng ®Ó x¸c ®Þnh sè nguyªn tè Mersenne. Ch¼ng h¹n nhê ®Þnh lÝ sau ®©y, ta cã thÓ kiÓm tra nhanh chãng dùa vµo d¹ng cña c¸c −íc sè cña sè nguyªn tè Mersenne. §Þnh lÝ 3.16. NÕu p lµ mét sè nguyªn tè lÎ, th× mäi −íc cña sè nguyªn tè Mersenne Mp ®Òu cã d¹ng 2kp+1, trong ®ã k lµ sè nguyªn d−¬ng. Chøng minh. Gi¶ sö q lµ mét sè nguyªn tè cña Mp. Theo ®Þnh lÝ Fermat bÐ, q|(2q- 1 -1). Theo hÖ qu¶ 1.9, (2p-1,2q-1-1)=2(p,q-1)-1. ¦íc chung nµy lín h¬n 1, v× nã lµ mét béi cña q. Do ®ã, (p,q-1)=p, v× p lµ mét sè nguyªn tè. Ta cã q=mp+1, vµ v× q lÎ nªn om m m=2k, ®Þnh lÝ ®−îc chøng minh. Sau ®©y lµ vµi vÝ dô cho thÊy øng dông cña ®Þnh lÝ trªn. o VÝ dô 1. §Ó xÐt xem M13=213-1=8191 cã ph¶i lµ sè nguyªn tè hay kh«ng, ta cÇn xem c¸c phÐp chia cho nh÷ng sè nguyªn tè kh«ng v−ît qu¸ 8191 =90,504... MÆt kh¸c, .C .C theo ®Þnh lÝ trªn, mäi −íc nguyªn tè ®Òu ph¶i cã d¹ng 26k+1. Nh− vËy chØ cÇn thö víi hai sè 53 vµ 79: ta thÊy M13 lµ sè nguyªn tè. VÝ dô 2. XÐt M23=8388607. Ta cÇn xÐt c¸c phÐp chia cña nã cho c¸c sè nguyªn tè h d¹ng 46k+1. Sè ®Çu tiªn 47 lµ −íc cña nã: M23 lµ hîp sè. th Cã nhiÒu thuËt to¸n ®Æc biÖt ®Ó kiÓm tra nguyªn tè c¸c sè Mersenne. Nhê ®ã, ng−êi at ta ph¸t hiÖn ®−îc nh÷ng sè nguyªn tè rÊt lín. Mçi lÇn cã mét sè nguyªn tè a Mersenne, ta l¹i ®−îc mét sè hoµn h¶o. Cho ®Õn nay, ng−êi ta ®· biÕt ®−îc r»ng, víi p ≤ 132049, chØ cã 30 sè nguyªn tè Mersenne, vµ tÝnh ®−îc chóng. Sè nguyªn tè nM Mersenne t×m ®−îc gÇn ®©y nhÊt lµ sè M216091, gåm 65050 ch÷ sè. M Gi¶ thuyÕt sau ®©y vÉn cßn ch−a ®−îc chøng minh. Gi¶ thuyÕt 3.17. Tån t¹i v« h¹n sè nguyªn tè Mersenne. n Ng−êi ta ®· biÕt ®−îc r»ng, trong kho¶ng tõ 1 ®Õn 10200 kh«ng cã sè hoµn h¶o lÎ. Tuy nhiªn c©u hái sau ®©y vÉn ch−a ®−îc tr¶ lêi. V V C©u hái 3.18. Tån t¹i hay kh«ng c¸c sè hoµn h¶o lÎ? §4. C¨n nguyªn thuû. Khi xÐt c¸c sè phøc lµ c¨n bËc n cña ®¬n vÞ, ta th−êng chó ý nh÷ng sè nµo kh«ng ph¶i lµ c¨n cña ®¬n vÞ víi bËc thÊp h¬n. Nh÷ng sè ®ã gäi lµ c¨n nguyªn thuû cña ®¬n vÞ. §èi víi c¸c sè nguyªn, ta còng cã kh¸i niÖm hoµn toµn t−¬ng tù vÒ “c¨n” vµ “c¨n nguyªn thuû” cña ®¬n vÞ. 44
§Þnh nghÜa 3.19. Gi¶ sö a vµ m lµ c¸c sè nguyªn d−¬ng nguyªn tè cïng nhau. Khi ®ã sè nguyªn nhá nhÊt x tho¶ m·n ®ång d− ax ≡ 1(mod m) ®−îc gäi lµ bËc cña a modulo m. Ta viÕt x= ordma . Ta chó ý r»ng, sè x nh− vËy tån t¹i v× theo ®Þnh lÝ Euler, a φ (m) ≡ 1(mod m). §Þnh lÝ 3.20. Gi¶ sö a vµ n lµ c¸c sè nguyªn tè cïng nhau, n>0. Khi ®ã sè nguyªn x lµ nghiÖm cña ®ång d− ax ≡ 1(mod m) khi vµ chØ khi x lµ mét béi cña bËc cña a modulo n. Chøng minh. Gi¶ sö x tho¶ m·n ®ång d− trªn. Ta viÕt x=q ordna+r, trong ®ã 0 ≤ r0, th× ordna | φ (n). om m HÖ qu¶ 3.22. NÕu a vµ n lµ c¸c sè nguyªn tè cïng nhau, n>0, th× ai ≡ aj(mod n) khi vµ chØ khi i ≡ j(mod n). o Chøng minh c¸c hÖ qu¶ trªn ®−îc dµnh cho ®éc gi¶. Do hÖ qu¶ 3.21, nÕu r vµ n lµ nguyªn tè cïng nhau th× bËc cña r kh«ng v−ît qu¸ .C .C φ (n). C¸c sè cã bËc ®óng b»ng φ (n) gi÷ vai trß quan träng trong nhiÒu vÊn ®Ò kh¸c nhau cña sè häc. Ta cã ®Þnh nghÜa sau. §Þnh nghÜa 3.23. NÕu r vµ n lµ c¸c sè nguyªn tè cïng nhau, n>0, vµ nÕu h ordnr = φ (n) th× r ®−îc gäi lµ c¨n nguyªn thuû modulo n. th at Chó ý r»ng kh«ng ph¶i mäi sè ®Òu cã c¨n nguyªn thuû. Ch¼ng h¹n, xÐt n=8. C¸c sè nhá h¬n 8 vµ nguyªn tè cïng nhau víi 8 lµ 1, 3, 5, 7, ®ång thêi ta cã ord81=1, bËc a cña c¸c sè cßn l¹i b»ng 2, trong khi φ (8)=4. VÊn ®Ò nh÷ng sè nguyªn nµo th× cã c¨n nM nguyªn thuû sÏ ®−îc xÐt vÒ sau. M §Þnh lÝ 3.24. NÕu r, n nguyªn tè cïng nhau, n>0, vµ nÕu r lµ c¨n nguyªn thuû modulo n, th× c¸c sè sau ®©y lËp thµnh hÖ thÆng d− thu gän modulo n: r1,r2,...,r φ (n). n Chøng minh. V× (r,n)=1, c¸c sè trªn nguyªn tè cïng nhau víi n. Ta chØ cÇn chøng tá V V r»ng, kh«ng cã hai sè nµo ®ång d− víi nhau modulo n. Gi¶ sö ri ≡ rj(mod n). Theo hÖ qu¶ 3.22, i ≡ j(mod φ (n)). Tõ ®ã suy ra i=j, v× i, j kh«ng v−ît qu¸ φ (n). §Þnh lÝ ®−îc chøng minh. §Þnh lÝ 3.25. NÕu ordma=t vµ u lµ sè nguyªn d−¬ng, th× ordm(au)= t / (t,u). Chøng minh. §Æt v=(t,u), t=t1v, u=u1v, s= ordm(au). Ta cã (au)t 1 =(au1v)t/v=(at)u1 ≡ 1(mod m). Do ®ã, s|t1. MÆt kh¸c, (au)s=aus ≡ 1(mod m) nªn t|su. Nh− vËy, t1v | u1vs, do ®ã, t1|u1s. V× (u1, t1)=1, ta cã t1|s. Cuèi cïng, v× s|t1, t1|s nªn s=t1=t/v=t/(t, u), chøng minh xong. 45
HÖ qu¶ 3.26. Gi¶ sö r lµ c¨n nguyªn thñy modulo m, trong ®ã m lµ sè nguyªn lín h¬n 1. Khi ®ã ru lµ c¨n nguyªn thñy modulo m nÕu vµ chØ nÕu (u, φ (m))=1. ThËt vËy, ordmru=ord mr/(u, ordmr)= φ (m)/(u, φ (m)): hÖ qu¶ ®−îc chøng minh. §Þnh lÝ 3.27. NÕu sè nguyªn d−¬ng m cã c¨n nguyªn thuû, th× nã cã tÊt c¶ φ ( φ (m)) c¨n nguyªn thuû kh«ng ®ång d− nhau. ThËt vËy, nÕu r lµ mét c¨n nguyªn thuû th× r, r2, ..., r φ (m) lµ mét hÖ ®Çy ®ñ c¸c thÆng d− thu gän modulo m. Sè c¨n nguyªn thuû modulo m ®óng b»ng sè c¸c sè u tho¶ m·n (u, φ (m))=1, vµ cã ®óng φ ( φ (m)) sè u nh− thÕ. §Þnh lÝ ®−îc chøng minh. om m §5. Sù tån t¹i cña c¨n nguyªn thuû. o Trong tiÕt nµy, ta sÏ x¸c ®Þnh nh÷ng sè nguyªn cã c¨n nguyªn thuû. Tr−íc tiªn ta sÏ chøng minh r»ng mäi sè nguyªn tè ®Òu cã c¨n nguyªn thuû. §Ó lµm viÖc ®ã, ta cÇn .C .C mét vµi kiÕn thøc vÒ ®ång d− ®a thøc. Gi¶ sö f(x) lµ ®a thøc víi hÖ sè nguyªn. Sè c ®−îc gäi lµ nghiÖm cña ®a thøc f(x) modulo m nÕu f(c) ≡ 0(mod m). DÔ thÊy r»ng, nÕu c lµ mét nghiÖm th× mäi sè ®ång h d− víi c modulo m còng lµ nghiÖm. th §èi víi sè nghiÖm cña mét ®a thøc modulo mét sè nguyªn, ta còng cã tÝnh chÊt at t−¬ng tù nh− sè nghiÖm cña mét ®a thøc. a §Þnh lÝ Lagrange. Gi¶ sö f(x)=anxn+...+a1x+a0 lµ ®a thøc víi hÖ sè nguyªn, n>o, ®ång thêi an ≡ 0(mod p). Khi ®ã f(x) cã nhiÒu nhÊt n nghiÖm modulo p kh«ng ®ång / nM M d− tõng cÆp. Chøng minh. Ta chøng minh b»ng qui n¹p. Khi n=1, ®Þnh lÝ lµ râ rµng. Gi¶ sö ®Þnh lÝ ®· chøng minh víi ®a thøc bËc n-1 cã hÖ sè cña luü thõa cao nhÊt kh«ng chia hÕt cho n p, vµ gi¶ sö r»ng ®a thøc f(x) cã n+1 nghiÖm modulo p kh«ng ®ång d− tõng cÆp c0,c1,...,cn. Ta cã f(x)-f(c0)=(x-x0)g(x), trong ®ã g(x) lµ ®a thøc bËc n-1 víi hÖ sè cao V nhÊt lµ an. V× víi mäi k, 0 ≤ k ≤ n, ck-c0 ≡ 0 (mod p), trong khi ®ã f(ck)-f(c0)= / V (ck-c0)g(ck) ≡ 0(mod p), nªn ck lµ nghiÖm cña g(x) modulo p: tr¸i víi gi¶ thiÕt quy n¹p. §Þnh lÝ ®−îc chøng minh. §Þnh lÝ 3.28. Gi¶ sö p lµ sè nguyªn tè vµ d lµ mét −íc cña p-1. Khi ®ã ®a thøc xd-1 cã ®óng d nghiÖm modulo p kh«ng ®ång d− tõng cÆp. Chøng minh. ThËt vËy, gi¶ sö p-1=de. Ta cã xp-1-1=(xd-1)g(x). Theo ®Þnh lÝ Fermat bÐ, xp-1-1 cã p-1 nghiÖm modulo p kh«ng ®ång d− tõng cÆp. MÆt kh¸c, mçi mét nghiÖm ®ã ph¶i lµ nghiÖm cña xd-1 hoÆc lµ cña g(x). Theo ®Þnh lÝ Lagrange, g(x) cã nhiÒu nhÊt p-d-1 nghiÖm kh«ng ®ång d− tõng cÆp, v× thÕ xd-1 ph¶i cã Ýt nhÊt (p-1)-(p-d-1)=d nghiÖm. L¹i theo ®Þnh lÝ Lagrange, xd-1 cã kh«ng qu¸ d nghiÖm, vËy nã cã ®óng d nghiÖm modulo p kh«ng ®ång d− tõng cÆp. §Þnh lÝ d−îc chøng minh. 46
§Þnh lÝ trªn ®©y sÏ ®−îc sö dông trong ch−¬ng 5 khi x©y dùng c¸c tr−êng h÷u h¹n. §Þnh lÝ 3.29. Gi¶ sö p lµ sè nguyªn tè, d lµ −íc d−¬ng cña p-1. Khi ®ã, sè c¸c sè nguyªn kh«ng ®ång d− bËc d modulo p lµ φ (d). Chøng minh. Gi¶ sö F(d) lµ sè c¸c sè nguyªn d−¬ng bËc d modulo p vµ bÐ h¬n p. Ta cÇn chøng tá r»ng F(d)= φ (d). V× φ (d)=p-1 nªn d|p-1, tõ ®ã ta cã p-1= ∑ F (d ) d | p −1 MÆt kh¸c ta cã: p-1= ∑ φ (d ) d | p −1 om m theo c«ng thøc cña Phi-hµm. Nh− vËy ®Þnh lÝ sÏ ®−îc chøng minh nÕu ta chøng tá ®−îc r»ng F(d) ≤ φ (d) nÕu d|p-1. o Khi F(d)=0, ®iÒu nãi trªn lµ tÇm th−êng. Gi¶ sö F(d) ≠ 0, tøc lµ tån t¹i sè nguyªn a bËc d modulo p. Khi ®ã, c¸c sè nguyªn a, a2,...,ad kh«ng ®ång d− modulo p. Râ rµng r»ng, mçi luü thõa cña a lµ mét nghiÖm cña xd-1 ≡ 0(mod p), mµ sè nghiÖm kh«ng ®ång .C .C d− ®óng b»ng d, nªn mçi nghiÖm modulo p ®ång d− víi mét trong c¸c luü thõa cña a. Do ®ã, v× phÇn tö tuú ý bËc d lµ mét nghiÖm cña ph−¬ng tr×nh xd-1 ≡ 0(mod p) nªn ph¶i ®ång d− víi mét trong c¸c luü thõa cña a. MÆt kh¸c, theo ®Þnh lÝ 3.24, luü thõa k cña a cã bËc d khi vµ chØ khi (k,d)=1. Cã ®óng φ (d) sè k nh− vËy, vµ do ®ã suy ra thh F(d) ) ≤ φ (d), ®Þnh lÝ ®−îc chøng minh. at HÖ qu¶ 3.30. Mäi sè nguyªn tè ®Òu cã c¨n nguyªn thuû. a ThËt vËy, gi¶ sö p lµ sè nguyªn tè. Khi ®ã cã φ (p-1) sè nguyªn bËc p-1 modulo p nM M (§Þnh lÝ 3.28) kh«ng ®ång d− tõng cÆp. Theo ®Þnh nghÜa, mçi sè ®ã lµ mét c¨n nguyªn thuû: p cã φ (p-1) c¨n nguyªn thuû. PhÇn cßn l¹i cña ch−¬ng ®−îc giµnh ®Ó t×m tÊt c¶ c¸c sè nguyªn d−¬ng cã c¨n n nguyªn thuû. §Þnh lÝ 3.31. NÕu p lµ mét sè nguyªn tè lÎ víi c¨n nguyªn thuû r, th× hoÆc r, hoÆc V V r+p lµ c¨n nguyªn thuû modulo p2. Chøng minh. V× r lµ c¨n nguyªn thuû modulo p nªn ta cã ordpr= φ (d)=p-1. Gi¶ sö n= ord p 2 r. Ta cã rn ≡ 1(mod p2), vµ do ®ã rn ≡ 1(mod p). Nh− vËy, bËc p-1 cña r lµ mét −íc cña n. MÆt kh¸c, n lµ bËc cña r modulo p2 nªn n lµ −íc cña φ (p2)=p(p-1). V× n|p(p-1) vµ p-1|n nªn dÔ dµng suy ra r»ng, hoÆc n=p-1, hoÆc n=p(p-1). NÕu n=p(p-1) th× r lµ c¨n nguyªn thuû modulo p2, v× ord p2 r= φ (p2). Trong tr−êng hîp cßn l¹i, n=p-1, ta cã rp-1 ≡ 1(mod p2). §Æt s=r+p. CÇn ph¶i chøng minh r»ng s lµ c¨n nguyªn thuû modulo p2. V× s ≡ r(mod p), s còng lµ c¨n nguyªn thuû 47
modulo p. Nh− vËy, theo chøng minh trªn ord p2 s hoÆc b»ng p-1, hoÆc b»ng p(p-1). Ta sÏ chøng tá r»ng, bËc ®ã kh«ng thÓ lµ p-1. Ta cã sp-1=(r+p)p-1 ≡ rp-1+(p-1)prp-2(mod p2) ≡ 1+(p-1)prp-2 ≡ 1-prp-2(mod p2) Tõ ®ã ta cã thÓ thÊy r»ng, sp-1 ≡ 1(mod p2). ThËt vËy, nÕu ng−îc l¹i th× / prp- 2 ≡ 0(mod p ), nªn r ≡ 0(mod p). §iÒu nµy kh«ng thÓ cã, v× p / r do r lµ c¨n nguyªn 2 p-2 | thuû modulo p. Nh− vËy ord p2 s=p(p-1)= φ (p ), tøc s=r+p lµ c¨n nguyªn thuû 2 modulo p2. B©y giê ta xÐt luü thõa tuú ý cña sè nguyªn tè §Þnh lý 3.32. Gi¶ sö p lµ mét sè nguyªn tè lÎ, khi ®ã pk cã c¨n nguyªn thuû víi mäi sè nguyªn d−¬ng k. H¬n n÷a, nÕu n lµ c¨n nguyªn thuû modulo p2 th× r lµ c¨n nguyªn om thuû modulo pk víi mäi sè ngyªn d−¬ng k. m Chøng minh. Tõ §Þnh lÝ 3.31, p cã c¨n nguyªn thuû r sao cho ®ã còng lµ c¨n nguyªn thuû modulo p2, vµ do ®ã o rp-1 ≡ 1 (mod p2). / .C .C Ta sÏ chøng minh r còng lµ c¨n nguyªn thuû modulo pk víi mäi sè nguyªn d−¬ng k. B»ng quy n¹p cã thÓ thÊy r»ng k −1 ( p −1) rp ≡ 1 (mod pk) / h (*) th víi mäi sè nguyªn d−¬ng k. Gi¶ sö at n= ord p k r a Ta cã n | ϕ (pk)=pk-1(p-1). MÆt kh¸c nM M rn ≡ 1 (mod pk), / vµ rn ≡ 1 (mod p). / n Do ®ã p-1= ϕ (p) |n (§Þnh lÝ 3.30). V× (p-1) |n vµ n|pk-1(p-1) nªn n=pt(p-1), trong ®ã t lµ sè nguyªn d−¬ng 0 ≤ t ≤ k-1. NÕu n=pt(p-1) víi t ≤ k-2 th× V V k −2 t k −2 −t ( p −1) rp = (r p ( p −1) ) p ≡ 1 (mod p k ) , m©u thuÉn. VËy ord p k r =pk-1(p-1)= ϕ (pk), r còng lµ còng nguyªn thuûcña pk. Chøng minh (*): k=2: ®óng. Gi¶ sö (*) ®óng víi sè nguyªn d−¬ng k ≥ 2. Khi ®ã k −2 ( p −1) rp ≡ 1 (mod p k ) . / V× (r,p)=1, ta thÊy (r,pk-1)=1. Do ®ã, tõ §Þnh lÝ Euler ta cã k −2 k −1 rp ( p −1) ≡ rϕ( p ) VËy tån t¹i sè nguyªn d sao cho 48