Luận văn thạc sĩ phương trình nghiệm nguyên và hàm số học

MỘT SỐ KIẾN THỨC CƠ BẢN

Một số kết quả của số học trong giải phương trình nghiệm nguyên

Định lý 1.1.1 (Định lý cơ bản của số học).

Cho n là số nguyên dương lớn hơn 1 Khi đó n luôn có thể biểu diễn được một cách duy nhất dưới dạng sau: n

Trong toán học, k, α (i = 1, 2, , k) là các số tự nhiên và p i là các số nguyên tố với điều kiện 1 < p i < p 2 < < p k Theo Định lý Euclid (Định lý 1.1.2), có vô hạn số nguyên tố Định lý 1.1.3 chỉ ra rằng nếu a, b là hai số nguyên dương và p là một số nguyên tố sao cho ab ≡ p, thì phải có hoặc là a ≡ p, hoặc là b ≡ p Định nghĩa 1.1.1 cho biết rằng hai số nguyên a và b được coi là đồng dư nếu chúng thỏa mãn một điều kiện nhất định.

Modulo m (m nguyên dương) và ký hiệu a ≡ b (mod m) khi và chỉ khi (a - b) m.

Các tính chất cơ bản của đồng dƣ

Tính chất 1 Nếu a ≡ b (mod m) và c ≡ d (mod m) thì a + c ≡ b + d (mod m) và ac ≡ bd (mod m).

Nếu p là số nguyên tố và ab ≡ 0 (mod p), thì a ≡ 0 (mod p) hoặc b ≡ 0 (mod p) Định lý Fermat khẳng định rằng nếu p là một số nguyên tố và a là một số nguyên bất kỳ, thì (a^p - a) ≡ 0 (mod p).

Khi (a, p) = 1, thì a^(p-1) ≡ 1 (mod p) Theo Định lý Euler, nếu m là số nguyên dương và (a, m) = 1, thì a^φ(m) ≡ 1 (mod m), trong đó φ(m) là số các số nguyên dương nhỏ hơn m và nguyên tố cùng nhau với m.

( φ( m ) gọi là Phi-hàm Euler) Định lý 1.1.6 (Đinh lý Wilson). p là số nguyên tố khi và chỉ khi (p - 1)! + 1 chia hết cho p.

1 2 k i Định lý 1.1.7 (Đinh lý Fermat-Euler) Nếu p = 4k + 1, thì tồn tại các số nguyên dương a, b sao cho p = a 2 + b 2 Định lý 1.1 8 (Định lý phần dƣ Trung Hoa).

Giả sử r và s là hai số nguyên dương nguyên tố cùng nhau, và a, b là hai số nguyên bất kỳ Thì sẽ luôn tồn tại một số nguyên N thỏa mãn điều kiện N ≡ a (mod r) và N ≡ b (mod s).

Ngoài ra N đƣợc xác đinh một cách duy nhất.

Phương trình Điôphăng tuyến tính

Phương trình Điôphăng tuyến tính có dạng ax + by = c, trong đó a, b, c là các số nguyên và x, y cũng là các số nguyên Giải phương trình này có nghĩa là tìm các cặp số nguyên (x, y) thỏa mãn điều kiện trên Theo định lý 1.2.1, nếu a và b là các số nguyên và d là ước chung lớn nhất của a và b, thì phương trình ax + by = c sẽ không có nghiệm nguyên nếu d không chia hết cho c Ngược lại, nếu c chia hết cho d, phương trình sẽ có vô số nghiệm Hơn nữa, nếu (x₀, y₀) là một nghiệm cụ thể của phương trình, thì mọi nghiệm khác sẽ có dạng x = x₀.

Trong đó n là số nguyên.

Giả sử (x, y) là nghiệm của phương trình Do d|a, d|b nên d|c Như vậy, nếu d không là ước của c thì phương trình không có nghiệm nguyên.

Vì (a, b) = d nên tồn tại số nguyên t và s sao cho d = as + bt (2)

Cũng do d|c nên tồn tại e nguyên sao cho de = c Nhân hai vế của (2) với c ta đƣợc: c = de = (as + bt)e = a(se) + b(te).

Như vậy, ta có một nghiệm của phương trình cho bởi x = x0 = se, y = y0 = te.

Ta sẽ chứng minh tồn tại vô số nghiệm. Đặt x = x0 + b n, y = y0 - a n trong đó n nguyên. d d

Ta thấy cặp (x, y) xác định nhƣ trên là một nghiệm, vì: b ax + by = ax0 + a d n + by0 — b a n = ax0 + by0 = c d

Ta chỉ còn phải chứng minh rằng, mọi nghiệm của phương trình phải có dạng nêu trên.

Giả sử (x, y) là một nghiệm nguyên của phương trình ax + by = c Khi đó, từ phương trình (ax + by) - (ax0 + by0) = 0, ta suy ra a(x - x0) + b(y - y0) = 0, tức là a(x - x0) = -b(y - y0) Nếu chia hai vế của đẳng thức này cho d, ta sẽ có a(x - x0) / d = -b(y - y0) / d.

Từ đó suy ra y0 - y chia hết cho a

, tức là tồn tại n nguyên sao cho a n = y0 - y. d d

Thay giá trị này của y vào phương trình (3) ta được: x = x0 + b n. d Định lý trên giúp ta tìm được nghiệm của phương trình Điôphăng tuyến tính.

Phương trình Fermat

Bộ ba số nguyên dương (x, y, z) được gọi là bộ số Pitago nếu thỏa mãn phương trình x² + y² = z², dựa trên Định lý Pitago nổi tiếng Điều này có nghĩa là (x, y, z) là bộ số Pitago khi và chỉ khi tồn tại một tam giác vuông với hai cạnh góc vuông lần lượt là x và y, còn cạnh huyền là z, với x, y, z đều là các số nguyên dương.

Giả sử các bộ số (3, 4, 5), (6, 8, 10) là các bộ số Pitago.

Nếu (x, y, z) là bộ số Pitago, thì (kx, ky, kz) cũng là bộ số Pitago với mọi số tự nhiên k Vì vậy, chúng ta chỉ cần xem xét các bộ ba số nguyên tố cùng nhau Định nghĩa 1.3.1: Bộ số Pitago (x, y, z) được gọi là nguyên thủy nếu.

Ví dụ 1.3.1 Các bộ số (3, 4, 5), (5, 12, 13) là nguyên thủy, bộ số (6, 8, 10) không nguyên thủy.

Nếu bộ ba số (x, y, z) không phải là nguyên thủy, tức là (x, y, z) = d, thì bộ ba (x, d, d) sẽ tạo thành một bộ số Pitago nguyên thủy Để xác định bộ số Pitago nguyên thủy, chúng ta áp dụng Bổ đề sau đây.

Bổ đề 1.3.1 Nếu (x, y, z) là một bộ Pitago nguyên thủy thì (x, y) = (y, z) = (z, x) = 1 (ký hiệu (x, y, z, ) = d đƣợc hiểu là ƢCLN của các số x, y, z….)

Giả sử (x, y, z) là một bộ số Pitago nguyên thủy với (x, y) > 1, tồn tại một số nguyên p sao cho p chia hết cho cả x và y Do đó, p cũng chia hết cho z², dẫn đến p chia hết cho z Điều này mâu thuẫn với giả thiết rằng (x, y, z) là bộ số nguyên thủy.

Bổ đề 1.3.2 Giả sử (x, y, z) là bộ số Pitago nguyên thủy Khi đó x chẵn, y lẻ hoặc x lẻ, y chẵn.

Giả sử (x, y, z) là một bộ Pitago nguyên thủy Do Bổ đề 1.3.2

(x, y) = 1, nên x và y không thể cùng chẵn Nếu x, y cùng lẻ thì ta có: x 2 ≡ y 2 ≡ 1 (mod 4)

Nên z 2 = x 2 + y 2 ≡ 2 (mod 4) Điều đó vô lý Vậy x và y không cùng tính chẵn lẻ.

Bổ đề 1.3.3 Giả sử r, s, t là các số nguyên dương sao cho (r, s) = 1 và rs = t 2 Khi đó tồn tại các số nguyên h, l sao cho r = l 2 và s = h 2

Nếu r = 1 hoặc s = 1 thì Bổ đề là hiển nhiên.

Ta giả sử r > 1 và s > 1 Giả sử các phân tích r, s, t ra thừa số nguyên tố ta đƣợc các dạng sau r = p α1 pα 2 p αn s = p α n + 1 p α n + 2 p α m t = q β1 pβ 2 p βk

Vì (r, s) = 1 nên các số nguyên tố xuất hiện trong phân tích của r và s là khác nhau Do r.s = t 2 nên p α1 p α2 p αn p α n +1 p α n+2 p α m = q 2β1 q 2β2 q 2βk

Từ Định lý cơ bản của Số học, ta có thể suy ra rằng các lũy thừa nguyên tố trong hai vế của đẳng thức phải giống nhau Điều này dẫn đến việc mỗi p_i phải tương ứng với một q_j nào đó, và đồng thời α phải bằng β Do đó, mỗi số mũ α đều phải là số chẵn, từ đó suy ra rằng i là số nguyên Kết quả là r = l^2 và s = h^2, trong đó l và h là các số nguyên, biểu diễn dưới dạng 2^α1 * 2^α2 * * 2^αn = 2.

Định lý 1.3.1 mô tả cách tạo ra các bộ số Pitago nguyên thủy (x, y, z) với y là số chẵn Cụ thể, tồn tại các số nguyên dương m và n, với m > n, m là số lẻ và n là số chẵn, hoặc ngược lại, sao cho: x = m² – n², y = 2mn, và z = m² + n² Điều này chỉ xảy ra khi m và n là các số nguyên dương nguyên tố cùng nhau.

Giả sử x, y, z là một bộ số Pitago nguyên thủy Từ Bổ đề 1.3.2 cho thấy x lẻ, y chẵn, hoặc ngƣợc lại Vì ta giả thiết y chẵn nên x, z đều lẻ.

Do x + z và z - x đều là số chẵn, nên các số x + z

Ta để ý rằng (r, s) = 1 Thật vậy, nếu (r, s) = d thì do d|r, d|s nên d|(r + s) = z và

4rs 4m 2 n 2 d|(r - s) = x Điều đó có nghĩa là d|(z, x) = 1 nên d =1. Áp dụng Bổ đề 1.3.3 ta thấy rằng tồn tại các số nguyên m, n sao cho r = m 2 , s n 2 Viết x, y, z thông qua m, n ta có x = r - s = m 2 – n 2 ; y = = = 2mn ; z = r +s = m 2 + n 2

Nếu (m, n) = 1, thì mọi ước chung của m và n cũng là ước của x = m² - n², y = 2mn, z = m² + n², do đó x, y, z cũng có ước chung là (x, y, z) Vì x, y, z nguyên tố cùng nhau, nên (m, n) = 1 Hơn nữa, m và n không thể đều là số lẻ, do đó một trong hai số phải là chẵn và số kia là lẻ Do đó, mỗi bộ số Pythagore nguyên thủy sẽ có dạng như đã nêu Điều này chứng tỏ rằng bộ ba số x² = m² - n²; y = 2mn; z = m² + n² là đúng.

Trong đó m, n là các số nguyên dương, m > n, (m, n) = 1, m khác n và m không đồng dư n (mod 2) lập thành một bộ số Pitago nguyên thủy, trước tiên ta nhận xét rằng x2 + y2 = ( m 2 − n 2 ) 2 + ( 2mn ) 2

Ta chứng minh rằng x, y, z là các nguyên tố cùng nhau Giả sử ngược lại, tức là (x, y, z) = d > 1 Khi đó, tồn tại một số nguyên tố p sao cho p chia hết cho (x, y, z) Tuy nhiên, p không chia hết cho 2 vì x là số lẻ (do x = m² - n², trong đó m² và n² không cùng chẵn lẻ) Hơn nữa, vì p chia hết cho x và z, nên p cũng chia hết cho (z + x) = 2m² và (z - x) = 2n².

Vậy p | m và p | n: Mâu thuẫn với (m, n) = 1.

Do đó (x, y, z) = 1 tức là (x, y, z) là một bộ số Pitago nguyên thủy.

Ví dụ 1.3.2 Lấy m = 5, n = 2 ta tìm đƣợc x = 21, y = 20, z = 29 là một bộ số Pitago nguyên thủy.

Ta thấy rằng phương trình x + y = z

Có vô hạn nghiệm nguyên (x, y, z) Các bộ số Pitago cũng cho ta vô hạn nghiệm nguyên của phương trình x 2 + y 2 = z 2

Nếu số mũ của các biến trong phương trình x^n + y^n = z^n tăng lên với n > 3, thì liệu có tồn tại nghiệm nguyên hay không? Nếu có, số nghiệm đó là hữu hạn hay vô hạn? Đây là câu hỏi liên quan đến Định lý Fermat, một trong những định lý nổi tiếng trong toán học.

Phương trình x⁴ + y⁴ = z⁴ không có nghiệm nguyên x, y, z khác 0, khi n = 4, là một trường hợp đặc biệt của Định lý lớn Fermat Định lý này, được chứng minh bởi A Wiles vào năm 1993, sử dụng các kiến thức cao cấp từ nhiều lĩnh vực toán học khác nhau Phương pháp lùi vô hạn mà Fermat đề xuất là một trong những mấu chốt quan trọng trong việc chứng minh định lý này.

Giả sử phương trình trên có nghiệm nguyên dương x, y, z khác 0 Do có thể thay đổi biến bằng số đối của nó, ta có thể coi x, y, z là các số nguyên dương.

Ta giả thiết (x, y) = 1 Thật vậy, nếu (x, y) = d thì x = d x1 , y = dy1, trong đó x1, y1 là các số nguyên dương.

Ta sẽ chỉ ra phương trình x 4 + y 4 = z 2 không có nghiệm nguyên dương vì vậy phương trình x 4 + y 4 = z 4 cũng không có nghiệm nguyên dương.

Vậy d 4 |z 2 , suy ra d 2 | z, nghĩa là z = d 2 z1 với z1 là số nguyên dương.

Ta nhận đƣợc nghiệm x 4 + y 4 = z 2 với các số nguyên dương x = x1, y = y1, z = z1, trong đó (x1, y1) = 1.

Bây giờ ta giả sử x = xo, y = yo, z = z0 là nghiệm của phương trình x 4 + y 4 = z 2 , trong đó (xo, yo) = 1.

Ta sẽ chỉ ra tồn tại nghiệm khác gồm các số nguyên dương x = x1, y = y1, z = z1 với (x1, y1) = 1 sao cho z1 < z0.

Vì x 4 + y 4 = z 2 nên ( x 2 ) 2 + ( y 2 ) 2 = z 2 tức là , z y 2 , ) 2, nguyênlà một bộ số Pitago Hơn nữa y 2 ) = 1, vì nếu p là số (

( x 0 0 0 x 0 0 tố, p | 2 , p| 2 , y 2, z y2 thì p|x , p|y , mâu thuẫn với (x , y ) = 1 Nhƣ vậy là một bộ x 0 0 o o o o x 0 0 0 số Pitago nguyên thủy, tồn tại các số nguyên dương m, n với (m, n) 1, m không đồng dƣ với n (mod 2) và x 2 = m 2 − n 2

Trong đó có thể xem 2 là số chẵn (nếu cần thì đổi ký

Từ đẳng thức của x 2 ta đƣợc: x 2 + n 2 = m 2

Do (m, n) = 1 nên (xo, n, m) là một bộ số Pitago nguyên thủy Tồn tại các số nguyên dương r, s với (r, s) = 1, r không đồng dư với s (mod 2) và

Vì m lẻ và (m, n) = 1, ta có (m, 2n) = 1 Do = (2n)m nên tồn tại các số nguyên

0 dương zl và w với m = z 2 , 2n = w 2 Vì w chẵn, w = 2u, trong đó u là số nguyên dương, nên u 2 = n

Do (r, s) = 1, tồn tại các số nguyên dương xl; y l sao cho r = x 2 , s = y2

Chú ý rằng vì (r, s) = 1 nên dễ suy ra (x1, y1) = 1 Nhƣ vậy, x4 1 + y41 = z21 , trong đó x1, y1, zl là các số nguyên dương với (xl, yl) = 1 Hơn nữa, ta có zl < z0 vì zl ≤ z41 = m 2

< m 2 + n 2 = z0 Để kết thúc chứng minh định lý, giả sử x 4 + y 4 = z 4 có ít nhất một nghiệm nguyên.

Do nguyên lý sắp thứ tự tốt, tồn tại nghiệm nguyên dương với giá trị z0 nhỏ nhất Tuy nhiên, từ nghiệm này, ta có thể tìm ra nghiệm khác có giá trị z nhỏ hơn, dẫn đến mâu thuẫn.

Nhƣ vậy ta đã đƣợc điều phải chứng minh.

* Về Định lý lớn Fermat

Có rất nhiều bộ ba số nguyên dương thỏa mãn phương trình x² + y² = z² Tuy nhiên, câu hỏi đặt ra là liệu có tồn tại bộ ba số nguyên dương nào thỏa mãn phương trình x³ + y³ = z³ hay không?

Vào năm 1637, nhà toán học Pháp Fermat (Pierre de Fermat, 1601 - 1665) đã nêu lên mệnh đề sau, đƣợc gọi là định lý lớn Fermat:

Phương trình x n + y n = z n (với n là số nguyên lớn hơn 2) không có nghiệm nguyên dương.

Fermat đã ghi chú trong cuốn Số học của Điôphăng rằng không thể phân tích một lập phương thành tổng của hai lập phương, cũng như không thể phân tích một trùng phương thành tổng của hai trùng phương, và điều này áp dụng cho bất kỳ lũy thừa nào lớn hơn 2 Ông khẳng định đã tìm ra cách chứng minh cho mệnh đề này, nhưng không đủ chỗ trên lề sách để ghi lại.

Năm 1670, 5 năm sau khi Fermat mất, con trai ông đã công bố mệnh đề này.

Lịch sử chứng minh Định lý lớn Fermat

Chứng minh của Fermat với n = 4 đã được tìm thấy, nhưng vẫn còn nhiều câu hỏi về cách ông đã giải quyết bài toán tổng quát Điều này đặt ra nghi vấn liệu lời giải của ông có tồn tại sai sót hay không.

MỘT SỐ DẠNG PHƯƠNG TRÌNH NGHIÊM NGUYÊN

Các bài toán về phương trình nghiệm nguyên

A Các ví dụ mình họa cho phương trình nghiệm nguyên sử dụng chia hết để giải Dang 1: Phương pháp đưa về phương trình tích

Ví dụ 2.2.1 Giải phương trình nghiệm nguyên sau:

Vậy nghiệm của phương trình là:

Ví dụ 2.2.2 Giải phương trình nghiệm nguyên sau:

Ví dụ 2.2.3 Giải phương trình nghiệm nguyên sau: x 2 + x + 6 = y 2

Vậy nghiệm nguyên của phương trình là: (x; y) = (5; -6); (-6; -6); (5; 6); (-6; 6);

Ví dụ 2.2.4 Giải phương trình nghiệm nguyên sau: x 2 + 2y 2 + 3xy – x - y + 3 = 0

Vậy nghiệm nguyên của phương trình là: (x; y) = (-8; 5); (-6; 5); (4; -3); (6; -3);

Ví dụ 2.2.5 (Đề tuyển sinh vào lớp 10 trường THPT Chuyên HN- Amsterdam 2014)

Giải phương trình nghiệm nguyên sau: x 2 y + xy – 2x 2 – 3x + 4 = 0

Làm tương tự như ví dụ trên, lập bảng và giải ra ta được nghiệm:

Các bài tập tương tự: a) xy + 3x – 2y = 11 b) x 2 – 4xy + 5y 2 = 169 c) x 2 + 7x = y 2 d) x 3 – y 3 = 91 e) x(x +1)(x +7)(x +8) = y 2 f) x 3 + y 3 + z 3 = 3xyz +1

Các bài tập tự ra: Giải các phương trình nghiệm nguyên sau: a) 4x + xy + 3y = 5 b) 6x 2 + 5xy – y 2 – 7 = 0 c) 3x 2 +2x + 2 = 3y 2

Dang 2: Phương pháp xét số dư

Phương pháp này thường được áp dụng để chứng minh rằng một phương trình vô nghiệm Kiến thức cơ bản cần nắm là xét số dư của lũy thừa khi chia cho một số cụ thể Cụ thể, với số mũ 2, ta có các kết quả sau: a² ≡ 0, 1 (mod 3), a² ≡ 0, 1 (mod 4), a² ≡ 0, 1, 4 (mod 5), a² ≡ 0, 1, 4 (mod 8), và a² ≡ 0, 1, 4, 7 (mod 9) Đối với số mũ 3, ta có a³ ≡ 0, 1, 8 (mod 9).

Chú ý: Trong các ví dụ tiếp theo ta đặt vế trái của phương trình = VT;

Vế phải của phương trình = VP.

Ví dụ 2.2.6 Giải phương trình nghiệm nguyên: x 2 = 2y 2 – 8y + 3

VP ≡ 3, 5 (mod 8) suy ra phương trình không có nghiệm nguyên.

Ví dụ 2.2.7 Giải phương trình nghiệm nguyên: 9x 2 + 6x + 10 = y 3 (*)

⇔(3x+ 1) 2 ≡ -1 (mod8) Điều này là vô lý suy ra loại trường hợp y = 2k, k ∈ Z TH2: y là số lẻ Ta viết lại phương trình (*) :

Ta xét hai trường hợp nhỏ :

Với y = 4k + 1, ta có y – 2 = 4k – 1 Khi đó, vế phải của biểu thức (***) có ước nguyên tố dạng p = 4l – 1, và ước này cũng là ước của vế trái (***) Điều này dẫn đến mâu thuẫn, vì vế trái là tổng của hai số chính phương.

Với y = 4k – 1 Khi đó y 2 + 2y + 4 có dạng 4m – 1.

Lập luận tương tự ta cũng suy ra điều vô lý

Vậy không có giá trị của x, y thỏa mãn phương trình trên.

Ví dụ 2.2.8 Giải phương trình nghiệm nguyên: 15x 2 – 7y 2 = 9

⇒y 2 ≡ 0 (mod 3) ⇒y ≡ 0 (mod 3) Đặt y = 3.y‘(y ‘∈Z), phương trình trên có dạng: 15x 2 – 63.y‘ 2 = 9

Làm tương tự như trên ta suy ra được: x ≡ 0 (mod

Mà VP = 1 ≡1 (mod 3); VT ≡0, 2 (mod 3)

Vậy phương trình không có nghiệm nguyên.

Ví dụ 2.2.9 Giải phương trình: x 15 + y 15 + z 15 = 19 2003 + 7 2003 + 9 2003

Xét vế trái, ta có: a 3 ≡ 0, 1, -1 (mod 9)

Vì x 15 = (x 3 ) 5 = (x 5 ) 3 ⇒(x 5 ) 3 ≡ 0, 1, -1 (mod 9) Hay x 15 ≡ 0, 1, -1 (mod 9) Tương tự ta có: y 15 ≡ 0, 1, -1 (mod 9); z 15 ≡ 0, 1, -1 (mod 9)

Từ (*) và (**) suy ra vô lý

Vậy phương trình trên không có nghiệm nguyên.

Ví dụ 2.2.10 Giải phương trình với nghiệm tự nhiên: a) 3 x + 7 = y 3 b) 2 x + 2 y = 2 x+y

Lời giải a) Ta có: 3 x ≡ 1 (mod 3) khi x = 0 3 x ≡ 0 (mod 3) khi x = 1 3 x ≡ 0 (mod 9) khi x ≥2

Nếu x ≥2 ⇒3 x + 7 ≡7 (mod 9) suy ra vô lý

Với x = 1 ta có: 3 + 7 = y 3 => Không tìm đƣợc y nguyên ⇒ Loại

Vậy nghiệm duy nhất của phương trình là (x ; y) = (0 ; 2). b) 2 x + 2 y = 2 x+y

Vì vài trò của x và y trong phương trình là như nhau nên không mất tính tổng quát ta giả sử x ≥ y ⇒ 2 x ≥ 2 y

Chia hai vế của phương trình cho 2 y ta được:

TH1: Nếu x = 0 ta có: 2 -y +1 = 1 ⇒ Vô lý

TH2: Nếu x ≥ 1 ta thấy 2 x chẵn mà 1 lẻ nên suy ra 2 x-y phải lẻ ⇒ 2 x-y = 1 hay x – y = 0 ⇔ x = y

Vậy phương trình có nghiệm duy nhất là (x; y) = (1; 1).

Ví dụ 2.2.11 (Đề Olympic 30 - 4 năm 2014 trường THPT Bạc Liêu – Bạc Liêu)

Tìm nghiệm nguyên của phương trình:

Giả sử (1) có nghiệm nguyên (x0, y0) Ta có:

Suy ra 15n 2 – 7m 2 = 1 hay 15n 2 = 7m 2 +1 ⇒ (7m 2 + 1)  5 Mặt khác với mọi m ∈Z thì m 2 tận cùng bởi 0, 1, 4, 5, 6, 9

1 không thể chia hết cho 5 Cho nên

Vậy phương trình không có nghiệm nguyên

Vì A, A+1 nguyên tố cùng nhau nên A, A + 1 phải là

Gọi d là ƢCLN của y + 4 và y – 4, khi đó d |[(y + 4) – (y – 4)] = 8

Ta có t, s lẻ ⇒t 2 + ts +s 2 lẻ ⇒ t − s 8

Ví dụ 2.2.13 (Đề Olympic 30-4 năm 2014 trường THPT chuyên Nguyễn Quang Diệu – Đồng Tháp) T ì m c á c c ặ p s ố n g u y ê n t ố

∈N nên ta có số p có 3 dạng: p

 q = 3n + 2 Khi đó p ≡ 2 (mod 3), q ≡ 2(mod 3) => p + q = 1(mod 3)

Vậy trong hai số p, q phải có ít nhất một số chia hết cho 3 thì phương trình mới có nghiệm

Mặt khác p, q là các số nguyên tố nên trong hai số p, q phải có ít nhất một số bằng 3

Từ phương trình suy ra 3 3 – q 5 = (3 + q) 2 ⇒3 3 – q 5 ≥25 => q 2 ≤2, vô lý

Từ phương trình suy ra: p 3 – 3 5 = (p + 3) 2

p = 7 Vậy phương trình có nghiệm nguyên tố là

Ví dụ 2.2.14 (Đề Olympic 30 - 4 năm 2015 trường THPT chuyên

Nguyễn Bỉnh Khiêm – Vĩnh Long) Giải phương trình nghiệm nguyên: x 3

Xét phương trình: x 3 4y 3 + x 2 y + y + 13 Đặt x 2y + d, d ∈Z, ta có

(1) là phương trình ẩn yPhương trình (1) có nghiệm thực khi và chỉ: (5d 2 – 1) 2 –32d (d 3 – 13) ≥ 0

Phép thử trực tiếp cho ta nghiệm y = 1 khi d = 1, khi đó x = 3

Kết luận: Phương trình có nghiệm nguyên là: (x; y) = (3,1); (-26,-13).

Các bài tập tương tự:

Giải các phương trình nghiệm nguyên a) 7x 2 – 5y 2 = 3 b) 2x 2 + y 2 = 1007 c) x 3 + y 3 + z 3 = 2003 d) x 2| + y 2 + z 2 = 2015 e) x 4 + y 4 + z 4 + t 4 = 2015

Giải các phương trình sau với nghiệm tự nhiên: a) 5 x + 48 = y 2 b) 3 x + 8 = y 2 c) 2 x – 1 = y 2

3: Phương pháp biểu thị một ẩn theo ẩn còn lại

Ta sử dụng tính chất sau: Nếu a và b nguyên và a

Ví dụ 2.2.15 Giải phương trình nghiệm nguyên: x 2 y + y = 3 + x

Suy ra y x + 3 x 2 + 1. Để y nguyên thì x + 3

Vì x 2 + 3 có bậc là 2 mà x + 3 chỉ có bậc là 1 và dễ nhận thấy: x 2 +1 ≥ 1

∈Z chỉ xảy ra khi: x + 3 = 0 hoặc x + 3 ≥ x 2 +1 và (x+3) (x 2 +1) x 2 + 1

Với x = -1 thì Với x 0 thì Với x

Ví dụ 2.2.16 Giải phương trình nghiệm nguyên: xy – 2y – 3 = 3x – x 2

Với x = 2 ta thấy hiển nhiên không thỏa mãn:

Vậ y ng hiệ m của ph ƣơ ng trìn h là: (x; y)

Ví dụ 2.2.17 Giải phương trình nghiệm nguyên:

Làm tương tự như ví dụ 2.2.16 ta có tập nghiệm: (x; y) = (-1; 3); (0; -3)

Ví dụ 2.2.18 Tìm tất cả các cặp số nguyên sao cho: x 3 – x 2 y + 3x – 2y – 5 = 0

Làm tương tự ví dụ 2.2.15 ta được nghiệm của phương trình là: (x; y) = (5; 5); (-1; -3)

Ví dụ 2.2.19 (Đề Olympic 30-4 năm 2014 trường THPT chuyên Bảo Lộc – Lâm đồng)

Giải phương trình sau trên tập hợp các số nguyên

Nếu x = 1 thì phương trình (1) trở thành : -8y = 0 ⇔y = 0

Nếu x = -1 thì phương trình (1) trở thành: -4y = 0 ⇔y = 0

Vậy nghiệm nguyên của phương trình là:

 tương tự: Tìm nghiệm nguyên dương của phương trình a) x + xy 2 = y +5 b) 8y 2 – 25y = 3xy + 5x c) x 2 y 2 (x +y) + x+y = 3 + xy

Dạng 4: Phương pháp cực hạn hay xuống thang Ví dụ

2.2.20 Tìm nghiệm nguyên của phương trình: x 2 + y 2 = 7z 2 x0

Giả sử phương trình có nghiệm (x0, y0, z0) ≠(0, 0, 0)

Suy ra tồn tại bộ nghiệm (x0, y0, z0) sao cho

Thay vào phương trình ta có: x 2 0 + y 2 0 = 7z 2 0

Suy ra x 2 0≡0 (mod 7) và y 2 0≡0 (mod 7) Đặt x0 = 7x1 (x1∈Z), y0 = 7y1 (y1∈Z) Ta có phương trình: 7x 2 1 + 7y 2 1 = z 2 0

Nhận xét: (x1, y1, z1) cũng là nghiệm của phương trình đã cho

7 < x suy ra tồn tại bộ nghiệm (x1, y1, z1) có bé hơn Vậy phương trình có nghiệm duy nhất là (0, 0, 0)

Ví dụ 2.2.21 Giải phương trình nghiệm nguyên: x 2 + y 2 + z 2 = x 2 y 2

Ta thấy: a 2 ≡ 0 (mod 4) nếu a chẵn; a 2 ≡ 1 (mod 4) nếu a lẻ

Suy ra a 2 ≡0, 1 (mod 4), ta xét các trường hợp sau:

TH1: Cả 2 số x, y đều lẻ

Suy ra VT ≡2, 3 (mod 4), VP = x 2 y 2 ≡1 (mod 4) => Vô lý

TH2: Trong hai số x, y có 1 số lẻ, 1 số chẵn

Mà VP = x 2 y 2 ≡0 (mod 4) => Vô lý.

TH3 Hai số x y đều chẵn => VT = x 2 + y 2 + z 2 ≡ 0 (mod 4) thì z phải chẵn Đặt x = 2x1; y = 2y1; z = 2z1 ta có: x 2 1 + y 2 1 + z 2 1 = 4x1y1

Ta lại xét tiếp các trường hợp sau:

TH1: x1; y1 đều lẻ suy ra x 2 1 + y 2 1 + z 2 1≡2, 3 (mod 4) => Vô lý x

TH2: Trong hai số x1; y1 có 1 số chẵn, 1 số lẻ

Suy ra x 2 1 + y 2 1 + z 2 1≡1, 2 (mod 4) => Vô lý

TH3: Hai số x1; y1 cùng chẵn => x 2 1 + y 2 1 + z 2 1≡0 (mod 4) thì z1 phải chẵn

Lại đặt: x1 = 2x2; y1 = 2y2; z1 = 2z2 cứ tiếp tục quá trình nhƣ trên và ta thu đƣợc: x = 2 k xk; y = 2 k yk; z = 2 k zk;

Quá trình này không bao giờ dừng lại

Giả sử phương trình có nghiệm là (x0, y0, z0) ta suy ra mỗi số x0, y0, z0 luôn chia hết cho 2 k ( ∀k∈N )

Suy ra (x0, y0, z0) = (0, 0, 0) là nghiệm duy nhất của phương trình.

Ví dụ 2.2.22 Tìm nghiệm nguyên của phương trình: x 3 + 2y 3 = 4z 3

Suy ra tồn tại bộ nghiệm (x0, y0, z0) sao cho nhỏ nhất

Thay vào phương trình ta có: x 3 0 + 2y 3 0 = 4z 3 0

Suy ra x 3 0≡ 0 (mod 2) => x0≡ 0 (mod 2) Đặt x0 = 2x1, thay vào ta đƣợc: 8x 3 1 + 2y 3 0 = 4z 3 0

Tương tự ta lại suy ra được y0≡ 0 (mod 2), đặt y0 = 2y1 ta có phương trình:

⇒z0≡0 (mod 2), đặt z0 = 2z1 ta có phương trình:

Mặt khác: < x suy ra tồn tại bộ nghiệm (x1, y1, z1) có

Vậy phương trình có nghiệm duy nhất là (0, 0, 0). k y = z x 0 x 1 = 0 x x 0

Các bài tập tương tự: Tìm nghiệm nguyên của các phương trình: a) x 3 – 3y 3 = 9z 3 b) x 2 + y 2 = 6(z 2 + t 2 ) c) x 2 + y 2 + z 2 = 2xyz d) x 2 + y 2 + z 2 + t 2 = x 2 y 2 z 2

Dạng 5: Phương pháp sử dụng tính chia hết

Ví dụ 2.2.23 Giải phương trình nghiệm x hữu tỉ, y nguyên x 2 + 7x = y 2 Đặt x = m n

( m, n ∈ Z, n ≠ 0 và (|m|, |n|) = 1), thay vào phương trình ta được:

Vì 7mn  n; y 2 n 2  n suy ra m 2 n mà (|m|, |n|) = 1) nên mn vậy x ∈ Z

Ví dụ 2.2.24 Tìm các số nguyên x, y không nhỏ hơn 2 sao cho:

Theo bài ra ta có: (xy – 1)  (x -1)(y-1) (1)

Suy ra xy – 1 x – 1 và xy – 1 y – 1

Làm tương tự như trên ta có x – 1  y – 1 (**)

Từ (*) và (**) ta có: y – 1  x – 1 và x – 1  y – 1

Với: x -1 = y – 1 ⇒ x = y thay vào (1) ta có: x 2 – 1 (x – 1) 2

Với x – 1 = 1 – y suy ra x = 2 – y hay x + y = 2, mà bài toán yêu cầu tìm các giá trị nguyên không nhỏ hơn 2 nên trường hợp này loại.

Kết luận: Nghiệm thỏa mãn phương trình là: (x; y) = (2; 2); (3; 3).

Ví dụ 2.2.25 Giải phương trình nghiệm nguyên: x 2 + y 3 = y 6

Ta thấy (y 3 , y 3 – 1) = 1 mà x 2 là số chính phương nên suy ra y 3 , y 3 – 1 là các số chính phương. Đặt y 3 = a 2 ; y 3 – 1= b 2 ⇒ a 2 - b 2 = 1 ⇔ (a - b)(a + b) = 1

Hiển nhiên ta có: 0 ≤ a – b ≤ a + b nên từ (a - b)(a + b) = 1 ta suy ra:

Vậy nghiệm của phương trình là: (x; y) = (0; 1).

Nhận xét: Tích hai số nguyên tố cùng nhau là số chính phương thì hai số đó cùng là số chính phương.

Nếu tích hai số tự nhiên liên tiếp là số chính phương thì trong 2 số đó phải có một số bằng 0.

Ví dụ 2.2.26 Giải phương trình nghiệm nguyên: x 2 + xy + y 2 = x 2 y 2

Ta thấy (xy, xy + 1) = 1 mà (x + y) 2 là số chính phương nên suy ra xy, xy + 1 là các số chính phương. Đặt xy = a 2 ; xy + 1 = b 2 ⇒ b 2 - a 2 = 1 ⇔ (b - a)(b + a) = 1

⇒x.y = 0 thay vào phương trình: x 2 + xy + y 2 = x 2 y 2 ta được x 2 + y 2 = 0 ⇒ x = y = 0.

Ví dụ 2.2.27 (Đề Olympic 30-4 năm 2014 trường THPT Nguyễn Thị Minh Khai –

Tìm các số tự nhiên x thỏa mãn điều kiện: x 2 – 7x +11= 5 y

Nếu y = 0 thì phương trình trở thành: x 2 – 7x + 10 = 0

Phương trình trên có nghiệm (x, y) là (2; 0), (5; 0)

Nếu y = 1 thì phương trình trên trở thành:

Ta xét vế trái theo các trường hợp số dư của x khi chia cho 25

35k + 11 không chia hết cho 5 Vậy phương trình vô nghiệm

25k + 5 không chia hết cho 25 Phương trình vô nghiệm

15k +1 không chia hết cho 5 Phương trình vô nghiệm

Vậy nghiệm tự nhiên của phương trình là: (x; y) = (2;

Ví dụ 2.2.28 (Đề Olympic 30-4 năm 2015 trường

THPT Chuyên Tiền Giang –Tỉnh Tiền Giang).

Tìm các số nguyên dương x, y sao cho : (x 2

; y) là mộ t ng hiệ m ng uy ên dƣ ơn g củ a phương trình Ta có: (x 2 + y 2 ) 2014 = (xy) 2015

Do đó x, y cùng có tập các ƣớc nguyên tố

Gọi p là một ƣớc nguyên tố bất kì của x và y và ta kí hiệu vp(x) là số mũ của p trong phân tích tiêu chuẩn của x

Giả sử : vp(x) = m, vp(y) = n (m, n ∈Z + ) và m ≠ n

 m = n ⇔ m = n = 0 (điều này vô lý) Vậy vp(x) = vp(y), với mọi p là ƣớc nguyên tố của x và y

Do x, y có cùng tập các ƣớc nguyên tố nên x = y

Các bài tập tương tự: a) Tìm các số hữu tỉ x để x 2 + x + 6 là số chính phương

Tìm nghiệm nguyên của các phương trình: b) x 2 + x + 4 = y 2 c) x 2 y 2 – 2xy = x 2 +16y 2 d) x(1 +x + x 2 ) = 4y(y+1)

B Các ví dụ mình họa cho phương trình nghiệm nguyên sử dụng đánh giá để giải Dang 1: Phương pháp phân tích thành các tổng bình phương, tổng lập phương Ta phân tích thành các tổng không âm: A + B + C = 0

Nếu A, B, C đều không âm thì A = B = C = 0

Ví dụ 2.2.29 Giải phương trình nghiệm nguyên: x 2 – 3x + y 2 – 6y + 10 = 0

Ta thấy: 2y – 6 là số chẵn nên ta có:

Vậy nghiệm nguyên của phương trình là: (x; y) = (2; 4); (1; 2); (1; 4); (2; 2).

Ví dụ 2.2.30 Tìm nghiệm nguyên không âm của phương trình x 3 y 3 – 4xy 3 + y 2 + x 2 – 2y – 3 = 0

Theo giả thiết x, y nguyên và không âm nên ta có

Nếu x 2 – 4 = 0 ⇔ x = 2 thì y = 1 (chọn) hoặc x = -2 < 0 (loại).

Với x 2 – 4 < 0 mà x > 0 nên x = 1 thì ta suy ra không tìm đƣợc y => (loại) Vậy nghiệm nguyên dương của phương trình là: (x; y) = (2; 1).

x Giải các phương trình nghiệm nguyên: a) x 2 + 5y 2 – 4xy – 4y + 4 = 0 b) (x +y +1) 2 = 3(x 2 + y 2 +1)

Tìm nghiệm nguyên không âm của phương trình: x 2 + y 3 – 3y 2 = 65 – 3y

Dang 2: Phương pháp sử dung nguyên lí kẹp.

Ví dụ 2.2.31 Tìm nghiệm nguyên của phương trình x 4 – y 4 = 3y 2 + 1

Từ (1) và (2) ta suy ra: (y 2 + 1) 2 ≤ x 4 < (y 2 + 2) 2

Mà y 2 + 1 và y 2 + 2 là hai số nguyên liên tiếp nên (y 2 + 1) 2 và (y 2 + 2) 2 là hai số chính phương liên tiếp, suy ra x 4 = (y 2 + 1) 2 , thay vào phương trình ban đầu ta được: y 4 + 2y 2 + 1 = y 4 + 3y 2 + 1

Vậy nghiệm của phương trình là: (x; y) = (1; 0); (-1;

0) Ví dụ 2.2.32 Tìm nghiệm nguyên của phương trình. y 2 = 1 + x + x 2 + x 3 + x 4

⇒ (2x 2 + x) 2 < 4y 2 < (2x 2 + x +2) 2 Do đó 4y 2 = (2x 2 + x +1) 2 , thay vào (*) ta đƣợc: (2x 2 + x +1) 2 = 4 + 4x + 4x 2 + 4x 3 + 4x 4

Từ đó các nghiệm của phương trình là:

Ví dụ 2.2.33 Chứng mỉnh rằng với mọi số nguyên k cho trước, không tồn tại số nguyên dương x sao cho: x.(x +1) = k.(k +2)

Lời giải Giả sử x(x +1) = k(k +2) với k∈ Z + , x∈

Từ (1) và (2) suy ra x 2 < (k + 1) 2 < (x +1) 2 Điều này vô lý vì x và x + 1 là 2 số nguyên dương liên tiếp.

Vậy không tồn tại số nguyên dương x sao cho: x.(x +1) = k.(k +2).

Ví dụ 2.2.34 (Đề Olympic 30-4 năm 2015 của trường THPT chuyên Nguyễn Đình

Giải phương trình nghiệm nguyên: x 4 + x 2 – y 2 – y + 10 = 0

Giải từng trường hợp trên cho ta nghiệm của phương trình là :

Giải các phương trình nghiệm nguyên: a) y 3 = 1 + x + x 2 + x 3 b) y 3 – x 3 = 3x c) y 2 + y = x 4 + x 3 + x 2 + x

Dang 3: Phương pháp sắp thứ tự các ẩn.

Ví dụ 2.2.35 Giải phương trình nghiệm nguyên dương: xyz = x + y + z

Nếu một trong các số x, y, z bằng 0 thì ta có x = y = z = 0 (thỏa mãn) Xét trường hợp các biến đều dương.

Vì vai trò của x; y; z là nhƣ nhau nên không mất tính tổng quát ta giả sử:

Vì 0< x ≤ y≤ z nên ta có: xy xz yz

Tương tự, vì y ≤ z nên ta có: 1 = 1

Các bài tập tương tự: a) Tìm các số nguyên dương x; y; z; w phân biệt thỏa mãn điều kiện: x 2 + y 2 + z 2 + w 2 = 3(x + y + z +w) b) Tìm tất cả các bộ ba số nguyên dương (x; y; z) thỏa mãn điều kiện:

 c) Tìm tất cả các bộ ba số nguyên dương (x; y; z) sao cho: xy + yz + zx – xyz

Các bài tập tự ra: Giải các phương trình nghiệm nguyên dương sau: a) 2xyz = x + y + z b) x + 4y + 4z = xyz

C Phương trình nghiệm nguyên sử dụng tam thức bậc hai để giải Dang 1:

Phương pháp sử dụng tam thức bậc hai để phân tích thành nhân tử Ví dụ 2.2.36

Tìm nghiệm nguyên của phương trình sau : x 2 + 2y 2 + 3xy + 3x + 5y = 15

= (y – 1) 2 + 8, không phải là số chính phương, tuy nhiên 9(y +1) 2 − 4( 2y 2 + 5y

+ 2) = (y −1) 2 chính phương, vì vậy ta biến đổi phương trình đã cho thành x 2 + 2y 2 + 3xy + 3x + 5y = 15 x 2 + 3(y + 1)x + 2y 2 + 5y + 2 = 17

Có ∆ = (y – 1) 2 nên có 2 nghiệm là: x =− 3(y + 1) ± (y − 1)

Phương trình trên trở thành: (x + y + 2)(x + 2y +1) = 17

Từ đó x + y + 2 và x + 2y + 1 là ƣớc của 17 và lập bảng ta có đáp số là : (x ; y) = (-18 ; 17), (30 ; -15), (-36 ; 17), (12 ; -15).

Dang 2: Phương pháp sử dụng điều kiện có nghiệm của tam thức bậc hai

Ví dụ 2.2.37 Tìm nghiệm nguyên của phương trình

Phương trình (1) có nghiệm khi và chỉ khi

+)Với y = 2 và y = 2 ta có không tìm đƣợc x nguyên.

Vậy phương trình có hai nghiệm nguyên là (x ; y ) = (0; 0 ); (1; 1);

Ta coi phương trình (1) là phương trình bậc 2 ẩn là x + y Phương trình (1) có nghiệm khi và chỉ khi:

Với x 2 = 0 thì x = 0 thay vào phương trình ta được y = 0 Với x 2 = 1 thì x = ±1

+ Khi x = 1 thì ta có phương trình:

+ Khi x = -1 thì ta có phương trình:

+ khi x = 2 thì ta có phương trình:

Phương trình không có nghiệm nguyên => Loại

Phương trình trên vô nghiệm.

Vậy nghiệm nguyên của phương trình đã cho là:

Tìm các cặp số nguyên (x; y) thỏa mãn:

Dang 3: Phương pháp Sử dụng điều kiện ∆là số chính phương

Ví dụ 2.2.39 Tìm nghiệm nguyên dương của phương trình x 2 + 8x = 3 2y với y∈ N

Phương trình (1) có nghiệm nguyên Đặt 16 + 3 2y = z 2

Mà z + 3 y > z – 3 y nên ta suy ra:

Với y = 1 ta có phương trình: x 2 + 8x – 9 = 0

Vậy nghiệm nguyên của phương trình là: (x; y) = (1; 1); (-9; 1).

D Một số dạng khác của phương trình nghiệm nguyên.

Ví dụ 2.2.39 (Đề thi chọn HSG lớp 9 quận Hoàn Kiếm năm học 2016 – 2017)

Tìm tất cả các cặp số nguyên (x; y) thỏa mãn: x 3 + y 3 = (x + y) 2

0 ⇔ x = -y (với x, y bất kì ∈ Z) Th2: x 2 – xy + y 2 – x – y = 0

Xét các trường hợp còn lại ta được 4 cặp nghiệm là:

Vậy nghiệm của phương trình là: (x, y) = (0;1);(1; 0); (1; 2); (2; 1); (2;2) và (t; -t) với t ∈ Z

(Đề thi HSG lớp 9 - Tỉnh Yên Bái thi ngày 3/3/2017)

Tìm các số nguyên x, y thỏa mãn: x 2 + xy – 2016x – 2017y – 2018 = 0

Các khái niệm, định lí hàm số học

Các hàm số học cơ bản

3.1.1 Phi - hàm Ơ-le Định nghĩa Định nghĩa 3.1 Giả sử n là một số nguyên dương Phi-hàm Ơ-le của n 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 Phi-hàm Ơ-le là ϕ( n )

Trong toán học, với một số nguyên dương n, nếu a là số nguyên sao cho (a, n) = 1, thì luôn tồn tại một số nguyên dương k thỏa mãn a^k ≡ 1 (mod n) Số nguyên dương k nhỏ nhất thỏa mãn điều kiện này được gọi là cấp của số nguyên a (mod n) Hệ thặng dư thu gọn môđulô n là một tập hợp gồm ϕ(n) số nguyên, trong đó mỗi phần tử đều nguyên tố cùng nhau với n và không có hai phần tử nào đồng dư môđulô n.

Tập hợp {1, 3, 5, 7} là một hệ thặng dư thu gọn môđulô 8 Theo định nghĩa, một tập hợp A được coi là hệ thặng dư đầy đủ (mod n) nếu với bất kỳ số x thuộc Z, luôn tồn tại một phần tử a trong A sao cho x tương đương a (mod n).

Ví dụ 1.3 A = {0,1,2, , n - 1} là một hệ thặng dƣ đầy đủ theo môđulô n.

Một tập A = {a1, a2, , an} gồm n số được coi là một hệ thặng dư đầy đủ theo môđulô n nếu và chỉ nếu ai ≅ aj (mod n) với i khác j và i, j thuộc tập {1, 2, , n}.

Giả sử {r1, r2, , rϕ(n)} là một hệ thặng dư thu gọn môđulô n, với a là số nguyên dương và (a, n) = 1 Khi đó, tập hợp {ar1, ar2, , arϕ(n)} cũng tạo thành một hệ thặng dư thu gọn môđulô n.

Trước tiên ta chứng tỏ rằng, mỗi số nguyên arj là nguyên tố cùng nhau với n.

Giả sử (arj, n) > 1 với j nào đó, thì tồn tại ước nguyên tố p của (arj, n) Điều này dẫn đến hai khả năng: hoặc p chia hết cho a và p chia hết cho n, hoặc p chia hết cho rj và p chia hết cho n Tuy nhiên, không thể xảy ra trường hợp p chia hết cho cả rj và n, vì rj và n là hai số nguyên tố cùng nhau.

Tương tự, không thể có p |a và p |n.

Vậy arj và n nguyên tố cùng nhau với mọi j = 1, 2, , ϕ( n )

Còn phải chứng tỏ hai số arj, ark (j ≠ k) tùy ý không đồng dƣ môđulô n

Giả sử arj ≡ ark(mod n), j ≠ k và 1 ≤ j ≤ ϕ( n ) ; 1 ≤ k ≤ ϕ( n )

Vì (a, n) = 1 nên ta suy ra rj ≡ r k (mod n) Điều này mâu thuẫn vì rj, rk cùng thuộc một hệ thặng dƣ thu gọn ban đầu môđulô n.

Ví dụ 1.4 Tập hợp {1, 3, 5, 7} là một hệ thặng dƣ thu gọn môđulô 8.

Do (3, 8) = 1 nên {3, 9,15, 21} cũng là một hệ thặng dƣ môđulô 8.

Tính chất 2 (Định lí Ơ-le)

Giả sử m là số nguyên dương và a là số nguyên với (a, m) = 1 Khi đó a ( m ) ≡ 1(mod m).

Chứng minh r } là một hệ thặng thu gọn gồm các số nguyên dương không vượt quá m và nguyên tố cùng nhau với m.

Do tính chất 1 và do (a, m) = 1, tập hợp |ar1, ar2, , a r ϕ (n)| là một hệ thặng dư thu gọn môđulô m Các thặng dư dương bé nhất của ar1, ar2, , a r ϕ (m) là các số nguyên r1, r2, , ϕ(m) được xếp theo thứ tự Khi nhân các vế trong hệ thặng dư thu gọn này, ta thu được kết quả ar1.ar2 a r ϕ (m).

Ta có thể tìm nghịch đảo môđulô n bằng cách sử dụng Định lí Ơ-le.

Giả sử a,m là các số nguyên tố cùng nhau, khi đó: a a  ( m ) 1 = a  ( m ) ≡ 1(mod m). ϕ ( n ) r ϕ ( m ) ϕ ( m ) r r

Vậy a ( m ) 1 là nghịch đảo của a môđulô m.

Ví dụ 1.5 2 ( 9 ) 1 = 2 6-1 = 2 5 = 32 ≡ 5 (mod 9) là một nghịch đảo của 2 môđulô

Hệ quả 3.1 Với (a, b) = 1 thì a  ( b ) + b  ( a ) ≡ 1(mod ab).

Hệ quả 3.2 Với (a, b) = 1 và n, v là hai số nguyên dương nào đó thì a n ( b ) + b v ( a ) ≡ 1(mod ab).

Hệ quả 3.3 Giả sử có k (k ≥ 2) số nguyên dương m1, m2,…., mk và chúng nguyên tố với nhau từng đôi một. Đặt M = m1 m2….mk = mi.ti với i = 1, 2, …., k ta có: n + n

Bây giờ ta sẽ cho công thức tính giá trị của phi-hàm Ơ-le tại n khi biết phân tích của n ra thừa số nguyên tố.

Tính chất 3 Với số nguyên tố p ta có ϕ( p ) = p - 1.

Ngƣợc lại, nếu p là số nguyên dương sao cho

Chứng minh ϕ( p ) = p - 1 thì p là số nguyên tố.

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, dẫn đến ϕ(p) = p - 1 Ngược lại, nếu p là hợp số, thì p sẽ có các ước d với 1 < d < p.

Tất nhiên p và d không nguyên tố cùng nhau Nhƣ 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, nên ϕ( p ) ≤ p - 2.

Theo giả thiết, ϕ( p ) = p - 1 Vậy p là số nguyên tố.

Tính chất 4 Giả sử p là số nguyên tố và a là số nguyên dương.

Các số nguyên dương nhỏ hơn p a không nguyên tố cùng nhau với p là các số không vƣợt quá p a-1 và chia hết cho p.

Có đúng p a-1 số nhƣ vậy.

− p a-1 số nguyên nhỏ hơn p a và nguyên tố cùng nhau với p a

Tính chất 5 Nếu m, n là các số nguyên dương nguyên tố cùng nhau thì ϕ( mn ) = ϕ ( m ) ϕ ( n )

Ta viết các số nguyên dương không vượt quá mn thành bảng sau:

Bây giờ giả sử r là một số nguyên không vƣợt quá m Giả sử (m, r) = d > 1.

Khi đó, không có số nào trong dòng thứ r nguyên tố cùng nhau với mn, vì mỗi phần tử của dòng đó đều có dạng km + r, trong đó

Để tìm các số trong bảng mà nguyên tố cùng nhau với mn, ta cần xem xét các dòng thứ r với điều kiện (m, r) = 1 Mỗi dòng này sẽ chứa các số r, m + r, , (n - 1)m, với 1 ≤ k ≤ n - 1 và d chia hết cho (km + r), đồng thời d cũng chia hết cho m và r.

Vì (r, m) = 1, mỗi số nguyên trong dãy đều nguyên tố cùng nhau với n, tạo thành hệ thặng dư đầy đủ môđulô n Do đó, có đúng ϕ(n) số trong dãy này nguyên tố cùng nhau với n Những số này cũng nguyên tố cùng nhau với m, nên chúng nguyên tố cùng nhau với mn.

Vì có ϕ( m ) dòng, mỗi dòng chứa ϕ( n ) số nguyên tố cùng nhau với mn nên ta suy ra ϕ( mn ) = ϕ ( m ) ϕ ( n )

Kết hợp hai tính chất trên ta đƣợc tính chất sau:

Tính chất 6 Giả sử n = p p n2 p nk là phân tích n ra thừa số nguyên tố. n

V ì ϕ là h à m c ó tí nh chất nhân nên nếu n có phân tích nhƣ trên, ta đƣợc: ϕ( n ) = ϕ ( p a 1 ) ϕ ( p a2 ) ϕ ( p a k )

Tính chất 7 Giả sử n là một số nguyên dương Khi đó:

Tổng số tự nhiên từ 1 đến n được phân chia thành các lớp khác nhau Lớp Cd bao gồm các số nguyên m trong khoảng 1 đến n, mà có ước chung d với n Cụ thể, m thuộc lớp Cd nếu d là ước chung của cả m và n.

Như vậy, số phần tử của Cd là các số nguyên dương không vượt quá n d và nguyên tố cùng nhau với n

; tức là Cd gồm ϕ n  phần tử. d   

Vì mỗi số nguyên m từ 1 đến n thuộc một và chỉ một lớp Cd nào đó

(d = (m, n)) nên n bằng tổng của số các thành phần trong các lớp Cd, d là ƣớc số của n.

Hàm tổng các ước số dương của n

 d d  d d Định nghĩa 3.1 Hàm tổng các ước dương của số tự nhiên n được kí hiệu là σ( n ) Ví dụ 1.7 σ( 12 ) = 1 + 2 + 3 + 4 + 6 + 12 = 28.

Chú ý 3.2 Ta có thể biểu diễn hàm σ( n ) dưới dạng: σ( n ) = d|n ∑ d

Bổ đề 3.1 nêu rõ rằng, với m và n là các số nguyên dương nguyên tố cùng nhau, nếu d là ước chung của mn, thì tồn tại một cặp duy nhất các ước dương d1 của m và d2 của n sao cho d = d1.d2 Ngược lại, nếu d1 và d2 là các ước dương tương ứng của m và n, thì d = d1.d2 cũng sẽ là ước dương của mn.

Giả sử m, n có phân tích ra thừa số nguyên tố nhƣ sau: m = m1 m2 m s

Vì (m, n) = 1 nên tập hợp số nguyên tố p1, p2,… ps và tập hợp các số nguyên tố q1, q2 ,

,qt không có phần tử chung Do đó phân tích ra thừa số của mn có dạng: mn = m 1 m 2 m s n 1 n 2 n t

Nhƣ vậy, nếu d là một ƣớc chung của mn thì d = e 1 e 2 e s f 1 f 2 f t ,

1 2 s 1 2 t trong đó 0 ≤ e i ≤ mi (i = 1, 2, , s) ; 0 ≤ fi ≤ ni (i = 1, 2, , s). Đặt: d1 e1 e2

Ngược lại, giả sử d1 và d2 là các ước dương tương ứng của m và n Khi đó: d1 = e1 e2

Rõ ràng là ƣớc của mn

Trong phân tích thừa số nguyên tố, lũy thừa của mỗi số nguyên tố trong số d không được lớn hơn lũy thừa tương ứng của số nguyên tố đó trong phân tích của số mn.

Bổ đề 3.2 Giả sử p là số nguyên tố, a là số nguyên dương Khi đó a +1 σ( p p a ) = ( 1+ p + 2 + + p a a

Các ước của p a là 1, p, p 2 , p a Do đó, p a có đúng a + 1 ước dương p a +1 −1 τ( p a ) = a +1

Giả sử f là một hàm có tính chất nhân Khi đó hàm có tính chất nhân.

Ta sẽ chỉ ra rằng nếu m, n là các số nguyê n dương nguyê n tố cùng nhau thì F(mn) = F(m).F(n) Giả sử (m, n) = 1, ta có:

Vì (m, n) = 1, theo bổ đề 3.1, mỗi ước số của mn có thể được biểu diễn duy nhất dưới dạng tích của các ước số d1 của m và d2 của n, với điều kiện (d1, d2) = 1 Mỗi cặp ước số d1 của m và d2 của n sẽ tương ứng với ước số d1.d2 của mn.

Do đó ta có thể viết:

Vì f là hàm có tính chất nhân và (d1, d2) = 1 nên

Hàm σ( n ) là hàm nhân tính, tức là: Với mọi số tự nhiên n1, n2 nguyên tố cùng nhau thì σ( n 1 n 2 ) = σ ( n 1 ) σ ( n 2 )

Dựa vào Định lý 3.1, hàm số σ(n) có tính chất nhân, cho phép chúng ta diễn đạt công thức của nó dựa trên phân tích thành thừa số nguyên tố của n.

Tính chất 2 Nếu p là số nguyên tố thì σ( n ) = 1 + p

Chứng minh Đƣợc suy ra từ Bổ đề 3.2

Tính chất 3 Giả sử n là số nguyên dương và có khai triển chính tắc

Hàm số các ƣớc τ ( n ) 54

Do hàm σ có tính chất nhân nên ta có σ( n ) = σ ( p  1 ) σ ( p  2 ) σ ( p  s )

3.3.1 Định nghĩa Định nghĩa 3.1 Số các ước dương của của số tự nhiên n được kí hiệu là Ví dụ τ(1) = 1, τ (2) = 2, τ(12) = 6.

Chứng minh τ( n ) là hàm có tính chất nhân tính.

Dựa trực tiếp vào Định lí (3.1)

Tính chất 2 Nếu p là số nguyên tố thì τ(p) = 2.

Tính chất 3 Giả sử số nguyên dương n có khai triển chính tắc n = p  1 p  2 p  k thì τ (n) = ( α +1 )( α +1 ) ( α +1 )

Chứng minh Đƣợc suy ra trực tiếp từ Bổ đề 3.2

Hàm Mobius à(n)

Hàm Mobius ký hiệu là à(n) , đƣợc xỏc định bởi: i) à(1) = 1 ii) à(n) = (-1) k , nếu n là tớch của k số nguyờn tố khỏc nhau; iii)à(n) = 0, nếu n cú ước chớnh phương khỏc 1

Tớnh chất 1: Hàm à(n) là một hàm nhõn tớnh thỏa món

Tính chất 2: Giả sử f là hàm số học, nếu với mọi số nguyên dương n Khi đó ta có

Tớnh chất 1 Dễ thấy à( n ) là hàm nhõn tớnh nờn ta cú: F(n)

Hiển nhiên F(1) = 1 Nếu p là một số nguyên tố và α là một số nguyên dương thì

Hàm phần lẻ {x}