Lý thuyết Số học phổ thông: Phần 1

Chia sẻ: Lê Na | Ngày: | Loại File: PDF | Số trang:129

Thêm vào BST

Báo xấu

169
lượt xem 42
download

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

Phần 1 Tài liệu Số học phổ thông trình bày các nội dung: Lý thuyết chia hết trong vành số nguyên, số nguyên tố, một vài hàm số số học, liên phân số, phương trình nguyên. Tham khảo nội dung Tài liệu để nắm bắt nội dung chi tiết.

Chủ đề:

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

Lưu

Nội dung Text: Lý thuyết Số học phổ thông: Phần 1

if ÒÒHOC PHÔ THÔNG
ị /) É Ổ % NGUYỄN HỮU HOAN 'ộ SỐ H Ọ C PHÔ T H Ô N G Ị ĩ Is: - Vv I J ÍT -Ị -Mrr>VT I "nr; V in;; h ỉ 007854 Ị THÔN Q T Í N - Tmiívjgy NHÀ XUẤT BẢN ĐẠI HỌC VÀ TRUNG HỌC CHUYÊN NO.HỆ HÀ Nệl - 1986
Ig m ỗ i văn đè ngoài nội dung cơ bàn nói trôn, mỗi khi được, chúng tôi còn giúi thiệu những thành lựu lớn lia I những bài toán hay đang còn chờ đợi lởi giải. lối mỗi bài có nhiêu bài tập dã được lựa chọn đê bạn \ì l u y ệ n và c ủ n g cố chắc kiên thặc đã đọc, một số Lài linh chát bồ sung cho lý thuyết ngay trong bài đó hoặc tliiõt cho các bài sau. Tát cả các bài lạp đêu có dr.p dẫn hoặc l ờ i giai chi tiết. . dung cuốn sách dược trình bàv hoàn toàn bằng toán p nhưng theo m ộ t sự lựa chọn và sắp xếp phù họp với g khái niệm trong đ ạ i sỗ hiện đại. Ỵ vậy đê hiều được, bạn đọc chỉ ràn có kiên thặc toán íp hai bậc phò thông, một số kiến thặc về đa thặc. Ngoái một số k ý hiệu, chSc r ằ n g bạn đọc có thê chóng làm qui'ì! hi đọc một vai trang đâu của cuốn sách. hân đây tác già xin bày tỏ lòng biết ơn đỗi với giáo sít Đặc Thịnh và giáo sư Ngô Thúc L a n h đã giúp đờ và góp mi tiít nội dung cuốn sách. Tác giả cũng xin chiìn t h á n Í! n an sự quan lâm giúp đồi của cốc (tồng chí trong tò Dại sỏ lộc k h o a Toán trường Đại học Sư phạm Hà N ộ i ì, khi tác lit v i ẽ t cuốn sách này. Chúng tôi không nghĩ r ằ n g cuốn sách n à y đa đtrợc h o "in t h i ệ n Ồ m ọ i mặt, bôi vậy chúng lôi rát mong bạn dọc vui lòng chì' ho những thiêu sót. T h ư từ góp ý xin gửi vè Nhà xuất bản! lại học và Trung học chuyên nghiệp 45 — H à n g Chuối, Hà Nội NGUYỄN HỮU HOAN
MỞ ĐẦU < T r o n g cuốn sách này chúng tôi sô sử dụng một số ỊỊậễn thức m à bạn đ ọ c có thề đã quen biết ít nhiêu, p h ú n g tôi nhắc lại ở đ â y đẽ thống nhất với bạn đọc vè l á c van đ ề đ ó . 1. Khái niệm tập hợỌỵ C h ú n g ta thường vỉi> n ó i : Tạp hợp các học sinh trong một lớp h ọ c ; tập hợp các lớp trong một trường học, lập hợp các số tự n h i ê n : 0, Ì, 2, 3,..., lập hợp các số n g u y ê n : .... - 3 , - 2 , - Ì, 0, Ì, 2, 3,... Đ ế chỉ rằng a là một vặt của tập hợp A ta viết a ^ A v à đọc « a là một phàn tử của A » hoặc « a thuộc A i . Trong trường hợp a không là phần tử của A ta viết aỀA. Nếu m ọ i phàn tử của tập hợp A đ ề u là phỉn tử của tập hợp B thì ta viết A c B hoặc B > A , đọc lả a A là tập con của B » hoặc « A là một bộ phạn của B » hoặc « te chứa A ». Bằng ký hiệu lôgic chúng ta diễn tả điều kiện A c tì là V a : u £ A =• a £ B. Dâu « V » có nghĩa là c< tất cả » hay là « bát kỳ » hay là í m ọ i » ; dấu « => » c ó nghĩa là « k é o theo » hay là 4 suy ra ». Hai tập hợp A và B đ ư ợ c gọi là bằng nhau nếu như chúng chứa các phần tử y như nhau, nghĩa là mọi phàn
t ử thuộc A đ ê u thuộc B va ngược l ạ i . K h i á y ta v i ẽ t . A = B. Bằng k ý h i ệ u logic la có A =ị 13 «-> A c B và B ;> A. D ẫ u « 4 4 » chỉ sự t ư ơ n g đ ư ơ n g lògic giữa hai v ế , túc là m ỗ i vỗ đ ề u k é o theo vế kia và đọc là « k h i v à chỉ k h i » h a y là a nếu vả chỉ nếu » hay là ((Cần v à đ ủ » . Đ ề chỉ m ộ t tập h ạ n k h ô n g có phần t ử n à o ta vie! ộ, đọc là « r ỗ n g » . Chung hạn tập hợp các. nghiệm n g u y ê n của p h ư ơ n g trình 4x — Ì = 0 là rỗmị. V i ế t A = ị c ó nghĩa 2 « A là rỗng)), còn v i ế t A =fc (Ị) nghĩa là A chửa ít nhai một phần t ử n à o đ ó . N h ư v ậ y A =f= ệ
A = I a, b, c, X, yỊ ĩỉ = Ị a, X, y, z I ta c ó A w R = Ị a, b, 0. X, y. z Ị A A B = Ị a, X, y |. 2. T ồ họ-p v à n h ị I h ứ c N i u t ơ n . C h o tập hợp A g ồ m n phan (ử (n > 2). Mỏi m ộ i l ậ p con g ồ m k p h à n l ử c ủ a tập hợp A đ ư ợ c gọi là m ộ t tồ hep chạp k c ủ a TI phần í ử dã cho. Chẳng h ạ n v ớ i A = ị a j , a . a , ai Ị la c ó b ừ n tồ hợp chập 3 c ủ a 4 phần 2 3 tử c ủ a A là ị ít,. a a ị, ị ai, a , a.| ị. ị a a „ a ị v à ị a . 2> 3 2 h : 4 2 &3. a ị. Đ ễ chỉ s ừ tô h ợ p chập k c ủ a li phần tử (a v i ế t 4 k c . T a c ó c ô n g thức k c - "( ~ n Ị) ••• ( n - k + ĩ) n ~ k ! Ở đây k! = 1.2... k ( đ ọ c là « k giai thừa))) và đ ề cho thuận tiện, n g ư ờ i ta qui ư ớ c 0! = 1. C ò n g thức sau đ à y đ ư ợ c gọi là nhị thức Niu tan: 1 1 1 (X + ý ) " = c V + c X"- y+.... + c"~! xy"- + c" y». J I n n " li J n - Vế phải c ủ a đẳng thức t r ê n viết lắt là n l ; k k 2 c x"- Y . „ n k=0 (đọc là ((xích [na li từ 0 tới n c ủ a cỉ\\" kyk », nghĩa , _ k k là t ô n g các hạag lử c V y . k = 0, Ì n. 3. T ậ p hợp sừ tự nhiên. T r o n g tập hợp s ừ tự n h i ê n N = ịo. 1. 2....Ị p h é p c ộ n g v à p h é p n h â n l u ô n l u ô n I h ự c h i ệ n đ ư ợ c , tuy n h i ê n p h é p trừ v à p h é p chia cho s ừ k h á c 0 k h ô n g phải bao 7
g i ờ cũng thực h i ệ n đ ư ợ c . Vói m ỗ i sỏ tự n h i ê n a cho t r ư ớ c , bao g i ờ cũng có duv nhất một số t ự n h i ê n bé nhất l ớ n h ơ n n ỏ , đ ó là số a + 1 ; g ọ i là số kè sau của a. C h ú n g la n ê u lên m ộ t số k ế t quả quen thuộc sẽ được sử dụng trong cuốn sách n à y H ê n h đ ề Ì (Tiên đề qui nạp). Giả sử M c N thỏa mãn hơi điêu kiện 1) O^M 2) a £ M a + Ì £ M. Khi ấy la có M = N. T ừ mệnh đ ê Ì suy ra hệ q u ả sau đ â y g ọ i là phép c h ặ n g minh qui nạp t o á n học. H ệ quả. Nêu mệnh đè loàn học % (n) nào đó phụ thuộc váo sô tự nhiên Tì, thỏa mãn các điêu kiện : ỉ) (n) đúng với n = 0; 2) Oà (n) đúng với số tự nhiên n = a kéo ìheo
M ệ n h đ ề 3. Mọi bộ phận khác rỗng và bị chặn của tập hợp N các số tự nhiên đêu có sô lớn nhôi. M ệ n h đ ề é. (Nquyên tắc ngăn kéo của Dỉriclê). Nêu đem xếp tiết tăt cả TI vật vào Tì - Ì ngăn kéo thì nhát thiết có mội ngăn kéo nào dỏ chứa ít nhát hai vật. 4. T ậ p h ợ p số nguyên. Chúng ta thấy rằng tập hợp số nguyên z = I 0, ^£-2,...} gồm tất cả các số tự nhiên và đ ố i của tất cả các số tự nhiên. Trong tập hợp số ngii)-ên các p h é p toán cộng, trừ và nhân l u ô n Luôn thực hiện được, tuv nhiên phép chia cho số n g u y ê n khác 0 không phải bao giở cũng thực hiện được. Khác với tập hợp số tự nhiên* tập hợp số nguyên không có số nhỏ nhất. Giả sử M c z. Ta g Ị i M là bị chặn "trên nếu như 3 a «s z sao cho X < a, V x ^ M. T ư ơ n g tự, la gỊi Mlà bị chặn d i r ớ i nếu như 3 b € z sao cho b < X, Vx ^ Mi Tập hợp M được gỊi là bị chặn nếu nó vừa bị chặn trên vừa bị chặn dưới. T a c ó : M ệ n h đ ề 5. Mọi bộ phận khác rỗng và bị chặn trên của tập hợp sô nguyên z đều có sô lớn nhái. Mọi bộ phận khác rỗ nọ và bị chặn dưới cùa tập hợp sô nguyên z đổu có sô nhò nhất. Giá tri tuyệt dổi c ủ a s ố n g u y ê n X l à một số tự nhiên^ ký hiệu là |x ị được xác định như sau : . _ ( X nếu X £ N, | x l ~ Ị - X nếu XỀN. Ta có các hệ thức - | x ị < x < i x | ; im - i y K u ± y i < i J t i + iyi ; I XV I = I X li y I Ồ
BÀI THỬ NHẤT LÝ THUYẾT CHIA HÉT TRONG VÀNH SỔ NGUYÊN §1. TÍNH CHIA HẾT ì - ĐỊNH NGHĨA Cho hai số nguyên, a v à b , h =j= 0. Ta nói a cilia hối cho b, hay b chia lúi a n ế u n h ư có số ngu vón q sao cho a = bq, K h i ãv n g ư ờ i ta c ò n nói a là b ộ i của 1) liav b là ước của a và k ý h i ệ u a '• b lun b I a, Chú ý: Nếu b I a m à a 0 thì t ừ a = bq ta có (Ị Ị= 0 cho n ê n h i ề n n h i ê n ị a 1 = 1 b ị I q I ^ I b I bởi v i i q ì > 1 . li - TÍNH CHẤT 1. b la =>. ±b \ ±ã ; 2. a I a, V ẩz . a + 0 ; a a 3. 4-1 l a , Y € z . Ngoài ± 1 ra k h ô n g còn số n g u y ê n n à o k h á c có tính chất n à y ; a 4. 0 ; a, V €EZ, a 4* 0. Ngoài 0 ra k h ô n g c ò n số n g u y ê n n à o k h á c có tính chất nà)' ; 5. b I a v à a I b ^ a = ± b ; G. a ị Ì) và b I c a Ic; 7. c I ai, i = 1.2,..., n c I a i X | + a x , 4- ... + a „ V „ ; 3 Xi € z . i = 1. ,n. Các lính chất t r ô n đ à v đ ư ợ c chửng minh (lề (làng, coi đó là những bài tập đ ơ n £ ụ n . ớ' đ à y chúng la : chứng minh t i n h chất 5 l à m v i d ụ . Từ b I a và A ỉ b la có q, q ' z sao cho a = bq và b = aq'. Hai riaI).Lị t h ứ c n à y cho ta a = aqq' và do a =f= 0 ta có qq' = 1. Theo t í n h chất 3 ta phụi có hoặc q = q' = Ì khi đó a = b : hoặc q = q' == — Ì k h i đó a — — b. lủ
HI - PHÉP CHIA CÓ Dư 1. Định lý. Cho hai sỗ nguyên a vá b, b ="£»0. A7ỉ/ ây zà duy nhất cộp sô nguyên q, r tháu mưu cúc hệ thức a -ỵ bq 4- r và 0 < r < Ị bị, (1) Chứng minh. ì) Có cặp số n g u y ê n q, r thỏa m ã n các hộ thức (1). C h ú n g la x ẻ l tập hợp AI = ị b x | x < c z , bx < a Ị. Hiên n h i ê n Mcz vò \ỉ =f= ệ h ở i v i — I b ị I a I là m ộ t bội của b k h ô n g v ư ợ t q u ả a. Hơn nữa M bị chặn t r ê u bởi a, n é n iheo mệnh đ ề 5, trong M có phẳn t ử l ớ n nhfit, chẳng h ạ n là bq, q £ z . Vì ị b Ị > Ì n ê n bq + I b I > bq từ đ ó b q + ịb ị Ể M. H ơ n nữa bq + I b | cũng là b ộ i cua b cho n ê n ta c ó bq < a < bq + I b ị hav 0 < a - bq < ị Ì) Ị. Bằng cách đ ặ t r = a — bq ta đ ư ợ c r
chia a cho b. Nếu r =^= 0 íhì ta nói (ló lù p h é p chia cỏ d ư , r (lược gọi là số dư, q đ ư ợ c gọi lú số lhương hụt h òng p h é p chia a cho b. § 2 . ƯỚC CHUNG L Ở N NHẤT (ƯCLN) ì - Đ Ị N H NGHĨA ' — M ộ t số nguvêri đ ư ợ c gọi là irớc chung Clip, các số n g u y ê n ai, a v, a nếu nó là ước đồng t h ờ i của m ỗ i 2 n số đ ó . — M ộ i ước chung d của các số ai, a , a sao cho 2 n m ọ i ước chung của a i , a , a đ ề u là ước của (I d ư ợ c 5 n g ọ i là ước chung lởn nhát ( v i ế t t ắ t là UCLN) củ;! các số đ ó . — N ế u số Ì l à ước chung l ớ n nhất của các hố aj, a j , a„ thì ta nói các số ai, a j , a là nguyên n lố cùng nhau. Còn nếu số ] là ư ớ c chung l ớ n nhất của m ọ i c ặ p 1 ai, ũj v ớ i i =± j ; i , j = Ì, 2 n thì ta nói các số ai, a, 2 a là nguyên n lổ cùng nhau lừng đôi mội, hay nguyên lố sánh đôi. Chú ý. í . T ằ p hợp các ư ớ c chung của n h i ề u số cho t r ư ớ c t r ù n g v ớ i l ằ p hợp các ước của ƯCLN của các. số đ ó , 2. Ta b i ế t số Ì là ư ớ c chung của m ọ i số n g u y ê n , nôn c á c số a i , a ,2 a bao g i ờ cũng có ư ớ c chung ít nhất n là số 1. Số 0 là b ộ i của m ọ i số n g u y ê n k h á c 0 cho n ê n ' n ế u tất cả các sổ a i , a a a đ ề u bằng 0 thì mỗi số n n g u y ê n k h á c 0 đ ề u là ước chung của c h ú n g , trong t r ư ờ n g h ợ p n à y k h á i n i ệ m UCLN k h ô n g có nghĩa nữa. Do đó ta già t h i ế t r ằ n g c á c sổ ai, a , ? a„ đ a n g xét k h ô n g phải bằỊig 0 tất cả. H ơ n nữa t ằ p h ọ p l ấ t cả các ước chung
của các số đ a n g x é t s ẽ k h ô n g thay đ ồ i nếu la t h ê m v à o hay bớt d i G á c số bằng 0. B ở i v ậ y có thề giả thiết thêm U i --Ị= 0 v ớ i m ọ i i = Ì, 2, .... n. 3. Nếu d là m ộ i UCLN của các số a i , a a thì — d 2 n cũng là m ộ t UCLN của các số đ ó . H ơ n nữa nếu d và d* là UCLN của các số a , a a thì d ' = ± ả. Do 1 3l n t đ ó (ừ đ â y v ề sau nếu k h ô n g có gì thay đôi. ta s ẽ l ấ y số d ư ơ n g d trong c á c ƯCLN của aj, a , a làm UCLN 2 n của c h ú n g v à k ý h i ệ u d = (ái, a , a ). 2 n 4. V ớ i chú ý 3) ta có t h è định nghĩa: UCLN của các số n g u y ê n a j , a a là s ổ l ớ n nhát trong t ậ p hẳp các 2 n ước chung của c h ú n g . Có t h ê chứng minh đ ư ẳ c r ằ n g hai định nghĩa v ề U C L N đã n ê u là t ư ơ n g đ ư ơ n g , nếu k h ô n g k ẽ đ e n sự sai k h á c m ộ t thừa số + 1 . l i - Đ Ị N H LÝ. Có ước chung lớn nhất của các sỗ nguyên khác không ai. a a cho trước. ĩt a Chứng minh. Chúng ta xét tập hạrp: M = ị aĩxi + a x + .. + a x / X i € Ì i = Ì, 2, .... 2 a n n n ị. Ta cố M c z v à M chứa ít nhất m ộ i số n g u y ê n d ư ơ n g , thật vậy, chẳng hạn l ấ y • _ ( Ì với a > 0, Xít = ị k í — Ì với a k < 0 v à Xi = x 2 = ... = 'x _i = k x k + I . = ... = x n thì tá Ihấv rằng = : § AịXi + a x + ... + ' a „ x » = I a 2 2 k I > 0 . I a I € M- B ở i v ậ y k t r o n g M c ó số H g u y ê n d ư ơ n g n h ỏ n h ấ t , chẳng h ạ n l à d, ' nghĩa là d s a j U i + a ^ a + .-.+anUn, Uj£Z, i = l , 2 n v à d < x , V x £ M, X > ỡ. Ta s ẽ c h ứ n g minh d = ( a a , .... a ). T r ư ớ c hết la t h ấ y b 2 n d I X , V x ^ M . Thật v ậ y , X M n ê n có các số n g u y ê n X i , X 2 . . . , x„ sao cho X = ajXi + a x + ... + a x „ . Giả sử 2 2 n Ỉ3
X = d q + r, 0 < r < d, r, q £ z. Ta thấy r ằ n g r ~ 0 vì níu 0 < r < d thì r = x—dq = a , ( x - u q ) - f a ( x - u q ) + . . . + a ( x - v i q ) I 1 2 2 2 n n n là m ộ t số n g u y ê n d ư ơ n g nhỏ h ơ n d, thuộc M , trối v ớ i cách chọn sỗ d. T ừ r = 0 ta có X = dq, q £ z . n g h ĩ a là d I X , V x £ M. Bởi vì a = a 0-f... + ai.. O + a l + a k 0 + . . . - f a O ^ M nôn 1 l k k + 1 n d I a , k = 1. 2. k n. Mặt k h á c nếu ố I a . k = .l, 2 n Hù la có ỏ I 3(111 + k + a u + ... 4- a u., tức là ổ I (ỉ. Vậy d là UCLN của, 2 2 n ai, a , ii„ và định ỉỷ đ ư ắ c chửng minh. 2 H I - H Ệ QUẢ 1. X ê u á = (rí,, (/•_>, í/,J //ỉí ắ/ có các sô WjUijfU Ui, ; u í':.., f/„ sao ('/ỉO í/ =
Khi ấy rõ ràng kd là số nguyên dương nhỏ nhất trong tập hợp k M = ị (ka,)x, + (ka )x + ... + (ka )x 'x € z, i = Ì, 2 , 2 2 n n f ..., n ị mà số nguyên dương nhỏ nhất trong tập hợp kM xác định như^lrên chính là (kai, ka ka ), cho nên 2 n i;i có (ka ka , b ka„) = k(ai, a , 2 a„). 2 b) Áp dụng kết quả a) của hệ quả trong truồng hợp 6 I ai i — ĩ , 2, l i ; 8 > 0 ta có (a„ i . , a„) = (b.h., 6 > , .... 6 . ^ \ = V Ố Ỏ ố / = 6 ^ , .... ^ - 1 cho nên Vố ố ố / a a a Ị l -í - i i i : 2' ") V Ố ' bì ố ' "" ố 4. Điêu kiện căn và đủ dì một ước chung dương d cùa các sô ar, ƠJ, a là UCLN n của chủng là các sỗ —. — nguyền lõ cùng nhau. Chứng minh. Giả s"ữ d > 0 . d I aj. i = Ì, 2, l i . Khi ây áp dụng hệ quả 3 ) ta cổ d =
2. Nêu (a, b) = í vả c là một sỗ nguyên tùy ý Hù {ác, b) = (c, b). Chứng minh. Dựa v à o chú ý 1) ì, § 2 ta chứng minh tập hợp các ước chung của ác và b t r ù n g v ớ i tập hợp các ước chung của b v à c. Giả sử 6 £ z, ò I ác và ỏ Ị b. khi ấ y í I ác v à ố I be, hay là ố I (ác, be). N h ư n g ( á c be) = (ít.-b) c = 1. c = c nên ố I c. Vậy ta có ố j b và ố Ị c. Ngược l ạ i , g i ả sử ỏ £ z, ố I b và ó I c thì h i ề n n h i ê n ta có ố I b và ố ị ác. 3. Nêu (a, b) = (a, c) =1 Hù (a, be) = 1. T ô n g q u á t : nếu (à;, bj) = Ì, i = Ì, 2,..., m, j = Ì, 2 rì thì (aja ...a , bi b ,... b„) = 1. 2 m 2 Chứng minh. T í n h c h á t n à y là h ệ quả của tinh c h ấ t '2. bời vì từ (a, b) = Ì ta có (a, be) = (a, c) n h ư n g (a, c ) = 1. T r ư ờ n g hợp tông q u á t lý l u ậ n t ư ơ n g t ụ , hoữc c ó thè chứng m i n h qui nạp. V - CÁCH TÌM Ư ổ r c C H U N G LỚN NHẤT 1. Tìm ước chung lưu nhốt của hai số : Cho hai s ổ n g u y ê n a và b, ta có thề giả thiết rằng a > 0, b > 0 và a > b. a) Trưởng hụp b I a. K h i ấ y la có (a, b) = b. T h ệ ! v ậ y b là ước của a v à b là ước của b n ê n b là ước chung của a và b h » n nữa m ọ i ước chung cần a và b h i ê n n h i ê n là ước của b. V ậ y (a, b) = b. b Trường hợp b không chia hết a. Chú ý : Với a, b, c ^ z sao cho a = bq + c, ọ € z, /« có (a, 6) = (ế, c). T h ậ t v ậ y , m ọ i ước chung của-a và b đ ề u là ước của c = a — bq n ê n cũng là ước chung của b và c. Ngược l ạ i m ọ i ước tìhung của b v à c đ ề u là ư ớ c của a = b q + c n ệ n cũtìg l à "iiớc c h ù n g của a v à b. Bôi v ậ y ta có (a, b) = (b. é). 16
- Thuật toán ơclid. K h i b không chia hểt a thì la có a = bq + 1-j, 0 < ri < b; b = r q + r , , 0 < r < r, ; 1 1 2 2 r n-J = I*n-I q .in -f- r , 0 0 < I n < r»_i r 0-i = r„q . n Dãy các p h é p chia liên t i ế p n à y gọi là thuật t o á n ơ c l i d thực h i ệ n t r ê n hai số a v ấ t ) . Số các p h é p chia này phải là h ữ u hạn và thuật toán 0'clid p h ả i k ế t thúc Nới m ộ t số d ư r — 0 v i d ã y các số b, r i , r ,... là d â y 1 1 + I s c á c số tự nhiên g i ả m d ầ n và do đ ó la có k h ô n g q u á b p h é p chia. Theo chú ý ở t r ê n ta có (a, b) = (b, Tị) — ... = (r„_i, r ) và v i r „ _ i = r q n ê n theo k ế t q u à a) thi ( r „ _ i . r ) = r , n n n n n do đ ó (a, b) = r . Nghĩa là : UCLN của hai số a và b a bằng số d ư cuối cùng k h á c k h ô n g trong thuật toán ơ c - l i d thực hiện t r ê n hai sổ đ ó . Ví dụ. Hãy t ì m UCLN của 924 v à 360. Thực h i ệ n thuật t o á n ơ c l i d t r ê n hai ^ đ ó ịèị đ ư ặ c 924 = 360 . 2 + 204, 360 = 204. Ì + 156, 204 = 156 . Ì + 48, 15G= 48.3 + 1 2 , 48 = 12 . 4. SỐ d ư cuối c ù n g k h á c 0 ở đ â y là 12. V ậ y (9Ì4, 3 ê 0 ) = 12. T r o n g thực h à n h n g ư ờ i ta đ ặ t p k é p tính n h ư sáu . 92*-, 3Si I 2 i k 284 Ị 156 \~~ịW 156 iLÍ Ì 48 12 0 4 nên (924, 368) = 12. 2-SHPH
2. T ì m ước chung l ớ n n h á i cùa n h i ề u số. G i o c á c lố n g u y ê n d ư ơ n g 3], a ... , a„ la đặt d = (in a ,... a ) 2 s n ỉa* ă-i) = dí, (dạ, a ) = ( l , . . . , ( d „ . j . a„) = d„ Hù la c ó s 3 d = d . n Thật v ậ y la d ỗ tháy r ằ n ; ' m ọ i ước cluing của a i , a 2 a3,... a đ ề u là ước chung của d , a ... a vù ngược l ạ i . n 2 3l n Vì v ậ y la có (ai, a , a s a ) = ( d , a ,..., a ). 3 n 2 3 n L ặ p l ạ i l ý luận n à y n h i ề u l ầ n , ta sẽ được (ai, ai,..., a ) = ( d , a ..., a ) = ( d , a ,..., a ) = ... = (
4) V ó i c h ú Ý 3) ta có (hễ định nghĩa BCNN của c á c số n g u y ê n a i , a , . . . , a „ íà sổ nhỏ nhai trong t ậ p hợp c á c 2 h ộ i chung d ư ơ n g của c h ú n g . Có t h è chứng m i n h d ư ợ c r ằ n g h a i d i n h nghĩa v ề BCNN đ ã n ê u là t ư ơ n g đ ư ơ n g n ế u k h ô n g k ê đ ế n sự sai k h á c m ộ i thừa số ± 1. Củ bội chung nhỏ nhất I I - D Ị N T l LÝ. của các sô nguyên khác không a a ,..., a cho Irước. u t n Chứng minh: Chủng ta x é t t ậ p h ợ p M = Ị x £ Z I X l a i , i T= Ĩ , 2, . . . . ri ị . ra c ó M e z v à Ai chứa ít nhất m ộ t số n g u y ê n d ư ơ n g , chẳng h ạ n s ố I a i a ... a„ I ^ M. Bửi v ệ } ' trong M cỏ số 2 d ư ơ n g n h ỏ n h ấ t m , nghĩa l à m i a i , i = l , 2,..., m > 0 v à n i < X , X ^ M , X > 0. Til sè. c h ứ n g l ĩ i i n h m = [ a i , a , . . . , a „ ] . 2 Giả sử ịx l à m ộ t b ộ i chung của a i , a ,..., a v à giả sử 2 n ụ = mq + r, 0 < r < m , q, r ^ z . B ả i v i n ; a;, m ỉ á p : i = Ì, 2,..., n n ô n r = ụ. — mq a i = Ì, 2, lì tức là it r
1 các số — , — — có m ộ t ước chung d =f> j b n à o đ ó ai a 2 a„ in khi đ ó ---—là bôi chung của ai, a a„ v à 0 < "d < 2 d m. Điều n à y trái v ớ i g i ả t h i ế t m là BCNN của ai, a , ...a . 2 n Ì „ r^.- , • - , —. ni ni ni,. , b) Đí( ii kiện dù. Cho b i ế t ~~ , — 5 — là che so n g u y ê n ai a a 2 n tố cùng nhau, ta sẽ c h ứ n g minh m là BCNN của ai, a ,..-' 2 a„. Thật v ậ y , n ế u k h ô n g n h ư t h ê , thì giả sử ni' là BCNN của ai, a . K h i á y ắ t có số n g u y ê n d > Ì đ ề m = drn. B T ừ đ ó ta c ó m /m_ m_ \ _ /dm* d m ' dm'\ _ \ ill ' a ' " ' a / 2 n 1 a, ' a ' ' a„ / 2 V ai a 'A J 2 , I / ra m m\ m m m , suy ra d —, — , . . . . — ), nghĩa là — , — -— có | U | a 2 a„ / ai a, a n m ộ t ư ớ c chung d > Ì, trái v ớ i g i ả thiễt c á c số n à y ià nguj-en l ỗ c ù n g nhau. 2. a) Với k là một sỗ nguyên, dương, ta có [ ka ka . u 2 k a ] = k [ai, aĩ,..., a ] . n n b) V ớ i s ô n g u y ê n d ư ơ n g ố là m ộ t ư ớ c chung của các số a ãì,..., a t ã có b n ai aj a„l _ [ a i , ạ,- a„l — f I— • ó a bị ó Chứng minh. a) Đặt m = [a,, a ,...,a ] theo c á c h chửng 2 n m i n h định l ý ở l i , la c ó n i là sỗ n g u y ê n ả ư ơ n g n h n h á t của t ậ p h ợ p M = I X £ z I X i ai, i = Ì , 2,..., n ị. K h i đ ó k m sẽ l à số n g u y ê n d ư ơ n g n h n h ấ t của t ậ p hợp 20
k.M = I kx € z I X € z, X : a,, i = 1,2 l i ị. Bồi v ậ y n ế u ta chứng minh đ ư ợ c t ạ p hợp kM t r ù n g v ó i l ậ p hợp Mk = ị y