Bài Giảng Các Hàm Số Học - Tài Liệu Text - 123doc

Có thể bạn quan tâm

Tải bản đầy đủ (.pdf) (20 trang)

Trang chủ

Trung học cơ sở - phổ thông

Lớp 12

Bài Giảng Các Hàm Số Học

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (252.93 KB, 20 trang )

Chơng 3Các hàm số họcKhi 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 ớccủ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. Trongchơ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 đợcgià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.Đị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.Đị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(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.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ơngcó khai triển thành thừa số nguyên tố dạng n=p1a1p2a2...pkak, thì f(n) đợc tính theocông thứcf(n)=f(pa1)f(pa2)...f(pak).Đ2. Phi hàm Euler.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ố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àovấ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 chomỗ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ọnmodulo n.Chúng tôi dành chứng minh định lí này cho độc giả.Đị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ìa ( m) 1(mod m).Chứng minh. Ta lập luận hoàn toàn tơng tự nh trong định lí Fermat bé. Giả sử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êntố 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 thugọ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ếptheo một thứ tự nào đó. Ta có:ar1ar2...a r ( m) r1r2... r ( m) (mod m).Nh vậy,a ( m)r1,r2,...,r ( m) r1r2... r ( m) (mod m).Từ đó suy ra định lí.Đị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ácsố 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đảo của a modulo m. Từ đó cũng suy ra nghiệm của phơng trình đồng d tuyếntí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á nmthành bảng sau:1m+12m+1...(n-1)m+12m+22m+2...(n-1)m+2... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...40rm+r2m+r...(n-1)m+r... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...m2m3m...mnGiả sử r là số nguyên không vợt quá m, và (m,n)=d>1. Khi đó trong hàng thứ rkhông có số nào nguyên tố cùng nhau với mn. Vì thế để tính (mn), ta chỉ cần quantâ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ùngnhau 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ứclà trong hàng có (n) số nguyên tố cùng nhau với mn. Cả thảy có (n) hàng nhvậ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.Đị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ó: (n)=n(1-111)(1 )...(1 )p1p2pkChứ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.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ớip 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ácsố 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ấtquan trọng sau đây của Phi-hàm thờng dợc sử dụng về sau.Định lí 3.8. Giả sử n là một số nguyên dơng. Khi đó (d ) =nd |ntrong đó tổng đợc lấy theo mọi ớc của 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 đúngbằ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 |nKhi 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í đợcchứ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ữngluỹ 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ó41k= 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 r0. Khi đó số nguyên xlà 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 amodulo 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).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) khivà chỉ khi i j(mod n).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á (n). Các số có bậc đúng bằng (n) giữ vai trò quan trọng trong nhiều vấn đề khácnhau 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ếuordnr = (n) thì r đợc gọi là căn nguyên thuỷ modulo n.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ậccủ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ănnguyên thuỷ sẽ đợc xét về sau.Đị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).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ỏ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í đợcchứ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 minhxong.45Hệ quả 3.26. Giả sử r là căn nguyên thủy modulo m, trong đó m là số nguyên lớnhơ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ácthặng d thu gọn modulo m. Số căn nguyên thuỷ modulo m đúng bằng số các số uthoả mãn (u, (m))=1, và có đúng ( (m)) số u nh thế. Định lí đợc chứngminh.Đ5. Sự tồn tại của căn nguyên thuỷ.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ầnmộ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ố đồngd với c modulo m cũng là nghiệm.Đố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ấttơng tự nh số nghiệm của một đa thức.Đị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 đồngd 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 chop, và giả sử rằng đa thức f(x) có n+1 nghiệm modulo p không đồng d từng cặpc0,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ố caonhất là an. Vì với mọi k, 0 k n, ck-c0 / 0 (mod p), trong khi đó f(ck)-f(c0)=(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 quynạ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-1có đú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í Fermatbé, 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ộtnghiệ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ậynó 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. Tacầ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 1Mặt khác ta có:p-1= (d )d | p 1theo 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.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 abậc d modulo p. Khi đó, các số nguyên a, a2,...,ad không đồng d modulo p. Rõ ràngrằ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 đồngd đú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ủaa. 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ênphả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ừak 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 raF(d) ) (d), định lí đợc chứng minh.Hệ quả 3.30. Mọi số nguyên tố đều có căn nguyên thuỷ.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(Định lí 3.28) không đồng d từng cặp. Theo định nghĩa, mỗi số đó là một cănnguyê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ănnguyê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ặcr+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ủar 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ặcn=p(p-1). Nếu n=p(p-1) thì r là căn nguyên thuỷ modulo p2, vì ord p2 r= (p2). Trongtrờ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 minhrằng s là căn nguyên thuỷ modulo p2. Vì s r(mod p), s cũng là căn nguyên thuỷ47modulo 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ìprp2p-22 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ênthuỷ modulo p. Nh vậy ord p2 s=p(p-1)= (p2), tức s=r+p là căn nguyên thuỷ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ọisố 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ênthuỷ modulo pk với mọi số ngyên dơng k.Chứng minh. Từ Định lí 3.31, p có căn nguyên thuỷ r sao cho đó cũng là căn nguyênthuỷ modulo p2, và do đórp-1 / 1 (mod p2).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ằngrpk 1( p 1)/ 1 (mod pk)(*)với mọi số nguyên dơng k. Giả sửn= ord p k rTa có n | (pk)=pk-1(p-1). Mặt khácrn / 1 (mod pk),và rn / 1 (mod p).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ìrpk 2( p 1)t= (r p ( p 1) ) pk 2 t 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 đórpk 2( p 1)/ 1 (mod p k ) .Vì (r,p)=1, ta thấy (r,pk-1)=1. Do đó, từ Định lí Euler ta córpk 2( p 1) r( pVậy tồn tại số nguyên d sao cho48k 1)rptrong đó p /| d, vì theo giả thiết r pk 2k 2( p 1)( p 1)=1+dpk-1,/ 1 (mod p k ) .Ta lấy luỹ thừa bậc p của hai vế phơng trình trên và nhận đợcrpk 1( p 1) p= (1 + dp k 1 ) p = 1 + p(dp k 1 ) + p 2 (dp k 1 ) 2 +...+ (dp k 1 ) p 2 1 + dp k (mod p k +1 ).Vì p /| d nên ta córpk 1( p 1)/ 1 (mod p k +1 ) ,chứng minh xong.Ví dụ: r=3 là căn nguyên thuỷ modulo 7k với mọi số nguyên dơng k.Định lí 3.33: Nếu số nguyên dơng n không phải là luỹ thừa của một số nguyên tốhoặc hai lần luỹ thừa một số nguyên tố, thì n không có căn nguyên thuỷ.Chứng minh. Giả sử n là số nguyên dơng với phân tích ra thừa số nguyên tố nh sautttn = p1 1 p2 2 ... pm m .Giả sử n có căn nguyên thuỷ r, tức là (n,r)=1 và ordnr= (n). Vì (r,n)=1 nên(r,pt)=1 trong đó pt là một trong các luỹ thừa nguyên tố có mặt trong phân tích trên.Theo Định lý Euler,tr ( p ) 1 (mod p t ).Giả sử U là bội chung nhỏ nhất của ( p1 1 ), ( p2 2 ),..., ( pm m ),tttU=[ ( p1 1 ), ( p2 2 ),..., ( pm m ) ].tttVì ( pi i ) | U nênttrU 1(mod pi i )Với I=1, 2, ..., m. Do đóordnr= (n) U.Mặt khác, (n)= ( p1t p2 t ... pmt ) = ( p1t ) ( p2 t )... ( pmt ) .12m12mTừ đó ta có ( p1t ) ( p2 t )... ( pmt ) [ ( p1 t ), ( p2 t ),..., ( pm t ) ],12m1492mTức là ( p1 t1 ), ( p2 t2 ),..., ( pm tm ) phải nguyên tố cùng nhau từng đôi một. Do (pt)=pt-1(p-1) nên (pt) chẵn nếu p lẻ, hoặc nếu p=2 và t 2. Vậy, các số ( p1t ), ( p2 t ),..., ( pm t ) không nguyên tố cùng nhau từng cặp, trừ trờng hợp12mm=1 (và do đó n là luỹ thừa của số nguyên tố), hoặc m=2 và n=2pt, trong đó p là sốnguyên tố lẻ và t là số nguyên dơng.Định lí 3.34: Nếu p là số nguyên tố lẻ và t là số nguyên dơng, thì 2pt có cănnguyên thuỷ. Cụ thể là, nếu r là căn nguyên thuỷ modulo pt thì r, (tơng ứng, r+pt),là căn nguyên thuỷ modulo 2pt khi r lẻ, (tơng ứng, khi r chẵn).Chứng minh: Giả sử r là căn nguyên thuỷ modulo pt, khi đótr ( p ) 1 (mod p t ) ,và không có luỹ thừa nào nhỏ hơn (pt) thoả mãn đồng d.Do (2pt)= (2) (pt)= (pt) nêntr ( 2 p ) 1 (mod p t ).Khi r lẻ,tr ( 2 p ) 1 (mod 2) .tTừ đó ta có r ( 2 p ) 1 (mod 2 p t ) . Vì không có luỹ thừa bé hơn của r thoả mãn đồngd nên r chính là căn nguyên thuỷ của 2pt.Khi r chẵn, r+pt lẻ. Do đó,t(r + p t ) ( 2 p ) 1 (mod 2) .Vì r+pt r (mod pt) nênt(r + pt ) ( 2 p ) 1 (mod p t ) .Do đót(r + pt ) ( 2 p ) 1 (mod 2 p t ) ,và vì không có luỹ thừa bé hơn nào của (r+pt) thoả mãn đồng d, ta suy ra r+pt làcăn nguyên thuỷ modulo 2pt.Định lí 3.35: Nếu a là số nguyên lẻ, k 3 là số nguyên thìa (2k)/2= a2k 2 1 (mod 2k).Chứng minh. Ta chứng minh bằng quy nạp. Giả sử a là số nguyên lẻ, a=2b+1.Ta cóa2=4b(b+1)+1. Vì b hoặc b+1 chẵn nên 8 | 4b(b+1)+1, tức làa2 1 (mod 8).50Nh vậy, định lí đúng khi k=3. Giả sửa2k 2 1 (mod 2k)Khi đó tồn tại số nguyên d sao choa2k 2=1+d.2k.Từ đó ta có:k 1a 2 =1+d.2k+1+d2.22k,tức làa2k 1 1 (mod 2k+1).Từ định lí trên ta suy ra rằng, các luỹ thừa 2k với k 3 không có căn nguyên thuỷ.Nh vậy, trong các luỹ thừa của 2 chỉ có 2 và 4 là có căn nguyên thuỷ. Kết hợp điềunày với các Định lí 3.32, 3.33, 3.34, ta có định lí sau đâyĐịnh lí 3.36: Số nguyên dơng n có căn nguyên thuỷ khi và chỉ khin=2, 4, pt, 2pt,trong đó p là số nguyên tố lẻ, t là số nguyên dơng.51Bài tập và tính toán thực hành chơng 3I. Bài tập3.1. Hàm Mửbius đợc định nghĩa nh sau: à (n)=(-1)k, nếu n không chia hết cho sốchính phơng nào khác 1, và k là số các ớc nguyên tố của n; à (1)=1, à (n)=0 khi ncó ớc là số chính phơng khác 1.Chứng minh rằng, với mọi n>1, à (d ) =0.d |n3.2 (Biến đổi ngợc Mửbius ). Cho f(n) là một hàm số học. ĐặtF(n)= f (d ) .d |nChứng minh rằng:1)f(n)= à (d ) F(n/d).d |n2) Nếu f là hàm nhân tính thì F cũng là hàm nhân tính.3.3. Dùng biến đổi ngợc Mửbius và công thức n= (n/d), chứng minh rằngd |n1) (pk)=pk-pk-1 với p là số nguyên tố.2) (n) là hàm nhân tính.3.4. Cho là hàm nhân tính và à là hàm Mửbius. Chứng minh rằng, nếu các ớcnguyên tố của n là p1,p2,...pk thì à (d ) (d)=(1- (p ))(1- (p ))...(1- (p ))12kd |n(nếu n=1, ta xem vế phải là 1)3.5. Hàm k(n) (tổng luỹ thừa bậc k của các ớc số của n) đợc định nghĩa nh sau: k(n)= d k .d |n1) Cho công thức tính k(p) với p là số nguyên tố.2) Tính k(ps) khi s là số nguyên dơng.3) Chứng minh rằng k(n) là hàm nhân tính.524) Từ đó cho công thức tính k(n) khi n= p1 1 p2 2 ... ps s .3.6. Tìm tất cả các số tự nhiên n thoả mãn (n)+ (n)=2n.3.7. Chứng minh rằng n là một hợp số khi và chỉ khi (n)>n+ (n) .3.8. Chứng minh rằng nếu hai số nguyên có tích các ớc số khác nhau thì hai sốnguyên đó khác nhau.3.9.Tính các đồng d sau đây bằng nhiều phơng pháp khác nhau (chẳng hạn bằngphơng pháp bình phơng liên tiếp hoặc nhờ nhận xét cuối Đ2):1. 31000000mod 165.2. 51234567mod 221.3. 71000000000mod541.3.10. Chứng minh rằng 91 là số giả nguyên tố cơ sở 3 nhng không giả nguyên tốEuler cơ sở 3, và không là số giả nguyên tố cơ sở 2.3.11. Cho f(n) là hàm nhân tính giới nội. Chứng minh rằng tổng f ( n) / nshội tụ tuyệt đối trong nửa mặt phẳng Re s>1 (trong đó Re là kí hiệu phần thực củamột số), và tổng trong miền hội tụ bằng tích vô hạn hội tụ sau đây (1 + f ( p) ps+...+ f ( p m ) p ms +...) ,pP(tích đợc lấy trên tập hợp tất cả các số nguyên tố).3.12. Chứng minh rằng, nếu f là hàm nhân tính mạnh giới nội thì f ( n) / nn =1s1.spP 1 f ( p) / p=3.13. Chứng minh đẳng thức sau đối với Zeta-hàm Riemann:1.sp P 1 p ( s) = 1 / n s = n =13.14. Chứng minh rằng nếu n 2,4,p ,2 p , trong đó p là số nguyên tố lẻ thìa ( n )/ 2 1(mod n) .3.15. Chứng minh rằng nếu n chia hết cho 24 thì (n) cũng chia hết cho 24.533.17. a) Chứng minh rằng nếu p,q là các số nguyên tố lẻ khác nhau thì n=pq là số giảnguyên tố cơ sở 2 khi và chỉ khi ordq2|p-1, ordp2|q-1.b) Trong các số sau đây, số nào là số giả nguyên tố cơ sở 2: 871, 1378, 2047, 2813.3.18. Chứng minh rằng nếu p,q là các số nguyên tố lẻ khác nhau thì n=pq là số giảnguyên tố cơ sở 2 khi và chỉ khi MpMq=(2p-1)(2q-1) là số giả nguyên tố cơ sở 2.3.19. a) Chứng minh rằng nếu đa thức f(x) bậc n, hệ số nguyên, có quá n nghiệmmodulo p thì mọi hệ số của f(x) đều chia hết cho p.b) Cho p là một số nguyên tố. Chứng minh rằng mọi hệ số của đa thứcf(x)=(x-1)(x-2)...(x-p+1)-xp-1-x+1chia hết cho p.c) Dùng câu b) để chứng minh định lí Wilson.3.20. Tìm tất cả các số tự nhiên n sao cho: (n)=12, 18, 24, 48, 52, 84.3.21. Chứng minh rằng với mọi k>1, phơng trình (n)=k có vô số nghiệm.3.22. Tìm n nhỏ nhất để (n)=1, 2, 3, 6, 14, 100.3.23. Tìm căn nguyên thuỷ modulo:112 , 17 2, 132, 192, 3k, 13k, 11k, 17k.3.24. Chứng minh rằng nếu m có căn nguyên thuỷ thì đồng d x2 1(mod m) chỉ cónghiệm x= 1(mod m).3.25. Chứng minh rằng mặc dù không tồn tại căn nguyên thuỷ 2k, k 3, mỗi sốnguyên lẻ đồng d với đúng một số nguyên dạng ( 1) 5 , trong đó =0 hoặc 1, là số nguyên thoả mãn o 2 k 2 1 .3.26. Giả sử n là một số có căn nguyên thuỷ. Chứng minh rằng tích của các sốnguyên dơng nhỏ hơn n và nguyên tố cùng nhau với n đồng d (-1) modulo n (khi nlà số nguyên tố, ta có định lí Wilson).3.27. Tìm tất cả các nghiệm của đồng d sau:a) x2+x+1 0(mod 7)b) x2+5x+1 0(mod 7)c) x2+3x+1 0(mod 7).II. Thực hành tính toán trên máy tínhII. 1. Tính Phi-hàm EulerĐể tính Phi-hàm Euler của một số nguyên dơng n ta thực hiện dòng lệnh nh sau:[> phi(n);54Sau dấu (;) ấn phím Enter màn hình sẽ hiện ra kết quả.Thí dụ: Tính Phi-hàm Euler của 65.[> phi(65);48II. 2. Thực hành tìm các số khi biết phi-hàm Euler của nóĐể tìm các số khi biết Phi-hàm Euler k ta thực hiện dòng lệnh sau:[>invphi(k);Sau dấu (;) ấn phím Enter màn hình sẽ hiện ra các số cần tìm.Thí dụ: Tìm các số khi biết Phi-hàm Euler của nó là 4.Ta thực hiện nh sau:[> invphi(4);[5, 8, 10, 12]Vậy các số có Phi-hàm Euler bằng 4 là 5, 8, 10, 12.II. 3. Thực hành kiểm tra số nguyên tố MersenneCho m là một số nguyên dơng, đặt Mm:=2m-1. Để kiểm tra xem Mm có phải là sốnguyên tố Mersenne hay không ta thực hiện dòng lệnh nh sau:[> mersenne(m);Sau dấu (;) ấn phím Enter. Nếu trên màn hình xuất hiện kết quả là một số thì Mmlà số nguyên tố Mersenne và Mm chính bằng số đó. Nếu không trên màn hình sẽ xuấthiện chữ false.Thí dụ 1: M7 có phải là số nguyên tố Mersenne hay không?Ta thực hiện dòng lệnh nh sau:[> mersenne(7);127Vậy M7=127 và là số nguyên tố Mersenne.Thí dụ 2: M125 có phải là số nguyên tố Mersenne hay không?[> mersenne(125);falseVậy M125 không phải là số nguyên tố Mersenne.55Thí dụ 3: M11 có phải là số nguyên tố Mersenne hay không?[> mersenne(11);falseVậy M11 không phải là số nguyên tố Mersenne.II. 4. Tính bậc của một số theo một modulo nào đóCho m là một số nguyên dơng, n là một số nguyên. Để tính bậc của n modulo m tathực hiện dòng lệnh nh sau:[>order(n,m);Sau dấu (;) ấn phím Enter. Nếu m, n là các số nguyên tố cùng nhau thì trên mànhình sẽ xuất hiện kết quả chính là bậc của n theo modulo m. Nếu m, n không nguyêntố cùng nhau thì trên màn hình sẽ xuất hiện chữ FAIL.Thí dụ 1: Tính bậc của 13 theo modulo 100.[> order(13,100);20Vậy ord10013=20.Thí dụ 2: Tính bậc của 5 theo modulo 8[>order(5,8);2Vậy ord85 =2.Thí dụ 3: Tính bậc của 8 theo modulo 12.[> order(8,12);FAILII. 5. Tìm căn nguyên thuỷ1. Cho n là một số nguyên lớn hơn 1. Để tìm căn nguyên thuỷ đầu tiên modulo n tathực hiện dòng lệnh nh sau:[> primroot(n);Sau dấu (;) ấn phím Enter. Nếu trên màn hình hiện ra kết quả là một số thì số đóchính là căn nguyên thuỷ đầu tiên modulo n. Nếu màn hình hiện ra chữ FAIL thì nkhông có căn nguyên thuỷ.Thí dụ 1: Tìm căn nguyên thuỷ modulo 41.[> primroot(41);6Vậy 6 là căn nguyên thuỷ modulo 41.56Thí dụ 2: Tìm căn nguyên thuỷ modulo 15.[> primroot(15);FAILVậy 15 không có căn nguyên thuỷ.2. Để tìm căn nguyên thuỷ modulo n lớn hơn g ta thực hiện dòng lệnh sau:[> primroot(g,n);Sau dấu (;) ấn phím Enter. Nếu trên màn hình hiện ra kết quả là một số thì số đóchính là căn nguyên thuỷ lớn hơn g đầu tiên modulo n. Nếu màn hình hiện ra chữFAIL thì n không có căn nguyên thuỷ. Chú ý, nếu g=0 thì hai lệnh trên là nhnhau.Thí dụ 1: Tìm căn nguyên thuỷ đầu tiên lớn hơn 7 modulo 41.[> primroot(7,41);11Vậy 11 là căn nguyên thuỷ lớn hơn 7 đầu tiên modulo 41.Thí dụ 2: Tìm căn nguyên thuỷ đầu tiên lớn hơn 2 modulo 8.[> primroot(2,8);FAILVậy 8 không có căn nguyên thuỷ lớn hơn 2.II. 6. Thực hành tính hàm (n)Để tính giá trị của hàm (n) tại n ta thực hiện dòng lệnh nh sau:[> tau(n);Sau dấu (;) ấn phím Enter màn hình sẽ hiện ra kết quả.Thí dụ 1: Tính (-9).[> tau(-9);3Thí dụ 2: Tính (100).[> tau(100);9Vậy số các ớc dơng của 100 là 9.II. 7. Thực hành tính hàm (n)Để tính giá trị của hàm (n) tại n ta thực hiện dòng lệnh nh sau:[>sigma(n);57Sau dấu (;) ấn phím Enter màn hình sẽ hiện ra kết quả.Thí dụ: Tính (9).[>sigma(9);13Vậy tổng các ớc dơng của 9 là 13.II. 8. Thực hành tính đồng d thức, giải phơng trình đồng d1. Để tính đồng d của a theo modulo n ta thực hiện dòng lệnh nh sau:[> a mod n;Sau dấu (;) ấn phím Enter màn hình sẽ hiện ra kết quả.Thí dụ: Tính 51234567 mod 221[> 5&^1234567 mod 221;1122. Để giải phơng trình đồng d ta thực hiện dòng lệnh nh sau:[>msolve (các phơng trình, modulo);Sau dấu (;) ấn phím Enter, nếu phơng trình đồng d có nghiệm màn hình sẽ hiệnra kết quả.Thí dụ: Tìm nghiệm của đồng d sau:x2+x+1 0 (mod 7)[>msolve(x^2+x+1=0,7);x=4, x=2Vậy nghiệm của phơng trình là x=2, x=4(mod 7).58