Luận văn Thạc sĩ Toán học: Đa thức Lucas, đa thức Euler và số Lucas, số Euler

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:45

Thêm vào BST

Báo xấu

40
lượt xem 3
download

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

Dãy Fibonacci, dãy Lucas, hàm Euler là những vấn đề cơ bản của số học, và luôn là đối tượng được quan tâm nghiên cứu. Những vấn đề trên không chỉ là những vấn đề của các nhà nghiên cứu, mà nhiều nội dung đã được đưa vào chương trình toán của bậc THPT, đặc biệt là trong chương trình bồi dưỡng học sinh khá giỏi. Vì thế có thể nói rằng, tìm hiểu về dãy Fibonacci, dãy Lucas, hàm Euler cho ta cái nhìn sâu hơn về mối liên hệ giữa toán học hiện đại và toán học phổ thông.

Chủ đề:

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

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Đa thức Lucas, đa thức Euler và số Lucas, số Euler

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC DƯƠNG MINH NGUYỆT ĐA THỨC LUCAS, ĐA THỨC EULER VÀ SỐ LUCAS, SỐ EULER LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên, năm 2016
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC DƯƠNG MINH NGUYỆT ĐA THỨC LUCAS, ĐA THỨC EULER VÀ SỐ LUCAS, SỐ EULER LUẬN VĂN THẠC SĨ TOÁN HỌC Chuyên ngành : Phương pháp Toán sơ cấp Mã số : 60 46 01 13 NGƯỜI HƯỚNG DẪN KHOA HỌC: GS. TSKH. HÀ HUY KHOÁI Thái Nguyên, năm 2016
i Mục lục Mở đầu 1 1 Dãy hồi quy tuyến tính 3 1.1 Iđêan và đa thức đặc trưng tối thiểu . . . . . . . . . . . . . 3 1.2 Nghiệm của quan hệ hồi quy . . . . . . . . . . . . . . . . . 5 1.3 Quan hệ hồi quy không thuần nhất . . . . . . . . . . . . . 10 1.4 Định lí Mahler-Lech . . . . . . . . . . . . . . . . . . . . . . 11 2 Số Euler và đa thức Lucas suy rộng 14 2.1 Hàm Euler và dãy Fibonacci . . . . . . . . . . . . . . . . . 14 2.1.1 Hàm Euler . . . . . . . . . . . . . . . . . . . . . . . 14 2.1.2 Số Fibonacci . . . . . . . . . . . . . . . . . . . . . . 19 2.2 Tính trù mật của φ(Fn )/Fn . . . . . . . . . . . . . . . . . . 22 2.3 Số Euler và đa thức Lucas suy rộng . . . . . . . . . . . . . 38 Tài liệu tham khảo 42
1 Mở đầu Dãy Fibonacci, dãy Lucas, hàm Euler là những vấn đề cơ bản của số học, và luôn là đối tượng được quan tâm nghiên cứu. Những vấn đề trên không chỉ là những vấn đề của các nhà nghiên cứu, mà nhiều nội dung đã được đưa vào chương trình toán của bậc THPT, đặc biệt là trong chương trình bồi dưỡng học sinh khá giỏi. Vì thế có thể nói rằng, tìm hiểu về dãy Fibonacci, dãy Lucas, hàm Euler cho ta cái nhìn sâu hơn về mối liên hệ giữa toán học hiện đại và toán học phổ thông. Luận văn này có hai phần. Phần thứ nhất trình bày một cách tương đối hệ thống và dễ hiểu về các dãy hồi quy tuyến tính và phi tuyến; về dãy Fibonacci và dãy Lucas, cũng như về hàm Euler. Luận văn cũng giới thiệu về một kết quả sâu sắc trong lý thuyết dãy hồi quy, là định lý Mahler-Lech. Cho đến nay, chưa có chứng minh nào của định lý này mà không dùng đến giải tích p-adic, là nội dung vượt ra ngoài khuôn khổ của luận văn. Vì thế luận văn chỉ giới hạn ở việc trình bày sơ lược (dựa trên bài viết của Terence Tao trên trang blog của ông). Phần thứ hai trình bày một kết quả gần đây (xem [2]) về tính trù mật φ(Fn ) của dãy { }, trong đọạn [0, 1], trong đó {Fn } là dãy Fibonacci, φ(m) Fn là hàm Euler. Đây là một mở rộng của kết quả cổ điển của Lucas, trong đó dãy Fibonacci được thay bởi dãy hồi quy đơn giản an = 2n − 1. Nhân dịp này tôi xin bày tỏ lòng biết ơn sâu sắc tới GS.TSKH Hà Huy Khoái, người đã tận tình hướng dẫn, giúp đỡ tôi hoàn thành bản luận văn
2 này. Tôi xin chân thành cảm ơn Ban chủ nhiệm khoa Toán trường Đại học Khoa học - Đại học Thái Nguyên cùng các thầy cô giáo đã tham gia giảng dạy khóa học. Xin chân thành cảm ơn gia đình, bạn bè, đồng nghiệp và các thành viên lớp Cao học Toán K8A đã luôn quan tâm, động viên, giúp đỡ tôi trong suốt quá trình làm luận văn. Thái Nguyên, ngày 22 tháng 5 năm 2016 Tác giả Dương Minh Nguyệt
3 Chương 1 Dãy hồi quy tuyến tính 1.1 Iđêan và đa thức đặc trưng tối thiểu Dãy số là một dãy gồm vô hạn các số, như 1, 2, 4, 8, 16, ... (1.1) Các số trong dãy số được gọi là các số hạng của dãy số, Ta viết dãy số là a1 , a2 , a3 , ... trong đó an là số hạng thứ n của dãy. Ví dụ, trong dãy số (1.1) ta có a1 = 1, a2 = 2, a3 = 4, ... Kí hiệu {an } hoặc {an }∞n=1 viết gọn cho dãy a1 , a2 , a3 , .... Thỉnh thoảng, chỉ số của các số hạng sẽ được bắt đầu khác 1, ví dụ như {an }∞ n=0 nghĩa là a0 , a1 , a2 , ... (trong đó an là số hạng thứ n + 1 của dãy số). Dãy số có thể được xác định bằng công thức của an , nghĩa là an được biểu thị bằng một hàm số của n. Ví dụ, dãy số (1.1) được xác định bằng công thức an = 2n−1 . Có một cách khác để cho dãy số là liệt kê một vài số hạng đầu và một quy tắc để tính toán các số hạng còn lại của dãy. Ví dụ, dãy (1.1) có thể được xác định bằng cách cho số hạng đầu a1 = 1 và quy tắc an+1 = 2an
4 với những số nguyên n ≥ 1. Khi đó ta có a2 = 2.a1 = 2.1 = 2 a3 = 2.a2 = 2.2 = 4 a4 = 2.a3 = 2.4 = 8. Quy tắc cho ta tính số hạng tiếp theo dựa vào các số hạng trước đó được gọi là quan hệ hồi quy hay gọi tắt là hồi quy. Định nghĩa 1.1.1. Một dãy {an } được gọi là thỏa mãn quan hệ hồi quy tuyến tính với các hệ số ck , ck−1 , ..., c0 nếu ck an+k + ck−1 an+k−1 + ... + c1 an+1 + c0 an = 0 (1.2) được thỏa mãn với mọi số nguyên n ≥ 1. Số nguyên k được gọi là bậc của quan hệ hồi quy tuyến tính. Dãy hồi quy tuyến tính là một dãy số a1 , a2 , a3 , ... thỏa mãn một quan hệ hồi quy tuyến tính như trên với ck 6= 0 và c0 6= 0. Ví dụ, dãy số (1.1) thỏa mãn quan hệ an+1 = 2an , với mọi số nguyên n ≥ 1 nên nó là một dãy hồi quy tuyến tính bậc 1 với c1 = 1 và c0 = −2. Định nghĩa 1.1.2. Quan hệ hồi quy tuyến tính ck an+k + ck−1 an+k−1 + ... + c1 an+1 + c0 an = 0 có đa thức hồi quy tuyến tính đặc trưng là đa thức ck xk + ck−1 xk−1 + ... + c1 x + c0 . Ví dụ, dãy số (1.1) có quan hệ hồi quy là an+1 − 2an = 0 nên có đa thức đặc trưng là x − 2 Cùng một dãy số có thể thỏa mãn nhiều quan hệ hồi quy tuyến tính khác nhau. Ví dụ, dãy (1.1) còn thỏa mãn quan hệ 2.an+1 − 4.an = 0, đa thức đặc trưng tương ứng là 2x − 4. Nó cũng thỏa mãn an+2 − 3an+1 + 2an = 0 nên cũng có đa thức đặc trưng là x2 − 3x + 2 = (x − 1) (x − 2).
5 Bây giờ, ta xét một dãy {an } tùy ý. Cho I là tập hợp các đa thức đặc trưng của tất cả các quan hệ hồi quy tuyến tính thỏa mãn bởi dãy {an }. Khi đó (a) Nếu f (x) ∈ I và g (x) ∈ I thì f (x) + g (x) ∈ I (b) Nếu f (x) ∈ I và h (x) là một đa thức bất kì, thì h (x) f (x) ∈ I. Một tập con khác rỗng I các đa thức, thoả mãn hai quan hệ trên được gọi là một iđêan. Một sự kiện trong đại số: Giả sử I là một iđêan của các đa thức. Khi đó I = {0} hoặc có một đa thức monic duy nhất f (x) ∈ I sao cho I = {h (x) .f (x)} trong đó h (x) là đa thức. (Một đa thức được gọi là monic nếu hệ số của lũy thừa cao nhất của x bằng 1) Áp dụng cho Iđêan của các đa thức đặc trưng của một dãy hồi quy tuyến tính {an },ta thấy luôn tồn tại một đa thức đặc trưng tối thiểu là đa thức monic có bậc thấp nhất trong I. Đây là đa thức đặc trưng của quan hệ tuyến tính không tầm thường bậc thấp nhất được thỏa mãn bởi {an }. Đa thức đặc trưng của bất kì quan hệ tuyến tính nào khác được thỏa mãn bởi {an } là đa thức bội của f (x). Bậc của dãy hồi quy tuyến tính {an } là bậc thấp nhất trong số tất cả các quan hệ hồi quy tuyến tính (có nghiệm không tầm thường) được thỏa mãn bởi {an }, nó cũng bằng bậc của đa thức đặc trưng tối thiểu. Ví dụ, dãy (1.1) là dãy hồi quy tuyến tính bậc nhất có đa thức đặc trưng tối thiểu là x − 2. 1.2 Nghiệm của quan hệ hồi quy Định nghĩa 1.2.1. Một dãy {an } thỏa mãn quan hệ hồi quy nào đó được gọi là một nghiệm của quan hệ đó. Nếu quan hệ hồi quy bậc k thì k giá trị đầu của dãy có thể lấy tùy ý, các giá trị tiếp theo hoàn toàn được xác định.
6 Một nghiệm của quan hệ hồi quy bậc k được gọi là nghiệm tổng quát nếu nó phụ thuộc k hằng số tùy ý C1 , ..., Ck . Ví dụ 1.2.1. Xét quan hệ hồi quy an+2 − 5an+1 + 6an = 0 có nghiệm tổng quát là an = C1 .2n + C2 .3n Sau đây là một số phương pháp tìm nghiệm của quan hệ hồi quy tuyến tính. Trước tiên, ta xét trường hợp đơn giản quan hệ hồi quy tuyến tính bậc 2: an+2 = c1 an+1 + c0 an (1.3) (1) (2) Bổ đề 1.2.1. Nếu an , an là các nghiệm của (1.3) thì với các số tùy ý A, B dãy an = Aa(1) n + Ban (2) cũng là nghiệm của (1.3). Chứng minh. Theo giả thiết ta có (1) (1) (1) an+2 = c1 an+1 + c0 an (2) (2) (2) an+2 = c1 an+1 + c0 an Từ đó suy ra h i h i (1) (2) (1) (1) Aan+2 + Ban+2 = c1 Aan+1 + Ban+1 + c0 Aa(1) n + Ba(1) n (1) (2) Như vậy, an = Aan + Ban cũng là một nghiệm của (1.3) Bổ đề 1.2.2. Giả sử r1 là nghiệm của phương trình đặc trưng r2 = c1 r + c0 (1.4) Khi đó dãy {r1n } là một nghiệm của quan hệ (1.3) Chứng minh. Ta có an = r1n , an+1 = r1n+1 , an+2 = r1n+2 . Thay vào quan hệ (1.3) ta được r1n+2 = c1 r1n+1 + c0 r1n Đẳng thức này đúng vì r2 = c1 r + c0 .
7 Nhận xét. Dãy r1n+m với m tùy ý cũng là một nghiệm của quan hệ hồi quy (1.3). Từ các bổ đề trên ta có định lí sau: Định lí 1.2.1. Giả sử cho quan hệ hồi quy an+2 = c1 an+1 + c0 an Giả sử phương trình đặc trưng r2 = c1 r + c0 Có hai nghiệm phân biệt r1 và r2 . Khi đó, nghiệm tổng quát của quan hệ hồi quy này có dạng an = Ar1n + Br2n (1) (2) Chứng minh. Theo bổ đề 1.2.2, an = r1n , an = r2n là các nghiệm của quan hệ đang xét. Theo bổ đề 1.2.1, với mọi A, B tùy ý, Ar1n + Br2n là nghiệm của quan hệ hồi quy trên. Chỉ còn phải chứng minh rằng, nghiệm tùy ý của quan hệ này có thể viết dưới dạng đã nêu trong định lí. Mỗi nghiệm của quan hệ trên được xác định duy nhất bởi các giá trị a0 , a1 . Vì thế ta chỉ cần chỉ ra rằng, hệ phương trình ( A+B =a Br1 + Ar2 = b có nghiệm với a, b tùy ý. Dễ thấy các nghiệm đó là b − ar2 ar1 − b A= , B= r1 − r2 r1 − r2 Bây giờ ta chuyển sang xét trường hợp phương trình đặc trưng có nghiệm bội. Giả sử phương trình đặc trưng của quan hệ đã cho có các nghiệm trùng nhau, chẳng hạn r1 = r2 . Khi đó, biểu thức Ar1n−1 + Br2n−1 không còn là nghiệm tổng quát nữa, vì nghiệm đó được viết dưới dạng an = Cr1n−1 . Nói chung không thể chọn hằng số C sao cho hai điều kiện ban đầu a0 = a, a1 = b được thỏa mãn.
8 Định lí 1.2.2. Giả sử phương trình đặc trưng r2 = c1 r + c0 có nghiệm bội r1 . Khi đó nghiệm tổng quát của quan hệ đang xét có dạng an = r1n (A + Bn) trong đó A, B là các hằng số tùy ý. Chứng minh. Vì phương trình đặc trưng có nghiệm bội r − 1 nên theo định lí Vi-ét ta có: c1 = 2r1 , c0 = −r12 . Ta viết phương trình đặc trưng dưới dạng r2 = 2r1 r − r12 . Như vậy quan hệ hồi quy sẽ có dạng an+2 = 2r1 an+1 − r12 an (2) Ta thử lại rằng an = nr1n là một nghiệm của quan hệ đang xét. Ta có: an+2 = (n + 2)r1n+2 , an+1 = (n + 1)r1n+1 . Thay các giá trị này vào quan hệ trên ta được (n + 2)r1n+2 = 2(n + 1)r1n+2 − nr1n+2 . Vậy nr1n đúng là một nghiệm. Theo bổ đề 1.2.1, với A, B là các hằng số tùy ý, ta có an = r1n (A + Bn) cũng là nghiệm. Mặt khác, với điều kiện a0 = a, a1 = b tùy ý, ta luôn xác định được A, B sao cho an = r1n (A + Bn) là một nghiệm của quan hệ đang xét. Vậy an = r1n (A + Bn) cho ta công thức nghiệm tổng quát trong trường hợp phương trình đặc trưng có nghiệm bội.
9 Đối với quan hệ hồi quy tuyến tính cấp k tùy ý, ta cũng có kết quả hoàn toàn tương tự. Định lí 1.2.3. Cho f (x) = ck xk + ... + c0 là một đa thức với ck 6= 0 và c0 6= 0. Giả sử phân tích của f (x) trên tập các số phức là f (x) = ck (x − r1 )m1 (x − r2 )m2 ....(x − r` )m` trong đó r1 , r2 , ..., r` là các số phức khác 0 phân biệt, m1 , m2 , ..., m` là các số nguyên. Khi đó dãy {an } thỏa mãn quan hệ hồi quy tuyến tính có đa thức đặc trưng là f (x) khi và chỉ khi tồn tại các đa thức g1 (n) , g2 (n) , ..., g` (n) với deg gi ≤ mi − 1 sao cho an = g1 (n) r1n + ... + g` (n) r`n với mọi n. Dưới đây là một trường hợp đặc biệt quan trọng Hệ quả 1.2.1. Giả sử f (x) = c1 (x − r1 ) (x − r2 ) ... (x − r` ), trong đó r1 , r2 , ..., r` là các nghiệm phức khác 0 phân biệt của f (x). Khi đó dãy {an } thỏa mãn quan hệ hồi quy tuyến tính có đa thức đặc trưng là f (x) khi và chỉ khi tồn tại các hằng số B1 , B2 , ..., B` sao cho an = B1 r1n + B2 r2n + ... + B` r`n với mọi n. Ví dụ 1.2.2. Xét quan hệ hồi quy an+3 = 9an+2 − 26an+1 + 24an Phương trình đặc trưng có dạng r3 − 9r2 + 26r − 24 = 0 Các nghiệm của phương trình đặc trưng là r1 = 2, r2 = 4, r3 = 3. Vậy nghiệm tổng quát của quan hệ hồi quy này là an = A2n + B4n + C3n
10 1.3 Quan hệ hồi quy không thuần nhất Giả sử ta muốn tìm một công thức cụ thể đối với một dãy {an } thỏa mãn a0 = 1 và an+1 − 2an = bn với n ≥ 0 (1.5) trong đó {bn } là dãy hồi quy tuyến tính thỏa mãn b0 = 2 và bn+1 = 3bn . Đây không phải là một quan hệ hồi quy tuyến tính theo nghĩa mà chúng ta đã đề cập (vì vế phải là bn chứ không phải là 0) do vậy phương pháp thông thường không sử dụng được. Quan hệ hồi quy dạng này, tuyến tính trừ một hàm của n ở vế phải, được gọi là quan hệ hồi quy không thuần nhất. Chúng ta có thể giải được các bài toán hồi quy không thuần nhất một cách rõ ràng khi vế phải là một dãy hồi quy tuyến tính. Trong ví dụ trên, {an } cũng thỏa mãn an+2 − 2an+1 = bn+1 . Từ đó, ta có an+2 − 5an+1 + 6an = bn+1 − 3bn = 0. Do đó {an } là một dãy hồi quy tuyến tính. Đa thức đặc trưng của quan hệ này là x2 − 5x + 6 = (x − 2) (x − 3) do đó tồn tại các hằng số A, B để an = A.2n + B.3n Do a0 = 1, a1 = 4 nên ta có ( ( A+B =1 A = −1 ⇒ 2A + 3B = 4 B=2 Vậy an = −2n + 2.3n hay an = −2n + bn .
11 Nếu một dãy {xn } bất kì thỏa mãn quan hệ xn+1 − 2xn = bn (1.6) Ta có dãy {yn } xác định bởi yn = xn − an thỏa mãn yn+1 − 2yn = 0, với mọi n. Do vậy yn = C.2n với một số C nào đó. Do đó nghiệm tổng quát của (1.6) là xn = yn + an = −2n + bn + C.2n hay xn = D.2n + bn trong đó D là hằng số nào đó. Nói chung loại lập luận này chứng minh điều sau đây Định lí 1.3.1. Cho {bn } là một dãy hồi quy tuyến tính thỏa mãn quan hệ hồi quy với đa thức đặc trưng f (x). Cho g (x) = ck xk + ck−1 xk−1 + ... + c1 x + c0 là một đa thức. Khi đó mỗi nghiệm {xn } của quan hệ hồi quy không thuần nhất ck xn+k + ck−1 xn+k−1 + ... + c1 xn+1 + c0 xn = bn (1.7) cũng thỏa mãn một quan hệ hồi quy tuyến tính với đa thức đặc trưng f (x) g (x). Hơn nữa nếu {an } là một nghiệm cụ thể của quan hệ (1.7) thì tất cả các nghiệm có dạng xn = an + yn , trong đó {yn } là một trong các nghiệm của quan hệ tuyến tính ck yn+k + ck−1 yn+k−1 + ... + c1 yn+1 + c0 yn+0 = 0 1.4 Định lí Mahler-Lech Đây là một định lí sâu sắc về các dãy hồi quy tuyến tính Định lí 1.4.1. Cho {an } là một dãy hồi quy tuyến tính của các số phức, và cho c là một số phức. Thế thì tồn tại một dãy hữu hạn (có thể rỗng)
12 các cấp số cộng T1 , T2 , ..., Tm và tập S hữu hạn (có thể rỗng) các số nguyên sao cho {n | an = c} = S ∪ T1 ∪ T2 ∪ ... ∪ Tm Sau đây là một vài ví dụ minh họa định lí Mahler-Lech Ví dụ 1.4.1. Cho dãy hồi quy tuyến tính {an } thỏa mãn a0 = 0, a1 = 1 và an = an−2 với mọi n ≥ 2. Khi đó, dễ dàng tìm được 1 1 an = − (−1)n . 2 2 Nếu n chẵn thì an = 0 với mọi n ≥ 0 Nếu n lẻ thì an = 1 với mọi n ≥ 1 Gọi T là cấp số cộng thỏa mãn T = {0, 2, 4, 6, ...} , ta có {n |an = 0} = ∅ ∪ T. Ví dụ 1.4.2. Cho dãy hồi quy tuyến tính {an } thỏa mãn a1 = a2 = a3 = 1, a4 = 3 và an+4 = 3an+2 − 2an với mọi n ≥ 1. Xét đa thức đặc trưng x4 − 3x2 + 2 √ √ có các nghiệm là 1, −1, 2, − 2. Vậy, nghiệm tổng quát của quan hệ hồi quy trên là n n √ n √ n an = A.1 + B.(−1) + C. 2 + D. − 2 Do a1 = a2 = a3 = 1, a4 = 3 nên ta tìm được 1 √ n 1 √ n n an = −(−1) + . 2 + . − 2 . 2 2
13 Nếu n lẻ, thì an = 1 √ n Nếu n chẵn, thì an = −1 + 2 > 1, với mọi n ≥ 4. Gọi T là cấp số cộng thỏa mãn T = {1, 3, 5, 7, ...} , S = {2} , thì {n |an = 1} = S ∪ T.
14 Chương 2 Số Euler và đa thức Lucas suy rộng 2.1 Hàm Euler và dãy Fibonacci 2.1.1 Hàm Euler Định nghĩa 2.1.1. Giả sử n là một số nguyên dương. Hàm Euler được định nghĩa là số các số nguyên dương không vượt quá n và nguyên tố cùng nhau với n. Kí hiệu hàm Euler là ϕ(n). Ví dụ 2.1.1. ϕ(1) = 1, ϕ(2) = 1, ϕ(3) = 2, ϕ(4) = 2. Ta nhắc lại về hệ thặng dư. Hệ thặng dư đầy đủ môđunlô n là tập hợp gồm n số nguyên trong đó không có hai số đồng dư nhau môđunlô n. Ví dụ. {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} và {1, 2, −7, 4, 5, 6, 7, 8, 9, 10} là hai hệ thặng dư đầy đủ môđunlô 10. Hệ thặng dư thu gọn môđunlô n là tập hợp gồm ϕ(n) số nguyên, trong đó mỗi số đều nguyên tố cùng nhau với n và không có hai số đồng dư nhau môđunlô n. Ví dụ. {1, 3, 7, 9} là hệ thặng dư thu gọn môđunlô 10. Thặng dư dương bé nhất của X môđunlô n là số a với 0 < a < n và X ≡ a (mod n). Ví dụ. Số 23 có thặng dư dương bé nhất môđunlô 10 là 3. Ta có một số định lí quan trọng về hàm Euler trong số học.
15 Định lí 2.1.1. Giả sử r1 , r2 , ..., rϕ(n) là hệ thặng dư thu gọn môđunlô n, a là số nguyên dương và (a, n) = 1. Khi đó tập hợp ar1 , ar2 , ..., arϕ(n) cũng là hệ thặng dư thu gọn môđunlô n. Chứng minh. Rõ ràng hệ ar1 , ar2 , ..., arϕ(n) gồm ϕ(n) phần tử. Lấy 0 < i 6= j ≤ ϕ(n), ta sẽ chứng minh ari không đồng dư arj môđunlô n. Giả sử ngược lại ari ≡ arj (mod n). Nên a(ri − rj ) ≡ 0 (mod n), . mà (a, n) = 1 suy ra ri − rj ..n hay ri ≡ rj (mod n), điều này mâu thuẫn với giả thiết hệ r1 , r2 , ..., rϕ(n) là hệ thặng dư thu gọn môđunlô n. Vậy ari không đồng dư arj môđunlô n. Ta cần chứng minh (ari , n) = 1 với mọi n = 1, 2, ..., ϕ (n). Giả sử ngược lại, (ari , n) = d > 1 . Khi đó sẽ tồn tại ước nguyên tố p của d. Suy ra p |ari và p| n. Tức là p là ước chung của a và n hoặc p là ước chung của ri và n, mà cả hai điều này đều mâu thuẫn với giả thiết (a, n) = 1 và (ri , n) = 1. Vậy (ari , n) = 1 . Từ đó suy ra hệ ar1 , ar2 , ..., arϕ(n) cũng là hệ thặng dư thu gọn môđunlô n. Ví dụ 2.1.2. {1, 3, 7, 9} là hệ thặng dư thu gọn môđunlô 10, do (3, 10) = 1 nên {3, 9, 21, 27} cũng là hệ thặng dư thu gọn môđunlô 10. Định lí 2.1.2. (Định lí Euler) Giả sử n là số nguyên dương, a là số nguyên và (a, n) = 1. Khi đó aϕ(n) ≡ 1 (mod n). Chứng minh. Gọi r1 , r2 , ..., rϕ(n) là hệ thặng dư thu gọn môđunlô n gồm các số nguyên dương không vượt quá n. Vì (a, n) = 1 nên ar1 , ar2 , ..., arϕ(n) cũng là hệ thặng dư thu gọn môđunlô n. Ta có các thặng dư dương bé
16 nhất của ar1 , ar2 , ..., arϕ(n) là r1 , r2 , ..., rϕ(n) theo một thứ tự nào đó. Nên ta có ar1 .r2 ...arϕ(n) ≡ r1 .r2 ...rϕ(n) (mod n). Hay aϕ(n) r1 .r2 ...rϕ(n) ≡ r1 .r2 ...rϕ(n) (mod n). Do đó r1 .r2 ...rϕ(n) (aϕ(n) − 1) ≡ 0 (mod n). Vì r1 , r2 , ..., rϕ(n) là hệ thặng dư thu gọn môđunlô n nên (r1 .r2 ...rϕ(n) , n) = 1. Suy ra aϕ(n) ≡ 1 (mod n). Ví dụ 2.1.3. Vì 5ϕ(8) ≡ 1(mod8) nên 5.5ϕ(8)−1 ≡ 1(mod8) hay 5.125 ≡ 1(mod8) do đó số nghịch đảo của 5 môđunlô 8 là 125. Định lí 2.1.3. Với p là số nguyên tố ta có ϕ(p) = p − 1. Ngược lại, nếu p là số nguyên dương sao cho ϕ(p) = p − 1 thì p là số nguyên tố. Chứng minh. Nếu p là số nguyên tố thì mọi số nguyên dương nhỏ hơn p đều nguyên tố cùng nhau với p, như vậy ϕ(p) = p − 1. Ngược lại, nếu p là số nguyên dương thỏa mãn ϕ(p) = p − 1, ta chứng minh p là số nguyên tố. Giả sử ngược lại p là hợp số, khi đó tồn tại số nguyên dương d là ước của p, tức là 0 < d < p và d |p. Vậy trong các số 1, 2, ..., p − 1 phải có những số không nguyên tố cùng nhau với p. Vậy ϕ(p) ≤ p − 2, điều này mâu thuẫn với giả thiết ϕ(p) = p − 1. Vậy p là số nguyên tố. Định lí 2.1.4. Giả sử p là số nguyên tố, a là số nguyên dương. Khi đó ϕ(pa ) = pa − pa−1 . Chứng minh. Vì p là số nguyên tố nên các số nguyên dương không vượt quá pa , không nguyên tố cùng nhau với p là những số nguyên dương k
17 . thỏa mãn p ≤ k ≤ pa−1 và k ..p. Có đúng pa−1 số như vậy. Vậy có pa −pa−1 số nguyên dương không vượt quá pa và nguyên tố cùng nhau với p. Vậy ϕ(pa ) = pa − pa−1 . Ví dụ 2.1.4. ϕ(81) = ϕ(34 ) = 34 − 33 = 54. Định lí 2.1.5. Nếu m, n là các số nguyên dương nguyên tố cùng nhau Khi đó ϕ(m.n) = ϕ(m).ϕ(n). Chứng minh. Ta viết các số nguyên dương không vượt quá m.n thành bảng sau 1 m+1 2m + 1 ... (n − 1) m + 1 2 m+2 2m + 2 ... (n − 1) m + 2 3 m+3 2m + 3 ... (n − 1) m + 3 ... ... ... ... m 2m 3m ...n.m Giả sử r là số nguyên dương không vượt quá n,(r, m) = d > 1. Khi đó không có số nào trong dòng thứ r nguyên tố cùng nhau với m.n, vì mỗi phần tử trong dòng đó đều có dạng km + r với 1 ≤ k ≤ n − 1, d |m và d |r nên d |(km + r) và d |m.n do đó d |(km + r, m.n). Vậy, để tìm các số trong bảng nguyên tố cùng nhau với m.n ta chỉ cần xét các số trong dòng thứ r trong đó (r, m) = 1, có ϕ(m) dòng như thế. Ta xét một dòng như vậy, dòng này chứa các số r, m + r, 2m + r, ..., (n − 1)m + r, mà mỗi số này đều nguyên tố cùng nhau với n. Ta sẽ chứng minh các số trong dòng này lập thành một hệ thặng dư đầy đủ môđunlô n. Hệ trên gồm n số nguyên dương. Ta sẽ chứng minh không có hai số nào trong hệ đồng dư nhau môđunlô n. Giả sử ngược lại, với 0 ≤ i 6= j ≤ n − 1 mà im + r ≡ jm + r (mod n) ⇔ m(i − j) ≡ 0 (mod n).