Luận văn Thạc sĩ Toán học: Về đồng dư đa thức

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC KHOA HỌC --------------------------- NGUYỄN THỊ HOÀN

VỀ ĐỒNG DƯ ĐA THỨC

LUẬN VĂN THẠC SĨ TOÁN HỌC

THÁI NGUYÊN - 2019

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC KHOA HỌC ---------------------------

NGUYỄN THỊ HOÀN

VỀ ĐỒNG DƯ ĐA THỨC

Chuyên ngành: Phương pháp Toán sơ cấp

Mã số: 8 46 01 13

LUẬN VĂN THẠC SĨ TOÁN HỌC

NGƯỜI HƯỚNG DẪN KHOA HỌC TS. Nguyễn Thị Kiều Nga

THÁI NGUYÊN - 2019

Lời cảm ơn

Luận văn này được hoàn thành tại trường Đại học Khoa học - Đại học

Thái Nguyên. Tác giả xin bày tỏ lòng biết ơn sâu sắc đối với TS Nguyễn

Thị Kiều Nga, cô đã trực tiếp hướng dẫn tận tình và động viên tác giả

trong suốt thời gian nghiên cứu vừa qua.

Tác giả cũng xin chân thành cảm ơn tới các quý thầy, cô giáo đã giảng

dạy lớp cao học Toán K11A, các bạn học viên và đồng nghiệp đã tạo điều

kiện thuận lợi, giúp đỡ tác giả trong quá trình học tập và nghiên cứu tại

trường. Tác giả cũng xin bày tỏ lòng biết ơn sâu sắc tới gia đình và người

thân luôn khuyến khích động viên tác giả trong suốt quá trình học cao học

và viết luận văn này.

Mặc dù có nhiều cố gắng nhưng luận văn khó tránh khỏi những thiếu

sót và hạn chế. Tác giả mong nhận được những ý kiến đóng góp của các

thầy cô và các bạn đọc để luận văn được hoàn thiện hơn.

Xin chân thành cảm ơn!

Thái Nguyên, tháng 4 năm 2019

Tác giả

Nguyễn Thị Hoàn

Mục lục

Mở đầu 1

1 Kiến thức chuẩn bị 3

3 1.1 Một số kiến thức cơ bản về đa thức một ẩn . . . . . . . . .

3 1.1.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . . .

4 1.1.2 Bậc của đa thức . . . . . . . . . . . . . . . . . . . .

5 1.1.3 Phép chia với dư . . . . . . . . . . . . . . . . . . . .

6 1.1.4 Nghiệm của đa thức . . . . . . . . . . . . . . . . . .

7 1.1.5 Ước chung lớn nhất, bội chung nhỏ nhất của đa thức

8 1.2 Một số định lý cơ bản của số học . . . . . . . . . . . . . . .

10 2 Đồng dư đa thức

2.1 Đồng dư đa thức với môđun một đa thức . . . . . . . . . . 10

2.2 Tập hợp gồm các lớp tương đương theo quan hệ đồng dư

(cid:46) môđun một đa thức . . . . . . . . . . . . . . . . . . . . . . 15 (p(x)) . . . . . . . . . . . . . . . . . . . . . . 17 2.3 Trường A[x]

2.4 Đồng dư đa thức với môđun nguyên tố . . . . . . . . . . . . 18

. . . . . . 23

. . . . . . . . . . . . . . . . . . 29

2.5 Đồng dư đa thức với môđun lũy thừa nguyên tố 2.6 Đồng dư x2 ≡ a (mod m) 2.7 Phương trình đồng dư bậc hai tổng quát . . . . . . . . . . . 35

3 Một số ứng dụng của đồng dư đa thức trong giải toán sơ

. . 43 cấp 38 3.1 Tìm đa thức dư khi chia đa thức f (x) cho g(x) trong A[x] . 38 3.2 Chứng minh đa thức f (x) chia hết cho đa thức g(x) trong A[x] 40 3.3 Tìm điều kiện để f (x) chia hết cho g(x) (cid:54)= 0 trong A[x]

3.4 Bài toán về nghiệm của đa thức . . . . . . . . . . . . . . . 51

3.5 Một số bài toán khác . . . . . . . . . . . . . . . . . . . . . 51

Kết luận 56

iii

Tài liệu tham khảo 57

Mở đầu

Đa thức là một khái niệm cơ bản và quan trọng của toán học. Đa thức

không chỉ là đối tượng nghiên cứu của Đại số mà còn là công cụ quan

trọng được sử dụng trong các nghiên cứu của Giải tích như Lý thuyết điều

khiển, Lý thuyết tối ưu... Trong các kỳ thi học sinh giỏi trong và ngoài

nước các bài toán về đa thức cũng thường được đề cập đến. Vì thế trong

chương trình toán phổ thông đa thức là một chuyên đề quan trọng và cần

thiết trong việc bồi dưỡng học sinh giỏi.

Đồng dư đa thức là một vấn đề được nhiều nhà toán học quan tâm

khi nghiên cứu về đa thức mà trường hợp đặc biệt là các phương trình đồng dư hoặc các đồng dư thức. Theo [4], cho A là một trường, f (x), g(x), p(x) ∈ A[x], p(x) (cid:54)= 0. Ta nói f (x) đồng dư với g(x) theo môđun p(x) nếu và chỉ nếu f (x) − g(x) chia hết cho p(x) trong A[x]. Vì thế "đồng dư

đa thức theo môđun một đa thức" có thể coi là tổng quát của khái niệm

"đồng dư thức" đã biết.

Luận văn "Về đồng dư đa thức" nghiên cứu về đồng dư đa thức theo

môđun một đa thức, đồng dư đa thức theo môđun số nguyên tố và lũy

thừa một số nguyên tố. Các kết quả trong luận văn được tham khảo ở các

tài liệu [2], [4], [6], [7]. Hơn nữa, chúng tôi cũng đưa ra được đặc trưng của

đồng dư đa thức theo môđun một đa thức (Mệnh đề 2.1.2) và một số tính

chất của đồng dư đa thức theo môđun một đa thức (Định lý 2.1.3). Sử

dụng đồng dư đa thức, chúng tôi nghiên cứu một số ứng dụng của đồng

dư đa thức trong giải toán sơ cấp.

Luận văn gồm 3 chương.

Chương 1: Trình bày một số kiến thức chuẩn bị về đa thức và một số

tính chất số học cần thiết cho các chương sau.

Chương 2: Nghiên cứu về đồng dư đa thức: Đồng dư đa thức theo môđun

một đa thức và một số trường hợp đặc biệt là môđun số nguyên tố và lũy

thừa số nguyên tố.

Chương 3: Trình bày một số ứng dụng của đồng dư đa thức trong toán

sơ cấp.

Mặc dù đã rất cố gắng nhưng do thời gian và năng lực nghiên cứu còn

hạn chế nên rất mong được sự góp ý của các thầy cô và các bạn đọc để

luận văn được hoàn thiện hơn.

Chương 1

Kiến thức chuẩn bị

Trong chương này, chúng tôi nhắc lại một số kiến thức về đa thức một

ẩn và kiến thức về số học như khái niệm đa thức, bậc, nghiệm của đa thức,

một số định lý thường gặp như Định lý phép chia với dư, Định lý Bezout,

Viete, hàm Euler, một số định lý quan trọng của số học,... nhằm thuận

1.1 Một số kiến thức cơ bản về đa thức một ẩn

tiện cho việc theo dõi các chương sau.

1.1.1 Định nghĩa

f (x) = a0 + a1x + ... + amxm,

Định nghĩa 1.1.1. Cho A là một vành giao hoán có đơn vị. Một đa thức một ẩn với hệ số trên A là một biểu thức có dạng:

trong đó ai ∈ A với mọi i = 0, m và x là một kí hiệu gọi là biến. Khi đó, ai gọi là các hệ số thứ i của đa thức, aixi gọi là hạng tử thứ i của đa thức, a0 gọi là hạng tử tự do. Kí hiệu A[x] là tập các đa thức một biến x với hệ số trong A.

f (x) = a0 + a1x + ... + anxn

Cho hai đa thức

g(x) = b0 + b1x + ... + bmxm

và

g(x) = b0 + b1x + ... + bnxn + bn+1xn+1 + ... + bn+txn+t.

thuộc A[x]. Không giảm tính tổng quát, ta có thể giả sử m (cid:62) n và m = n + t. Khi đó

Ta nói hai đa thức f (x) và g(x) là bằng nhau nếu ai = bi với mọi i = 0, n và bn+1 = ... = bn+t = 0.

f (x) = a0 + a1x + ... + anxn

Định nghĩa 1.1.2. Cho hai đa thức

g(x) = b0 + b1x + ... + bmxm

và

max {n,m} (cid:88)

f (x) + g(x) =

(ai + bi)xi.

i=0

thuộc A[x]. Khi đó

m+n (cid:88)

f (x)g(x) =

xi.

ajbi−j

i=0

j=0

(cid:17) (cid:16) i (cid:88)

Quy ước ai = 0 nếu i > n và bi = 0 nếu i > m. Khi đó A[x] là một vành giao hoán có đơn vị với phép cộng và phép

nhân các đa thức, A[x] gọi là vành đa thức một ẩn với hệ số trong A.

1.1.2 Bậc của đa thức

f (x) = a0 + a1x + ... + an−1xn−1 + anxn

Định nghĩa 1.1.3. Bậc của đa thức khác 0 trong A[x]

là n nếu an (cid:54)= 0, kí hiệu deg f (x) = n.

Quy ước, đa thức 0 không có bậc hoặc có bậc là −∞.

Sau đây là tính chất về bậc của đa thức

Định lý 1.1.4. Giả sử f (x), g(x) là hai đa thức khác 0 thuộc A[x].

(i) Nếu f (x) + g(x) (cid:54)= 0 thì

f (x) + g(x)

(cid:16) (cid:17) (cid:110) (cid:111) deg (cid:54) max deg f (x), deg g(x)

(ii) Nếu f (x)g(x) (cid:54)= 0 thì

f (x)g(x)

(cid:16) (cid:17) deg (cid:54) deg f (x) + deg g(x),

đẳng thức sẽ xảy ra nếu A là miền nguyên.

1.1.3 Phép chia với dư

Định lý 1.1.5. (Định lý phép chia với dư). Cho A là một vành giao hoán có đơn vị và f (x), g(x) là hai đa thức thuộc A[x], g(x) là đa thức có hệ số cao nhất khả nghịch trong A. Khi đó tồn tại duy nhất q(x), r(x) ∈ A[x] sao cho f (x) = g(x)q(x) + r(x) và deg r(x) < deg g(x) nếu r(x) (cid:54)= 0.

Các đa thức q(x) và r(x) trong định lý trên lần lượt gọi là đa thức thương và dư trong phép chia f (x) cho g(x). Nếu r(x) = 0 thì ta nói f (x) chia hết cho g(x).

Kết quả sau đây là hệ quả trực tiếp của Định lý phép chia với dư trong

trường hợp đa thức g(x) là đa thức bậc nhất có hệ số cao nhất là 1.

f (x) =

Hệ quả 1.1.6. (Định lý Bezout). Cho A là một vành giao hoán có đơn vị và g(x) ∈ A[x], α ∈ A. Khi đó dư của phép chia f (x) cho x − α là f (α).

n (cid:80) i=0

x − α, ta được f (x) = (x − α)q(x) + r với r = f (α) và deg q(x) = n − 1. Giả sử q(x) = bn−1xn−1 + ... + b1x + b0. Đồng nhất các hệ số, ta có bn−1 = an, bn−2 = an−1 + αbn−1, ..., bk−1 = ak + αbk, ..., b0 = a1 + αb1, r = a0 + αb0.

... ...

α bn−1 = an

an−1 bn−2 = an−1 + αbn−1

b0 = a1 + αb1 r = a0 + αb0

Chú ý 1.1.7. Cho f (x) ∈ A[x], α ∈ A. Ta có lược đồ sau gọi là lược đồ Horner để tìm thương và dư của phép chia f (x) cho x − α. Giả sử aixi, an (cid:54)= 0. Theo Định lý phép chia với dư, chia f (x) cho

Nếu A là một trường, g(x) ∈ A[x], g(x) (cid:54)= 0 thì hiển nhiên hệ số cao

nhất của g(x) là khả nghịch. Vì thế ta có ngay hệ quả sau:

f (x) = g(x)q(x) + r(x) và deg r(x) < deg g(x) nếu r(x) (cid:54)= 0.

Hệ quả 1.1.8. Cho A là một trường và f (x), g(x) là hai đa thức thuộc A[x], g(x) (cid:54)= 0. Khi đó tồn tại duy nhất q(x), r(x) ∈ A[x] sao cho

1.1.4 Nghiệm của đa thức

Trong toàn bộ mục này, ta luôn giả sử A là một vành giao hoán có

đơn vị.

f (α) = a0 + a1α + ... + an−1αn−1 + anαn = 0,

Định nghĩa 1.1.9. Giả sử A là một vành con của vành giao hoán K. Cho f (x) = a0 + a1x + ... + an−1xn−1 + anxn ∈ A[x]. Khi đó, số α ∈ K được gọi là nghiệm của đa thức f (x) trong K nếu

Từ Định lý Bezout ta có ngay bổ đề sau.

Bổ đề 1.1.10. Phần tử α ∈ A là nghiệm của f (x) ∈ A[x] khi và chỉ khi f (x) chia hết cho x − α.

Định nghĩa 1.1.11. Cho K là vành giao hoán chứa vành A, f (x) ∈ A[x], α ∈ K. Nếu tồn tại số tự nhiên k (cid:54)= 0 sao cho f (x) chia hết cho (x − α)k nhưng f (x) không chia hết cho (x − α)k+1 thì α được gọi là nghiệm bội bậc k của f (x).

Nếu k = 1 thì α được gọi là nghiệm đơn, k = 2 thì α được gọi là nghiệm

kép.

Từ Định nghĩa 1.1.11, ta có ngay bổ đề sau:

Bổ đề 1.1.12. Phần tử α ∈ K là nghiệm bội bậc k của f (x) ∈ A[x] khi và chỉ khi f (x) chia hết cho (x − α)k.

Sau đây là công thức Viete về mối liên hệ giữa các nghiệm của đa thức

với các hệ số của đa thức đó.

f (x) = a0 + a1x + ... + an−1xn−1 + anxn ∈ A[x].

Mệnh đề 1.1.13. (Công thức Viete). Cho A là một miền nguyên và

Giả sử α1, α2, ..., αn là các nghiệm của f (x) trong một miền nguyên K

n (cid:88)

αi = (−1)an−1a−1 n

i=1

chứa A. Khi đó

αiαj = (−1)2an−2a−1 n

...

(cid:88)

αi1αi2...αik = (−1)kan−ka−1 n

α1α2...αn = (−1)na0a−1 n

(cid:88)

1.1.5 Ước chung lớn nhất, bội chung nhỏ nhất của đa thức

Trong toàn bộ phần này vành A là một trường.

Định nghĩa 1.1.14. i) Một đa thức a(x) ∈ A[x] gọi là một ước chung của các đa thức f1(x), ..., fs(x) ∈ A[x] nếu a(x) là ước của fi(x) với mọi i = 1, s.

ii) Một ước chung a(x) của các đa thức f1(x), ..., fs(x) gọi là một ước chung lớn nhất của f1(x), ..., fs(x) nếu a(x) là bội của mọi ước chung của f1(x), ..., fs(x).

Chú ý rằng ước chung lớn nhất của hai đa thức f (x), g(x) chỉ khác

nhau một nhân tử là hằng số khác 0 thuộc A.

Bổ đề 1.1.15. Cho a(x) ∈ A[x] là ước chung lớn nhất của f (x), g(x) ∈ A[x]. Khi đó đa thức t(x) ∈ A[x] cũng là ước chung lớn nhất của f (x), g(x) nếu và chỉ nếu tồn tại 0 (cid:54)= c ∈ A sao cho t(x) = c.a(x).

Ta có thể tìm ước chung lớn nhất của các đa thức dựa vào Định lý phép

chia với dư.

Bổ đề 1.1.16. Giả sử f (x) = g(x)q(x) + r(x), trong đó r(x) = 0 hoặc deg r(x) < deg g(x). Khi đó đa thức a(x) là ước chung lớn nhất của f (x) và g(x) nếu và chỉ nếu nó là ước chung lớn nhất của g(x) và r(x).

Định nghĩa 1.1.17. i) Một đa thức b(x) ∈ A[x] được gọi là một bội chung của các đa thức f1(x), ..., fs(x) ∈ A[x] nếu b(x) là bội của fi(x) với mọi i = 1, s.

ii) Một bội chung b(x) của các đa thức f1(x), ..., fs(x) gọi là một bội chung nhỏ nhất của f1(x), ..., fs(x) nếu mọi bội chung m(x) của fi(x) với i = 1, s đều là bội của b(x).

f (x), g(x) chỉ khác nhau các nhân tử là hằng số khác 0 trong A.

Tương tự như ước chung lớn nhất, bội chung nhỏ nhất của các đa thức

Bổ đề 1.1.18. Cho b(x) ∈ A[x] là bội chung nhỏ nhất của f (x), g(x) ∈ A[x]. Khi đó đa thức t(x) ∈ A[x] cũng là bội chung nhỏ nhất của f (x), g(x) nếu và chỉ nếu tồn tại 0 (cid:54)= c ∈ A sao cho t(x) = c.b(x).

Sau đây chúng tôi nhắc lại một số kiến thức số học để chuẩn bị cho các

1.2 Một số định lý cơ bản của số học

chương sau là: Hàm Euler, Định lý Euler, Fermat, Wilson.

Định nghĩa 1.2.1. Cho n là số tự nhiên khác 0. Hàm Euler của n ký hiệu là ϕ(n) xác định như sau

- Nếu n = 1 thì ϕ(1) = 1 - Nếu n > 1 thì ϕ(n) = |{a ∈ N, a < n, (a, n) = 1}|.

Nhận xét 1.2.2. Nếu p nguyên tố thì ϕ(p) = p − 1

Ví dụ 1.2.3. ϕ(4) = 2, ϕ(8) = 4, ϕ(5) = 4, ϕ(7) = 6.

ϕ(n) = pα1−1

(p1 − 1)pα2−1

2 ...pαk 1 pα2 (p2 − 1)...pαk−1

(pk − 1).

thì Ta có công thức tính hàm Euler như sau: Giả sử n có phân tích tiêu chuẩn n = pα1

ϕ(n) = n

1 −

...

1 −

1 p1

1 p2

1 pk

Hay (cid:16) (cid:17)(cid:16) (cid:17) (cid:16) (cid:17)

aϕ(n) ≡ 1( mod n).

Định lý 1.2.4. (Định lý Euler). Cho a là số nguyên, n là số nguyên dương và (a, n) = 1. Khi đó

Định lý sau là hệ quả của Định lý Euler.

Định lý 1.2.5. (Định lý Fermat). Cho p là số nguyên tố và với a là số

ap ≡ a( mod p).

nguyên bất kỳ. Khi đó

(a, p) = 1. Khi đó

ap−1 ≡ 1( mod p).

Hoặc phát biểu dưới dạng khác: Cho p là số nguyên tố, a là số nguyên,

Chương 2

Đồng dư đa thức

Trong chương này chúng tôi trình bày một số vấn đề về đồng dư đa

thức là: Đồng dư đa thức với môđun một đa thức, đồng dư đa thức với

môđun nguyên tố và đồng dư đa thức với môđun lũy thừa nguyên tố. Các

kết quả này được tham khảo ở [2], [4], [6], [7]. Chúng tôi cũng đưa ra đặc

trưng của đồng dư đa thức theo môđun một đa thức và một số tính chất

2.1 Đồng dư đa thức với môđun một đa thức

của nó.

Trong mục này, chúng tôi trình bày về đồng dư đa thức với môđun một

đa thức. Các kết quả chính trong mục này chúng tôi tham khảo trong [4]. Trong suốt mục này, ta luôn giả thiết vành A là một trường.

f (x) ≡ g(x) (cid:0)mod p(x)(cid:1).

Định nghĩa 2.1.1. [4]. Cho f (x), g(x), p(x) ∈ A[x], p(x) (cid:54)= 0. Ta nói đa ...p(x). Nếu thức f (x) và g(x) đồng dư theo môđun p(x) nếu f (x) − g(x) f (x) và g(x) đồng dư theo môđun p(x) thì kí hiệu là

Mệnh đề sau đây chúng tôi đưa ra đặc trưng của đồng dư đa thức với

môđun một đa thức

Mệnh đề 2.1.2. Cho các đa thức f (x), g(x), p(x) ∈ A[x], p(x) (cid:54)= 0. Các

khẳng định sau là tương đương

(i) f (x) ≡ g(x) (cid:0)mod p(x)(cid:1);

(ii) f (x) và g(x) cho cùng một đa thức dư khi chia cho p(x);

(iii) f (x) = g(x) + p(x)t(x) với t(x) ∈ A[x].

Chứng minh. (i) ⇒ (ii). Vì A là một trường nên tồn tại phép chia có dư trong A[x]. Giả sử f (x) = p(x)q(x) + r(x).

Nếu r(x) (cid:54)= 0 thì deg r(x) < deg p(x) và g(x) = p(x)h(x) + s(x).

Nếu s(x) (cid:54)= 0 thì deg s(x) < deg p(x).

f (x) − g(x) = p(x)(cid:2)q(x) − h(x)(cid:3) − s(x).

Ta xét các trường hợp sau: + Trường hợp 1. Nếu ít nhất một trong hai đa thức r(x), s(x) bằng 0, không mất tính tổng quát, ta giả sử r(x) = 0. Khi đó,

...p(x). Điều

...p(x) khi và chỉ khi

...p(x). Suy ra s(x) Vì f (x) ≡ g(x) (cid:0)mod p(x)(cid:1) nên f (x) − g(x) này xảy ra khi và chỉ khi s(x) = 0 (vì deg s(x) < deg p(x)). + Trường hợp 2. Nếu r(x) và s(x) (cid:54)= 0 thì f (x) − g(x) r(x) − s(x) ...p(x). Vì

deg (r(x) − s(x)) = max {deg r(x), deg s(x)} < deg p(x)

(ii) ⇒ (iii). Giả sử f (x) = p(x)h(x) + r(x), g(x) = p(x)k(x) + r(x). Nếu r(x) (cid:54)= 0 thì deg r(x) < deg p(x). Khi đó r(x) = g(x) − p(x)k(x). Do đó, f (x) = g(x) + p(x)t(x) với t(x) = h(x) − k(x). (iii) ⇒ (i). Hiển nhiên.

nên r(x) − s(x) = 0. Do đó r(x) = s(x).

Sau đây, chúng tôi đưa ra một số tính chất của đồng dư đa thức

với môđun một đa thức. Chú ý rằng các đa thức trong phần này đều thuộc A[x].

f1(x) ± f2(x) ± ... ± fk(x) ≡ g1(x) ± g2(x) ± ... ± gk(x) (cid:0)mod p(x)(cid:1); f1(x)f2(x)...fk(x) ≡ g1(x)g2(x)...gk(x) (cid:0)mod p(x)(cid:1);

Định lý 2.1.3. a) Quan hệ đồng dư của các đa thức thuộc A[x] theo môđun đa thức p(x) là quan hệ tương đương trên A[x]; b) Nếu fi(x) ≡ gi(x) (cid:0)mod p(x)(cid:1) với mọi i = 1, k thì

c) Nếu f (x) ≡ g(x) (cid:0)mod p(x)(cid:1) thì f (x)h(x) ≡ g(x)h(x) (cid:0)mod p(x)(cid:1); d) Nếu f (x) ≡ g(x) (cid:0)mod p(x)(cid:1) thì f (x)±h(x) ≡ g(x)±h(x) (cid:0)mod p(x)(cid:1); e) Nếu f (x)+h(x) ≡ g(x) (cid:0)mod p(x)(cid:1) thì f (x) ≡ g(x)−h(x) (cid:0)mod p(x)(cid:1); f) Nếu f (x) ≡ g(x) (cid:0)mod p(x)(cid:1) thì f (x) + h(x)p(x) ≡ g(x) (cid:0)mod p(x)(cid:1); g) Với t là một số tự nhiên bất kì. Nếu f (x) ≡ g(x) (cid:0)mod p(x)(cid:1) thì f t(x) ≡ gt(x) (cid:0)mod p(x)(cid:1); h) Nếu fi(x) ≡ gi(x) (cid:0)mod p(x)(cid:1) với mọi i = 1, k. Khi đó với mọi ui(x) ∈ A[x], i = 1, k thì u1(x)f1(x) + ... + uk(x)fk(x) ≡ u1(x)g1(x) + ... + uk(x)gk(x) (cid:0)mod p(x)(cid:1). i) Nếu f (x) ≡ g(x) (cid:0)mod p(x)(cid:1) thì h(f (x)) ≡ h(g(x)) (cid:0)mod p(x)(cid:1); k) Nếu f (x) ≡ g(x) (cid:0)mod p(x)(cid:1) và t(x) là ước chung của f (x), g(x), p(x) thì

≡

f (x) t(x)

g(x) t(x)

p(x) t(x)

(cid:0)mod (cid:1);

≡

l) Nếu f (x) ≡ g(x) (cid:0)mod p(x)(cid:1) và t(x) là ước chung của f (x), g(x) và (cid:0)p(x), t(x)(cid:1) = 1 thì

f (x) t(x)

g(x) t(x)

(cid:0)mod p(x)(cid:1);

f (x) ≡ g(x) (cid:0)mod t(x)(cid:1);

m) Nếu f (x) ≡ g(x) (cid:0)mod p1(x)(cid:1), f (x) ≡ g(x) (cid:0)mod p2(x)(cid:1), ..., f (x) ≡ g(x) (cid:0)mod pk(x)(cid:1) thì f (x) ≡ g(x) (cid:0)mod p(x)(cid:1) với p(x) ∈ A[x] là bội chung nhỏ nhất của p1(x), ..., pk(x); n) Nếu f (x) ≡ g(x) (cid:0)mod p(x)(cid:1), t(x) là ước của p(x) thì

p) Nếu f (x) ≡ g(x) (cid:0)mod p(x)(cid:1) thì (f (x), p(x)) = (g(x), p(x)).

f (x) ≡ f (x) (cid:0)mod p(x)(cid:1).

Chứng minh. a) + Với mọi f (x) ∈ A[x], hiển nhiên

Do đó quan hệ đồng dư theo môđun đa thức p(x) có tính chất phản xạ. ... p(x). Do đó + Giả sử f (x) ≡ g(x) (cid:0)mod p(x)(cid:1). Suy ra f (x) − g(x)

g(x) − f (x) dư theo môđun đa thức p(x) có tính chất đối xứng. + Với mọi f (x), g(x), h(x) ∈ A[x], giả sử f (x) ≡ g(x) (cid:0)mod p(x)(cid:1) và ...p(x). Do g(x) ≡ h(x) (cid:0)mod p(x)(cid:1). Suy ra f (x) − g(x) đó, (cid:0)f (x) − g(x)(cid:1) + (cid:0)g(x) − h(x)(cid:1) = f (x) − h(x)

...p(x). Kéo theo g(x) ≡ f (x) (cid:0)mod p(x)(cid:1). Vì thế quan hệ đồng

f (x) ≡ h(x) (cid:0)mod p(x)(cid:1).

...p(x), g(x) − h(x) ...p(x). Hay

fi(x) = gi(x) + hi(x)p(x).

Suy ra quan hệ đồng dư theo môđun đa thức p(x) có tính chất bắc cầu. b) Theo giả thiết fi(x) ≡ gi(x) (cid:0)mod p(x)(cid:1) với mọi i = 1, k nên sẽ tồn tại các đa thức hi(x) ∈ A[x], i = 1, k sao cho

± ... ± (cid:0)gk(x) + hk(x)p(x)(cid:1) = [g1(x) ± g2(x) ± ... ± gk(x)]

+ [h1(x) ± h2(x) ± ... ± hk(x)]p(x).

Do đó, f1(x) ± f2(x) ± ... ± fk(x) = (cid:0)g1(x) + h1(x)p(x)(cid:1) ± (cid:0)g2(x) + h2(x)p(x)(cid:1)

f1(x) ± f2(x) ± ... ± fk(x) ≡ g1(x) ± g2(x) ± ... ± gk(x) (cid:0)mod p(x)(cid:1).

Vì thế

ai[g(x)]i (cid:0)mod p(x)(cid:1).

ai[f (x)]i ≡

n (cid:80) i=0

Ta có f1(x)f2(x)...fk(x) = [g1(x) + h1(x)p(x)]...[gk(x) + hk(x)p(x)]. Suy ra f1(x)f2(x)...fk(x) = g1(x)g2(x)...gk(x) + p(x)t(x). Do đó f1(x)f2(x)...fk(x) ≡ g1(x)g2(x)...gk(x) (mod p(x)). Các tính chất c, d, e, f, g, h là hệ quả của tính chất b.

f (x) = g(x) + h(x)p(x).

i) Giả sử h(x) = a0 + a1x + ... + anxn. Vì f (x) ≡ g(x) (cid:0)mod p(x)(cid:1) nên [f (x)]i ≡ [g(x)]i (cid:0)mod p(x)(cid:1), ∀i = 0, n. Suy ra ai[f (x)]i ≡ ai[g(x)]i (cid:0)mod p(x)(cid:1) với ∀i = 0, n. Do đó Vì thế h(cid:0)f (x)(cid:1) ≡ h(cid:0)g(x)(cid:1) (cid:0)mod p(x)(cid:1). k) Vì f (x) ≡ g(x) (mod p(x)) nên tồn tại h(x) sao cho

+ h(x)

f (x) t(x)

g(x) t(x)

p(x) t(x)

Vì t(x) là ước chung của f (x), g(x), p(x) nên ta có

Vậy

≡

f (x) t(x)

g(x) t(x)

p(x) t(x)

(cid:0)mod (cid:1).

l) Vì f (x) ≡ g(x) (mod p(x)) nên f (x) − g(x) = p(x)h(x), trong đó ...t(x). h(x) ∈ A[x]. Do t(x) là ước chung của f (x), g(x) nên f (x) − g(x) ...t(x). Vì (cid:0)p(x), t(x)(cid:1) = 1 nên h(x) Suy ra p(x)h(x) ...t(x).

= m(x) ∈ A[x].

h(x) t(x)

Đặt

≡

= p(x)m(x).

f (x) − g(x) t(x)

p(x)h(x) t(x)

Suy ra

≡

(mod p(x)).

f (x) t(x)

g(x) t(x)

Vậy

...pi(x), ∀i = 1, k. m) Vì f (x) ≡ g(x) (cid:0)mod pi(x)(cid:1), ∀i = 1, k nên f (x)−g(x) Suy ra f (x) − g(x) là bội chung của p1(x), ..., pk(x). Giả sử p(x) là bội ...p(x). chung nhỏ nhất của p1(x), p2(x), ..., pk(x). Khi đó, ta có f (x) − g(x) Vậy f (x) ≡ g(x) (mod p(x)) n) Theo giả thiết f (x) ≡ g(x) (mod p(x)) nên tồn tại h(x) sao cho

f (x) = g(x) + h(x)p(x).

(2.1)

Vì t(x) là ước của p(x) nên tồn tại (cid:96)(x) sao cho

p(x) = t(x)(cid:96)(x).

(2.2)

Thay (2.2) vào (2.1) ta có f (x) = g(x)+h(x)p(x) = g(x)+[h(x)(cid:96)(x)]t(x). Vậy f (x) ≡ g(x) (mod t(x)). p) Giả sử d(x) = (cid:0)f (x), p(x)(cid:1), suy ra d(x)|f (x), d(x)|p(x).

Vì f (x) ≡ g(x) (cid:0)mod p(x)(cid:1) nên

f (x) = g(x) + p(x)h(x).

(2.3)

Suy ra g(x) = f (x) − p(x)h(x). Do đó d(x)|g(x). Từ đó ta thấy d(x) là ước chung của (cid:0)g(x), p(x)(cid:1). Giả sử m(x) là ước chung của g(x), p(x). Từ (2.3) ta có m(x) là ước

của f (x) nên m(x) là ước chung của f (x), p(x).

Mệnh đề 2.1.4. Giả sử m(x) là một đa thức có bậc lớn hơn hoặc bằng 1 và f (x) là đa thức bất kỳ, f (x) ∈ A[x]. Khi đó f (x) đồng dư theo môđun m(x) với đa thức duy nhất r(x) mà deg r(x) < deg m(x) và r(x) gọi là phần dư có bậc nhỏ nhất theo môđun m(x).

f (x) = m(x)q(x) + r(x) với deg r(x) < deg m(x).

Chứng minh. Theo Định lý phép chia với dư, ta có

Do đó f (x) ≡ r(x) (cid:0)mod m(x)(cid:1).

Hiển nhiên ta có mệnh đề sau đây

f (x) ≡ f (r) (cid:0)mod (x − r)(cid:1).

Mệnh đề 2.1.5. Giả sử r ∈ A và f (x) ∈ A[x]. Khi đó

Ví dụ 2.1.6. Cho m(x) = x2 + x + 1 ∈ Z3[x]. Tìm dư trong phép chia f (x) = x5 + 2x3 + x2 + 1 cho m(x).

f (x) = m(x)(x2 + 2x + 2) + (x + 1).

Giải. Ta có

2.2 Tập hợp gồm các lớp tương đương theo quan hệ

đồng dư môđun một đa thức

Vậy x + 1 chính là phần dư có bậc nhỏ nhất của f (x) theo môđun m(x).

Cho p(x) ∈ A[x], p(x) (cid:54)= 0. Khi đó quan hệ đồng dư theo môđun p(x) là một quan hệ tương đương trên A[x]. Với mọi f (x) ∈ A[x], lớp tương đương của f (x) theo quan hệ đồng dư môđun p(x), hay gọi là lớp đồng dư của f (x) môđun p(x), viết [f (x)]p(x) hoặc [f (x)] nếu p(x) đã rõ.

[f (x)]p(x) =

(cid:110) g(x) ∈ A[x] (cid:12) (cid:12) g(x) ≡ f (x) (cid:0)mod p(x)(cid:1)(cid:111)

Chú ý rằng [f (x)]p(x) = [g(x)]p(x) khi và chỉ khi f (x) ≡ g(x) (cid:0)mod p(x)(cid:1).

Định nghĩa 2.2.1. Tập hợp gồm các lớp đồng dư của các đa thức thuộc A[x] theo môđun p(x) được ký hiệu là A[x] (cid:46)(cid:0)p(x)(cid:1).

Với mọi b(x) ∈ [g(x)]p(x) thì b(x) gọi là đại diện của lớp đồng dư [g(x)]p(x). Do đó g(x) là đại diện của [g(x)]p(x). Theo Định lý phép chia với dư, với mọi f (x) ∈ A[x], ta có f (x) = p(x)q(x)+r(x). Giả sử deg p(x) = d thì deg r(x) < d. Suy ra f (x) ≡ r(x) (cid:0)mod p(x)(cid:1) và do đó [f (x)]p(x) = [r(x)]p(x). Do r(x) là duy nhất nên mỗi lớp đồng dư môđun p(x) là được đại diện bởi duy nhất đa thức r(x) ∈ A[x] mà deg r(x) < deg p(x).

Do đó

A[x]

(p(x)) =

[r(x)]p(x)

(cid:46) (cid:110) (cid:111) . (cid:12) (cid:12)r(x) ∈ A[x], deg r(x) < deg p(x)

(cid:46) Mệnh đề sau đây cho ta biết được (cid:12) (cid:12) (cid:12)A[x] (cid:12) (cid:12) (p(x)) (cid:12) dựa vào |A|.

(p(x))

(cid:46)

Mệnh đề 2.2.2. Nếu A có q phần tử và p(x) có bậc là d thì A[x] có qd phần tử.

r(x) = a0 + a1x + ... + ad−1xd−1, ai ∈ A, i = 0, d − 1.

Chứng minh. Giả sử r(x) ∈ A[x], deg r(x) < d và

(cid:46) (cid:110) r(x)(cid:12) (cid:12)r(x) ∈ A[x], deg r(x) < d (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12)A[x] (cid:12) (cid:12) (cid:12) = (p(x))

m(x) = x3 + 1 ∈ Z3(x).

(cid:111)(cid:12) (cid:12) (cid:12). Vì đa thức Ta có r(x) tương ứng với một và chỉ một phần tử (a0, a1, ..., ad−1) ∈ Ad. Suy ra số đa thức r(x) có deg r(x) < d bằng số phần tử của Ad. Do đó (cid:12) (cid:12) (cid:12)A[x](cid:14)(p(x)) (cid:12) (cid:12) (cid:12) = qd. Ví dụ 2.2.3. Cho A = Z(cid:14)3Z = Z3 = (cid:8)0, 1, 2 (mod 3)(cid:9) và

(cid:12) = 33 = 27. (cid:12)Z3[x](cid:14)(m(x))(cid:12)

m(x) = x4 + x2 + 1 ∈ Z2[x], deg m(x) = 4.

Ta có (cid:12) Ví dụ 2.2.4. Cho A = Z(cid:14)2Z = Z2 = (cid:8)0, 1 (mod 2)(cid:9) và

(cid:12)Z2[x](cid:14)(m(x))(cid:12) (cid:12) = 24 = 16. Khi đó Z2[x](cid:14)(m(x)) gồm các phần tử

Ta có (cid:12) sau: [0], [1], [x], [x + 1], [x2], [x2 + 1], [x2 + x], [x2 + x + 1], [x3], [x3 + 1], [x3 + x], [x3 + x + 1], [x3 + x2], [x3 + x2 + 1], [x3 + x2 + x], [x3 + x2 + x + 1].

(cid:46)

2.3 Trường A[x]

(p(x))

(p(x)) định nghĩa phép toán cộng và nhân như sau:

[a(x)]p(x) + [b(x)]p(x) = [a(x) + b(x)]p(x)

(cid:46) Trên A[x]

[a(x)]p(x).[b(x)]p(x) = [a(x)b(x)]p(x),

và

a(x) + b(x) ≡ a(cid:48)(x) + b(cid:48)(x) (cid:0)mod p(x)(cid:1)

Khi đó phép cộng và phép nhân trên không phụ thuộc vào phần tử đại diện. Nghĩa là, nếu [a(x)]p(x) = [a(cid:48)(x)]p(x) và [b(x)]p(x) = [b(cid:48)(x)]p(x), hay a(x) ≡ a(cid:48)(x) (cid:0)mod p(x)(cid:1), b(x) ≡ b(cid:48)(x) (cid:0)mod p(x)(cid:1) thì

a(x)b(x) ≡ a(cid:48)(x)b(cid:48)(x) (cid:0)mod p(x)(cid:1).

và

[a(x) + b(x)]p(x) = [a(cid:48)(x) + b(cid:48)(x)]p(x)

Do đó

[a(x)b(x)]p(x) = [a(cid:48)(x)b(cid:48)(x)]p(x).

và

(p(x)) là một vành giao hoán có đơn vị là 1 := [1]p(x) và

(cid:46) Suy ra A[x]

(p(x)) có phần

(cid:46)

(p(x)) là một trường.

phần tử không là 0 := [0]p(x), với mọi [a(x)](p(x)) ∈ A[x] tử đối là [−a(x)]p(x). (cid:46) Mệnh đề sau đây cho chúng ta điều kiện để A[x]

(cid:46) Mệnh đề 2.3.1. Giả sử p(x) ∈ A[x] là đa thức có bậc lớn hơn hoặc bằng 1. (p(x)) là một trường khi và chỉ khi p(x) là đa thức bất khả Khi đó A[x]

quy trên A.

1 (cid:54) deg r(x), deg s(x) < deg p(x).

Chứng minh. (⇒) Giả sử p(x) không bất khả quy trên A. Khi đó, ta có p(x) = r(x)s(x), với r(x), s(x) ∈ A[x] và

Do đó

[r(x)](p(x)), [s(x)](p(x)) ∈ A[x]

(p(x)), [r(x)]p(x) và [s(x)]p(x) (cid:54)= [0]p(x).

(cid:46)

(p(x)) có ước của

(cid:46) Vì [r(x)]p(x)[s(x)]p(x) = [p(x)]p(x) = [0]p(x) nên A[x]

(p(x)) không là một trường.

(cid:46) không. Suy ra A[x]

(⇐) Giả sử [a(x)]p(x) ∈ A[x]

(p(x)), [a(x)]p(x) (cid:54)= [0]p(x). Khi đó, ta có ... p(x). Do đó (cid:0)a(x), p(x)(cid:1) = 1. Vì p(x) là đa thức bất khả quy trên

a(x) (cid:54) A nên tồn tại r(x), s(x) ∈ A[x] sao cho

a(x)r(x) + p(x)s(x) = 1.

(cid:46)

1 := [1] = [a(x)r(x) + p(x)s(x)]p(x)

= [a(x)r(x)]p(x) + [p(x)s(x)]p(x)

= [a(x)r(x)]p(x)

= [a(x)]p(x)[r(x)]p(x).

Suy ra

(p(x))

(cid:46)

Do đó [r(x)]p(x) là phần tử nghịch đảo của [a(x)]p(x). Suy ra A[x] là một trường. Ví dụ 2.3.2. Q[x](cid:14)(x2 − 5) là một trường vì x2 − 5 là đa thức bất khả quy trên Q. Nếu [a + bx] là phần tử khác [0] thì nghịch đảo của nó là (cid:105) (cid:104) a/d − (b/d)x với d = a2 − 5b2.

Trong các mục tiếp theo của chương này, chúng ta xét các trường hợp

đặc biệt của đồng dư đa thức theo môđun một đa thức. Các kết quả chính

trong các mục này tham khảo ở [2], [6], [7]. Trước hết ta xét đồng dư tuyến

2.4 Đồng dư đa thức với môđun nguyên tố

tính.

Trong phần này, chúng ta xét trường hợp đặc biệt của đồng dư đa thức với môđun đa thức p(x) là số nguyên tố và g(x) = 0. Trong suốt phần này ta luôn giả thiết các đa thức thuộc Z[x].

Định lý sau đây được suy ra từ Định lý phép chia với dư.

f (x) = (x − c)p(x) + mb.

Định lý 2.4.1. Cho f (x) là một đa thức nguyên. Số nguyên c là nghiệm của đồng dư f (x) ≡ 0 (mod m) khi và chỉ khi tồn tại đa thức p(x) và số nguyên b sao cho

f (x) = (x − c)p(x) + a,

Chứng minh. Theo Định lý phép chia với dư, giả sử

trong đó p(x) là một đa thức nguyên và a là một đa thức hằng, nghĩa là một số nguyên. Mặt khác ta có f (c) = a và do đó c là một nghiệm của đồng dư khi và chỉ khi a ≡ 0 (mod m), nghĩa là a = mb. Suy ra điều cần

chứng minh.

f (x) ≡ 0 (mod p),

Ta xét đồng dư đa thức

f (x) = (xp − x)q(x) + r(x) và deg r(x) < p.

trong đó p là một số nguyên tố. Nếu bậc của deg f (x) (cid:62) p, ta có thể làm giảm bậc của f (x) như sau: Chia đa thức f (x) cho xp − x, theo Định lý phép chia với dư sẽ tồn tại hai đa thức q(x) và r(x) sao cho

f (a) ≡ r(a) (mod p),

Theo Định lý Fermat, ta có ap − a ≡ 0 (mod p) và do đó

với mọi số nguyên a. Sử dụng điều này ta chứng minh được kết quả sau.

Định lý 2.4.2. Nếu p là số nguyên tố thì với mọi đồng dư đa thức f (x) ≡ 0 (mod p) sẽ tương đương với đồng dư đa thức r(x) ≡ 0 (mod p), trong đó r(x) là một đa thức có bậc nhỏ hơn p.

Ta có thể chứng minh định lý trên theo phương pháp khác bằng cách

sử dụng bổ đề sau.

Bổ đề 2.4.3. Giả sử n (cid:62) p và n ≡ r (mod (p − 1)), với 1 (cid:54) r (cid:54) p − 1. Khi đó, xn ≡ xr (mod p) với mọi x.

Chứng minh. Vì n ≡ r(cid:0) mod (p − 1)(cid:1) nên n = q(p − 1) + r.

Nếu x (cid:54)≡ 0 (mod p) thì theo Định lý Fermat ta có xp−1 ≡ 1 (mod p). Nếu x ≡ 0 (mod p) thì hiển nhiên xn ≡ xr (mod p).

Sử dụng Bổ đề 2.4.3 ta có thể thay thế tất cả các số hạng có bậc của x lớn hơn bằng p trong đồng dư đa thức f (x) bằng các số hạng tương đương có bậc nhỏ hơn p và nó cho ta đa thức nguyên r(x) có bậc nhỏ hơn p có nghiệm tương tự trong đồng dư đa thức môđun p như đa thức f (x).

Ví dụ 2.4.4. Xét đồng dư x11 + 2x8 + x5 + 3x4 + 4x3 + 1 ≡ 0 (mod 5).

Đặt f (x) = x11 + 2x8 + x5 + 3x4 + 4x3 + 1 chia f (x) cho g(x) = x5 − x. Ta có f (x) = (x6 + 2x3 + x2 + 1)(x5 − x) + 5x4 + 5x3 + x + 1. Do đó đồng dư trên tương đương với 5x4 + 5x3 + x + 1 ≡ 0 (mod 5), suy ra x + 1 ≡ 0 (mod 5) có nghiệm là x ≡ 4 (mod 5).

x11, 2x8, x5 tương ứng bằng x3, 2x4, x. Từ đó ta có

x3 + 2x4 + x + 3x4 + 4x3 + 1 = 5x4 + 5x3 + x + 1 ≡ x + 1 (mod 5).

Theo Bổ đề 2.4.3 vì 11 ≡ 3, 8 ≡ 4, 5 ≡ 1 theo môđun 4. Ta thay

Định lý 2.4.5. Cho p là một số nguyên tố. Các số a1, a2, ..., ak ∈ Z, ai không đồng dư với 0 môđun p với mọi i = 1, k. Khi đó ai, i = 1, k là nghiệm của đồng dư đa thức f (x) ≡ 0 (mod p) nếu và chỉ nếu tồn tại hai đa thức nguyên q(x) và r(x) sao cho: f (x) = (x − a1)(x − a2)...(x − ak)q(x) + pr(x) và deg r(x) < k.

Chứng minh. Nếu tồn tại các đa thức q(x), r(x) thỏa mãn điều kiện của định lý thì f (aj) = pr(aj) ≡ 0 (mod p). Suy ra aj là nghiệm của đồng dư đa thức f (x) ≡ 0 (mod p) với ∀j = 1, k. Điều ngược lại được chứng minh bằng quy nạp theo k. Với k = 1 sẽ tồn tại q(x), r(x) theo Định lý 2.4.1. Giả sử định lý đúng với k − 1 nghiệm. Khi đó tồn tại các đa thức q1(x), r1(x) sao cho

f (x) = (x − a1)(x − a2)...(x − ak−1)q1(x) + pr1(x).

(2.4)

(ak − a1)(ak − a2)...(ak − ak−1)q1(ak) ≡ 0 (mod p).

Vì f (ak) ≡ 0 (mod p) nên ta có

Vì (ak − aj, p) = 1 với j = 1, 2, ..., k − 1 nên ta có thể rút gọn nhân tử (ak − aj) trong đồng dư trên. Khi đó ta có q1(ak) ≡ 0 (mod p). Do đó theo Định lý 2.4.1 sẽ tồn tại đa thức q(x) và số nguyên b sao cho q1(x) = (x − ak)q(x) + pb thay vào biểu thức (2.4) ta tìm được đa thức q(x) và r(x) = b(x−a1)(x−a2)...(x−ak−1)+r1(x) thỏa mãn yêu cầu.

Từ định lý trên ta có ngay hệ quả sau.

(p − 1)! ≡ −1 (mod p).

Định lý 2.4.6. (Định lý Wilson). Nếu p là số nguyên tố thì

Chứng minh. Theo Định lý Fermat, đa thức xp−1 − 1 có các nghiệm 1, 2, ... p − 1 theo môđun p. Do đó tồn tại q(x), r(x) là các đa thức nguyên sao

xp−1 − 1 = (x − 1)(x − 2)...(cid:0)x − (p − 1)(cid:1)q(x) + pr(x), deg r(x) < p − 1.

cho

Bằng so sánh bậc và hệ số lớn nhất của đa thức xp−1 − 1 ta có q(x) = 1. Với x = 0 ta có −1 ≡ (−1)p−1(p − 1)! (mod p). Nếu p là số nguyên tố lẻ ta suy ra (p − 1)! ≡ −1 (mod p), và với p = 2 ta có 1 ≡ −1 (mod 2).

Một đồng dư đa thức với môđun bất kỳ có thể có nhiều nghiệm hơn bậc của đa thức. Ví dụ x2 − 1 ≡ 0 (mod 8) có bốn nghiệm 1, 3, 5, 7. Nếu môđun là số nguyên tố thì số nghiệm không thể vượt quá bậc của đa thức trừ trường hợp tất cả các hạng tử của đa thức chia hết cho p. Từ Định lý

2.4.5 ta có định lý sau.

Định lý 2.4.7. Cho p là một số nguyên tố và f (x) ∈ Z[x] là một đa thức bậc n trong đó không phải tất cả các hạng tử đều chia hết cho p. Khi đó đồng dư f (x) ≡ 0 (mod p) có nhiều nhất n nghiệm.

f (x) = (x − a1)(x − a2)...(x − ak)q1(x) + pr1(x) và deg r1(x) < k.

Chứng minh. Giả sử đồng dư có k nghiệm a1, a2, ..., ak theo Định lý 2.4.2 ta có

Do đó q1(x) (cid:54)= 0 vì theo giả thiết không phải tất cả các hạng tử của f (x) đều chia hết cho p. Suy ra n = deg f (x) = k + deg q1(x) (cid:62) k.

Chú ý rằng một đồng dư đa thức có thể không có nghiệm. Ví dụ đồng dư x2 − 2 ≡ 0 (mod 3) không có nghiệm. Đồng dư xp − x + 1 ≡ 0 (mod p) không có nghiệm nếu p là số nguyên

tố (theo Định lý Fermat)

Định lý sau đây cho ta điều kiện để một đồng dư đa thức có số nghiệm

bằng bậc của đa thức.

Định lý 2.4.8. Cho p là số nguyên tố và giả sử rằng đa thức f (x) có bậc n (cid:54) p và có hệ số cao nhất bằng 1. Theo Định lý phép chia với dư, giả sử xp − x = q(x)f (x) + r(x), trong đó deg r(x) < deg f (x). Khi đó f (x) ≡ 0 (mod p) có n nghiệm nếu và chỉ nếu mọi hệ số của r(x) đều chia hết cho p.

Chú ý 2.4.9. Không làm mất tính tổng quát, ta giả sử hệ số cao nhất của f (x) là 1 vì nếu hệ số cao nhất của f (x) là a, ta có (a, p) = 1. Chọn a(cid:48) sao cho aa(cid:48) ≡ 1 (mod p) và thay f (x) bởi đa thức a(cid:48)f (x) − (a(cid:48)a − 1)xn. Ta có đa thức mới với hệ số cao nhất là 1 với các nghiệm tương tự theo môđun p như đồng dư ban đầu.

Chứng minh. Giả sử q(x) có bậc m, rõ ràng m + n = p và hệ số cao nhất của q(x) bằng 1. Nếu mỗi hệ số của r(x) đều chia hết cho p theo Định lý

q(a)f (a) ≡ ap − a ≡ 0 (mod p) với mỗi số nguyên a.

Fermat ta có

q(a) ≡ 0 (mod p) hoặc f (a) ≡ 0(mod p),

Vì p là số nguyên tố nên ta có

q(x) ≡ 0 (mod p) hoặc f (x) ≡ 0 (mod p).

hay mỗi số nguyên là một nghiệm của

Theo Định lý 2.4.7 đồng dư đầu tiên có nhiều nhất m nghiệm và đồng dư thứ hai có nhiều nhất n nghiệm. Do đó có nhiều nhất m + n = p nghiệm. Vậy đồng dư f (x) ≡ 0 (mod p) có n nghiệm.

Ngược lại, vì r(x) = xp − x − q(x)f (x) nên theo Định lý Fermat mỗi nghiệm của f (x) theo môđun p là nghiệm của r(x) theo môđun p. Vì thế

nếu f (x) có n nghiệm thì r(x) có n nghiệm. Vì deg r(x) < n nên điều này không thể xảy ra trừ trường hợp mọi hệ số của r(x) đều chia hết cho p.

Hệ quả 2.4.10. Giả sử p là số nguyên tố và d|(p − 1). Khi đó, đồng dư xd − 1 ≡ 0 (mod p) có d nghiệm.

yn − 1 = (y − 1)(yn−1 + yn−2 + ... + y + 1)

Chứng minh. Vì d|(p − 1) nên p − 1 = nd. Ta có

q(x) = x

xjd. Theo định lý trên ta có điều cần chứng minh.

n−1 (cid:80) j=0

2.5 Đồng dư đa thức với môđun lũy thừa nguyên tố

và thay y bằng xd ta có xp − x = (xp−1 − 1)x = (xd − 1)q(x), trong đó

Phương pháp chung để giải đồng dư đa thức f (x) ≡ 0 (mod m), khi m là lũy thừa nguyên tố pk là bắt đầu với một nghiệm của đồng dư đa thức theo môđun p và sử dụng nó để tìm một nghiệm hoặc vài nghiệm khác của đồng dư đa thức theo môđun p2. Sử dụng kỹ thuật tương tự, ta sẽ tìm nghiệm của đồng dư đa thức theo môđun pk.

Cho f (x) là một đa thức nguyên và a là một số nguyên. Khi đó, tồn

tại đa thức nguyên g(t) sao cho

f (a + t) = f (a) + f (cid:48)(a)t + t2g(t).

(2.5)

Đây là trường hợp đặc biệt của công thức Taylor. Để chứng minh điều này, dễ thấy f (a + t) là một đa thức theo t với hệ số nguyên, và do đó f (a + t) = A + Bt + t2g(t), trong đó g(t) là một đa thức nguyên. Hệ số A có được bằng cách đặt t = 0 và để tính B ta tính đạo hàm cấp một và cho t = 0.

Ta xét đồng dư

f (x) ≡ 0 (mod p2),

(2.6)

trong đó p là số nguyên tố. Bất kỳ nghiệm a nào của đồng dư trên cũng

là một nghiệm của đồng dư sau

f (x) ≡ 0 (mod p).

(2.7)

Ngược lại, giả sử a là nghiệm của (2.7) và ta cần tìm nghiệm b của (2.6) sao cho b ≡ a (mod p), nghĩa là b = a + pt với số nguyên t nào đó. Theo

f (a + pt) = f (a) + f (cid:48)(a)pt + p2t2g(pt) ≡ f (a) + pf (cid:48)(a)t (mod p2)

(2.5) ta có

f (a) + pf (cid:48)(a)t ≡ 0 (mod p2)

và do đó a + pt là nghiệm của (2.6)

nếu và chỉ nếu

f (cid:48)(a)t ≡ −

(mod p).

f (a) p Nếu (f (cid:48)(a), p) = 1 thì (2.8) có nghiệm duy nhất t ≡ t0 (mod p) và suy ra x ≡ a + pt0 (mod p2) là nghiệm của (2.6) và nó là nghiệm duy nhất thỏa mãn x ≡ a (mod p).

(2.8)

Nếu p|f (cid:48)(a) thì (2.8) có nghiệm nếu và chỉ nếu p2|f (a) và trong trường

x ≡ a + pj (mod p2)

hợp bất kỳ số t nào cũng thỏa mãn (2.8). Do đó

là nghiệm của (2.6) với j = 0, 1, 2, ..., p − 1. Trong trường hợp đó (2.6) có p nghiệm đồng dư với a theo môđun p.

Nếu p|f (cid:48)(a) và p2 (cid:54) |f (a) thì (2.6) không có nghiệm. Từ pk đến pk+1 làm tương tự như trên. Tiếp theo ta có định lý sau.

Định lý 2.5.1. Cho p là số nguyên tố và k là số nguyên dương tùy ý. Giả sử a là nghiệm của phương trình f (x) ≡ 0 (mod pk).

(i) Nếu p (cid:54) |f (cid:48)(a) thì có một nghiệm b của f (x) ≡ 0 (mod pk+1), sao cho b ≡ a (mod pk). Trong đó, b = a + pkt, với t là nghiệm duy nhất của f (cid:48)(a)t ≡ −f (a)/pk (mod p).

f (x) ≡ 0 (mod pk+1)

(ii) Nếu p|f (cid:48)(a) và pk+1|f (a) thì có p nghiệm của đồng dư

mà nó đồng dư với a theo môđun pk. Các nghiệm đó là a + pkj với j = 0, 1, ..., p − 1.

f (x) ≡ 0 (mod pk+1)

(iii) Nếu p|f (cid:48)(a) và pk+1 (cid:54) |f (a) thì không có nghiệm của đồng dư

mà nó đồng dư với a theo môđun pk.

0 ≡ f (b) = f (a + pkt)

= f (a) + f (cid:48)(a)pkt + p2kt2g(pkt) ≡ f (a) + f (cid:48)(a)pkt (mod pk+1)

Chứng minh. Giả sử b là một nghiệm của f (x) ≡ 0 (mod pk+1) mà b đồng dư với a theo môđun pk. Đặt b = a + pkt với t là số nguyên. Theo (2.5) ta có

do 2k (cid:62) k + 1.

Vì f (a) ≡ 0 (mod pk) nên f (a)/pk là một số nguyên và ta có thể chia

đồng dư trên cho pk. Từ đó, ta có

(mod p).

f (cid:48)(a)t ≡

−f (a) pk

(2.9)

Nếu (f (cid:48)(a), p) = 1, hay p (cid:54) |f (cid:48)(a) thì đồng dư này có duy nhất nghiệm. Nếu p|f (cid:48)(a) thì ta phải có f (a)/pk ≡ 0 (mod p) tức là pk+1|f (a). Trong trường hợp này bất kỳ giá trị nào của t cũng là nghiệm của (2.9). Nếu p|f (cid:48)(a) nhưng pk+1 (cid:54) |f (a) thì (2.9) vô nghiệm.

Hệ quả 2.5.2. Cho p là số nguyên tố và k là số nguyên dương tùy ý. Nếu a là nghiệm của f (x) ≡ 0 (mod p) và p (cid:54) |f (cid:48)(a) thì tồn tại một nghiệm b của f (x) ≡ 0 (mod pk) sao cho b ≡ a (mod p)

f (cid:48)(b2) ≡ f (cid:48)(a) (mod p).

Chứng minh. Theo Định lý 2.5.1 (i) tồn tại duy nhất nghiệm b2 của đồng dư f (x) ≡ 0 (mod p2) sao cho b2 ≡ a (mod p). Do đó

Suy ra p (cid:54) |f (cid:48)(b2). Hoàn toàn tương tự, theo định lý trên tồn tại nghiệm duy nhất b3 của f (x) ≡ 0 (mod p3) sao cho b3 ≡ b2 ≡ a (mod p). Cứ tiếp tục như vậy cuối cùng ta có b = bk đồng dư với a theo môđun p.

∗ Tóm lại. Phương pháp chung để tìm tất cả các nghiệm của

f (x) ≡ 0 (mod pk)

như sau:

1. Tìm tất cả các nghiệm của đồng dư

f (x) ≡ 0 (mod p).

(2.10)

2. Chọn một nghiệm bất kỳ của phương trình đồng dư (2.10), giả sử là a1. Khi đó có 0, 1 hoặc p nghiệm của f (x) ≡ 0 (mod p2) đồng dư với a1 theo môđun p. Nếu tồn tại nghiệm đó, ta giải đồng dư tuyến tính f (cid:48)(a1)t ≡ −f (a1)/p (mod p). Nếu phương trình không có nghiệm, bắt đầu với một nghiệm khác a1 của (2.10).

3. Nếu có các nghiệm của f (x) ≡ 0 (mod p2), chọn nghiệm bất kỳ của

f (x) ≡ 0 (mod p3)

đồng dư. Giả sử là a2 và tìm nghiệm tương ứng của

bằng việc giải đồng dư f (cid:48)(a2)t ≡ −f (a2)/p2 (mod p). Làm như vậy với mỗi nghiệm của f (x) ≡ 0 (mod p2). Chú ý rằng vì a2 ≡ a1 (mod p) nên f (cid:48)(a2) ≡ f (cid:48)(a1) (mod p) nên ta không cần tính f (cid:48)(a2).

4. Tiếp tục làm theo cách trên, cuối cùng ta tìm được tất cả các nghiệm

của f (x) ≡ 0 (mod pk).

Nếu trong bất kỳ bước nào của phương pháp trên ta tìm được nghiệm

bội thì ta có thể áp dụng tất cả các bước trên cho mỗi nghiệm.

Tuy nhiên sẽ không có phương pháp chung cho bước đầu tiên để tìm

tất cả các nghiệm của f (x) ≡ 0 (mod p).

x10 ≡ 24 (mod 125).

Ví dụ 2.5.3. Giải phương trình:

f (x) ≡ 0 (mod 5),

Giải. Ta có 125 = 53. Xét phương trình

x5 ≡ x (mod 5) ⇒ f (x) ≡ x2 − 24 ≡ x2 − 4 ≡ (x − 2)(x + 2) (mod 5),

với f (x) = x10 − 24. Theo Định lý Fermat ta có

f (x) ≡ 0 (mod 5) ⇔ (x + 2)(x − 2) ≡ 0 (mod 5) ⇒ x ≡ ±2 (mod 5), f (cid:48)(x) = 10x9...5, với mọi x.

f (±2) = 1000

...25.

x ≡ ±2 + 5k (mod 25), k = 0, 1, 2, 3, 4.

Do đó có 10 nghiệm của phương trình f (x) ≡ 0 (mod 25). là

x ≡ ±2, ±7, ±12, ±17, ±22 (mod 25).

Hay

f (cid:48)(a2) ≡ f (cid:48)(±2) ≡ 0 (mod 25).

Giả sử a2 là một nghiệm trên. Từ

Từ a2 suy ra phương trình f (x) ≡ 0 (mod 125) có 5 nghiệm hoặc

không có nghiệm tùy theo 125 có là ước của f (a2) hay không?

Tiếp theo ta tính f (x) ≡? (mod 125). Với mỗi nghiệm của phương

f (±2) ≡ 0, f (±7) ≡ 100, f (±12) ≡ 75, f (±17) ≡ 50, f (±22) ≡ 25.

trình f (x) ≡ 0 (mod 25). Ta có:

x ≡ ±2 + 25t (mod 125), t = 0, 4.

Do đó chúng ta có các nghiệm của phương trình là

x ≡ 2, 23, 27, 48, 52, 73, 77, 98, 102, 123 (mod 125).

Hay các nghiệm của phương trình là

7x6 + 4x + 12 ≡ 0 (mod 135).

Ví dụ 2.5.4. Giải phương trình đồng dư

7x6 + 4x + 12 ≡ 0 (mod 5)

Giải. Từ 135 = 335, phương trình trên tương đương với hệ

7x6 + 4x + 12 ≡ 0 (mod 33)

  (2.11) 

f (x) = 7x6 + 4x + 12 ≡ 0 (mod 5).

Đặt f (x) = 7x6 + 4x + 12. Xét phương trình

f (x) ≡ 2x2 + 4x + 2 ≡ 0 (mod 5) ⇔ 2(x + 1)2 ≡ 0 (mod 5).

Theo Định lý Fermat ta có x5 ≡ x (mod 5). Do đó ta có

(x + 1)2 ≡ 0 (mod 5) suy ra x ≡ −1 (mod 5).

Vì (2, 5) = 1 nên phương trình trên tương đương với phương trình

x ≡ 0 (mod 3) hoặc x ≡ −1 (mod 3), f (cid:48)(x) = 42x5 + 4.

Xét phương trình f (x) ≡ 0 (mod 33). Trướt hết ta giải phương trình f (x) ≡ 0 (mod 3). Theo Định lý Fermat ta có x3 ≡ x (mod 3). Do đó x6 ≡ x2 (mod 3). Suy ra phương trình trên tương đương với phương trình x2 + x ≡ 0 (mod 3) hay x(x + 1) ≡ 0 (mod 3). Như vậy

Vì f (cid:48)(0) = 4 ≡ 1 (mod 3) và f (cid:48)(−1) = −38 ≡ 1 (mod 3) nên theo hệ quả trên phương trình f (x) ≡ 0 (mod 33) có 2 nghiệm.

(mod 3) ⇒ t ≡ 2 (mod 3).

f (cid:48)(0)t ≡ f (cid:48)(6)t ≡

−f (cid:48)(6) 32

+ Với x1 = 0 và xét phương trình: f (cid:48)(0)t ≡ −f (0)/3 (mod 3). Suy ra t ≡ −4 (mod 3) hay t ≡ 2 (mod 3) ⇒ x2 = 0 + 2.3 = 6 là nghiệm của phương trình f (x) ≡ 0 (mod 32). Tiếp theo ta xét phương trình

Suy ra x3 = 6 + 2.9 = 24 là nghiệm của phương trình f (x) ≡ 0 (mod 33).

f (cid:48)(−1)t ≡

(mod 3) ⇒ t ≡ −5 (mod 3).

−f (−1) 3

+ Với y1 = −1, xét phương trình

f (cid:48)(x) ≡ 0 (mod 32).

Hay t ≡ 1 (mod 3) ⇒ y2 = −1 + 1.3 = 2 là nghiệm của phương trình

f (cid:48)(−1)t ≡ f (cid:48)(2)t ≡

(mod 3) ⇒ t ≡ 2 (mod 3).

−f (2) 9

Tiếp theo ta xét phương trình

f (x) ≡ 0 (mod 33).

Do đó y3 = 2 + 2.9 = 20 là nghiệm của phương trình

Để tìm nghiệm của hệ (2.11) ta sử dụng Định lý Thặng dư Trung Hoa

x ≡ −1 (mod 5)

để giải các hệ

x ≡ 24 (mod 33)

  (2.12) 

x ≡ −1 (mod 5)

và

x ≡ 20 (mod 33).

  (2.13) 

Suy ra, x ≡ 24 (mod 135) hoặc x ≡ 74 (mod 135).

Trong các mục tiếp theo, chúng ta sẽ xét một số trường hợp đặc biệt

2.6 Đồng dư x2 ≡ a (mod m)

của phương trình đồng dư đa thức.

Cho phương trình

x2 ≡ a (mod m).

(2.14)

Mục tiêu của mục này là xét sự tồn tại nghiệm, số nghiệm và cách tìm

nghiệm của phương trình trên.

Trước hết, chúng ta sẽ chỉ ra rằng luôn đưa được phương trình đồng dư

dạng (2.14) về đồng dư dạng tương tự với (a, m) = 1.

Giả sử (a, m) > 1 và p là số nguyên tố chia hết (a, m). Tức là p|a và p|m. Giả sử x là nghiệm của (2.14). Suy ra p|x2. Suy ra p|x. Giả sử x = py. Khi đó (2.14) tương đương p2y2 ≡ a (mod m). Chia cho p ta có

py2 ≡

(mod

a p

m p

(2.15)

Khi đó, ta xét các trường hợp sau

(i) Nếu p2|m và p2|a thì (2.15) tương đương với y2 ≡ a/p2 (mod m/p2), và với mỗi nghiệm y0 của đồng dư trên (nếu có) sẽ có p nghiệm không đồng dư theo môđun m của phương trình ban đầu (2.14). Do đó x ≡ py0 (mod m/p). Nếu (a/p2, m/p2) > 1 ta quay lại quá trình trên

(ii) Nếu p2|m nhưng p2 (cid:54) |a thì (2.15) mâu thuẫn. Do đó, (2.14) không có

nghiệm trong trường hợp này.

cp ≡ 1 (mod

m p

(iii) Nếu p2 (cid:54) |m thì (p, m/p) = 1. Khi đó tồn tại c sao cho

Suy ra (2.15) tương đương với y2 ≡ ca/p (mod m/p). Nghiệm bất kỳ y0 của đồng dư trên cho nghiệm duy nhất x ≡ py0 (mod m) của (2.14). Nếu (ca/p, m/p) > 1 ta có thể quay lại bước trên.

= cp.

a p2 (mod

a p2 ≡ 1.

a p2 ≡

ca p

m p tức là (2.15) tương đương với y2 ≡ a/p2 (mod m/p).

Chú ý rằng nếu p2|a thì

x2 ≡ 36 (mod 45).

Ví dụ 2.6.1. Giải phương trình đồng dư

Giải. Vì (36, 45) = 9 nên x = 3y. Từ đó, ta có phương trình đồng dư tương đương y2 ≡ 4 (mod 5) có nghiệm y ≡ ±2 (mod 5). Do đó x ≡ ±6 (mod 15) nghĩa là 6, 9, 21, 24, 36, 39 là các nghiệm của phương

trình đã cho.

(a, m) = 1. Trước hết ta có định nghĩa sau.

Trong phần này, chúng ta luôn xét phương trình x2 ≡ a (mod m) với

Định nghĩa 2.6.2. Giả sử (a, m) = 1, khi đó a được gọi là thặng dư bậc hai của m nếu phương trình đồng dư x2 ≡ a (mod m) có nghiệm. Nếu phương trình x2 ≡ a (mod m) không có nghiệm thì a được gọi là bất thặng dư bậc hai của m.

Bằng việc phân tích môđun m thành tích các thừa số nguyên tố và sử

dụng Định lý 6.5 [2], ta có thể giải (2.14) bằng cách giải các phương trình

x2 ≡ a (mod pk)

đồng dư dạng

trong đó môđun là lũy thừa nguyên tố. Tương tự như trong mục 2.6. Tuy nhiên vì đạo hàm của x2 là 2x và 2x ≡ 0 (mod 2) nên ta phải xét trường hợp p = 2 và p là số nguyên tố lẻ.

Bổ đề 2.6.3. Nếu p là một số nguyên tố lẻ, (a, p) = 1 và a là thặng dư bậc hai của p thì x2 ≡ a (mod p) có hai nghiệm.

Chứng minh. Theo giả thiết phương trình x2 ≡ a (cid:0)mod p(cid:1) có ít nhất một nghiệm b, hiển nhiên −b cũng là nghiệm và −b (cid:54)≡ b (cid:0)mod p(cid:1) do b (cid:54)≡ 0 (mod p). Theo Định lý 2.4.7 thì đồng dư không thể có nhiều hơn

hai nghiệm.

x2 ≡ a (mod pk)

Định lý 2.6.4. Nếu p là số nguyên tố lẻ và (a, p) = 1 thì

có hai nghiệm nếu a là thặng dư bậc hai của p và không có nghiệm nếu a là bất thặng dư bậc hai của p.

Chứng minh. Đặt f (x) = x2 − a thì f (cid:48)(x) = 2x không chia hết cho p với bất kỳ x (cid:54)≡ 0 (mod p). Từ Hệ quả 2.5.2 và Bổ đề 2.6.3 ta thấy x2 ≡ a (mod pk) có hai nghiệm với mỗi k nếu a là thặng dư bậc hai. Vì bất kì nghiệm nào của thặng dư x2 ≡ a (mod pk) cũng là nghiệm của x2 ≡ a (mod p) và phương trình x2 ≡ a (mod pk) cũng là nghiệm của x2 ≡ a (mod p) nên x2 ≡ a (mod p) có thể không có nghiệm nếu a là bất thặng dư bậc hai.

Trong trường hợp p = 2 ta có định lý sau

Định lý 2.6.5. Giả sử a là số lẻ. Khi đó

(i) Đồng dư x2 ≡ a (mod 2) luôn giải được và chỉ có một nghiệm.

(ii) Đồng dư x2 ≡ a (mod 4) giải được nếu và chỉ nếu a ≡ 1 (mod 4) có

đúng hai nghiệm.

(iii) Đồng dư x2 ≡ a (mod 2k) với k (cid:62) 3 giải được nếu và chỉ nếu a ≡ 1 (mod 8) và có đúng bốn nghiệm. Nếu x0 là nghiệm thì tất cả các nghiệm của đồng dư có dạng ±x0 và ±x0 + 2k−1.

(iii) Giả sử x2 ≡ a (mod 2k) có nghiệm x0. Hiển nhiên x2

0 ≡ a (mod 8) và x0 là số lẻ nên a lẻ. Nhưng bình phương của số lẻ đồng dư với 1

Chứng minh. (i) và (ii) là hiển nhiên.

0 ± 2kx0 + 22k−2 ≡ x2

theo môđun 8 nên a ≡ 1 (mod 8). Đây là điều kiện cần để phương trình x2 ≡ a (mod 2k) giải được. Mặt khác (−x0)2 = x2 0 ≡ a (mod 2k) và 0 ≡ a (mod 2k) vì 2k − 2 (cid:62) k. (±x0 + 2k−1)2 = x2 Có thể dễ dàng chứng minh được bốn số ±x0 và ±x0 + 2k−1 đồng dư theo môđun 2k. Do đó phương trình đồng dư có ít nhất bốn nghiệm.

Bây giờ ta chỉ ra điều kiện của a là đủ để phương trình có ít nhất bốn nghiệm. Chứng minh bằng quy nạp theo k. Trường hợp k = 3 là rõ ràng, vì x2 ≡ 1 (mod 8) có nghiệm x ≡ 1. Giả sử rằng x2 ≡ a (mod 2k) có nghiệm x0. Do đó ±x0 và ±x0 + 2k−1 là các nghiệm của đồng dư và ta sẽ chứng minh rằng một trong các nghiệm trên là nghiệm của đồng dư

x2 ≡ a (mod 2k+1).

0 = a + 2kn, với n là số nguyên. Nếu n chẵn thì x0 là nghiệm của

(2.16)

(x0 + 2k−1)2 = x2

0 + 2kx0 + 22k−2 = a + 2k(n + x0) + 22k−2 ≡ a (mod 2k+1),

Ta biết x2 (2.16). Nếu n lẻ thì

vì n + x0 là chẵn (do n và x0 đều lẻ) và 2k − 2 (cid:62) k + 1 (vì k (cid:62) 3).

Cuối cùng, trong đoạn [1, 2k] có 2k−3 số nguyên a đồng dư với 1 theo

x2 ≡ a (mod 2k)

môđun 8. Với mỗi a ta tìm được bốn nghiệm khác nhau của

và tất cả đều là số lẻ. Do đó, ta có 4.2k−3 = 2k−1 nghiệm. Nhưng sẽ có đúng 2k−1 số lẻ trong khoảng trên không chứa bất kì nghiệm nào. Do đó mỗi phương trình trên có đúng bốn nghiệm.

Kết hợp Định lý 2.6.4 và Định lý 2.6.5 ta có định lý sau chỉ ra số nghiệm

của phương trình đồng dư x2 ≡ a (mod m).

1 ...pkr r

trong đó pi là các số nguyên tố lẻ

x2 ≡ a (mod m)

Định lý 2.6.6. Cho m = 2kpk1 khác nhau và a là số nguyên tố cùng nhau với m. Khi đó

có nghiệm nếu và chỉ nếu a là thặng dư bậc hai của pi với mỗi i và a ≡ 1 (mod 4) trong trường hợp k = 2, a ≡ 1 (mod 8) với k (cid:62) 3. Nếu phương trình đồng dư có nghiệm thì có 2r nghiệm nếu k = 0 hoặc k = 1 và có 2r+1 nghiệm nếu k = 2 và có 2r+2 nghiệm nếu k (cid:62) 3.

Để sử dụng định lý trên ta cần một số tiêu chuẩn để một số là thặng dư bậc hai của số nguyên tố p đã cho. Trước tiên chú ý rằng có nhiều số

thặng dư hoặc bất thặng dư của một số nguyên tố lẻ.

Định lý 2.6.7. Cho p là số nguyên tố lẻ. Khi đó có đúng (p − 1)/2 thặng dư bậc hai của p và (p − 1)/2 bất thặng dư bậc hai của p.

Chứng minh. Tất cả các thặng dư bậc hai được tính bằng bình phương của các phần tử của một hệ thặng dư rút gọn. Phương trình x2 ≡ a (mod p) có đúng hai nghiệm nếu (a, p) = 1. Do đó, số thặng dư bậc hai bằng nửa số phần tử trong hệ thặng dư rút gọn, tức là (p − 1)/2. Tất cả các thặng dư bậc hai ta có thể lấy là 12, 22, ..., [(p − 1)/2]2.

a(p−1)/2 ( mod p)

Bổ đề 2.6.8. Cho p là số nguyên tố lẻ và giả sử a (cid:54)≡ 0 (mod p). Khi đó theo môđun p

(p−1)! ≡

−a(p−1)/2 ( mod p)

nếu a là bất thặng dư bậc hai của p,  

nếu a là thặng dư bậc hai của p 

Chứng minh. Ta có mx ≡ a (cid:0)mod p(cid:1) có nghiệm với mỗi số nguyên m trong đoạn [1, p − 1]. Tức là với mỗi số nguyên m có số nguyên n với n ∈ [1, p − 1] thỏa mãn mn ≡ a (mod p). Nếu x2 ≡ a (mod p) không có nghiệm thì n (cid:54)= m. Nếu nó có nghiệm thì có đúng hai nghiệm có dạng x ≡ m0 (mod p) và x ≡ p − m0 (mod p). Do đó n (cid:54)= m.

Tiếp theo ta xét (p − 1)! = 1.2.3...(p − 1). Nếu x2 ≡ a (mod p) không có nghiệm thì ta có thể ghép p − 1 số thành (p − 1)/2 cặp sao cho tích của hai số trong mỗi cặp đồng dư với a theo môđun p. Nghĩa là (p − 1)! đồng dư với a(p−1)/2 theo môđun p.

Mặc khác nếu đồng dư trên có hai nghiệm m0 và p − m0 ta có thể lấy số khác trong p − 3 số còn lại ghép thành (p − 3)/2 cặp sao cho tích của hai số trong mỗi cặp đồng dư với a theo môđun p.

0 ≡ −a (mod p) nên

(p − 1)! ≡ −a.a(p−3)/2 ≡ −a(p−1)/2 (mod p).

Vì m0(p − m0) ≡ −m2

Chú ý rằng Định lý Wilson với số nguyên tố p > 2 là một trường hợp đặc biệt của Bổ đề 2.6.8, với a = 1 là một thặng dư bậc hai của số nguyên tố p. Kết hợp Định lý Wilson với Bổ đề 2.6.8 ta có định lý sau.

Định lý 2.6.9. (Tiêu chuẩn Euler). Cho p là số nguyên tố lẻ và giả sử (a, p) = 1. Khi đó, a là thặng dư bậc hai của p khi a(p−1)/2 ≡ 1 (mod p) và a là bất thặng dư bậc hai của p khi a(p−1)/2 ≡ −1 (mod p).

Kết quả quan trọng sau đây được suy ra từ Tiêu chuẩn Euler.

Định lý 2.6.10. Cho p là số nguyên tố. Khi đó −1 là thặng dư bậc hai của p nếu và chỉ nếu p = 2 hoặc p ≡ 1 (mod 4).

Chứng minh. −1 là thặng dư bậc hai của 2 vì 12 = 1 ≡ −1 (mod 2). Với số nguyên tố lẻ, ta áp dụng Tiêu chuẩn Euler với chú ý rằng (−1)p−1/2 = 1 nếu và chỉ nếu (p − 1)/2 chẵn. Tức là nếu và chỉ nếu p là số nguyên tố có dạng 4k + 1.

Chú ý rằng Định lý Fermat là hệ quả của Tiêu chuẩn Euler. Bằng việc

ap−1 = (a(p−1)/2)2 ≡ (±1)2 = 1 (mod p).

bình phương ta có

Bây giờ ta tìm nghiệm của x2 ≡ a (mod p). Giả sử a là thặng dư bậc

hai của p. Trong trường hợp p ≡ 3 (mod 4) ta có định lý sau.

Định lý 2.6.11. Cho p là số nguyên tố và giả sử rằng p ≡ 3 (mod 4). Nếu a là thặng dư bậc hai của p thì đồng dư x2 ≡ a (mod p) có hai nghiệm ±a(p+1)/4.

(±a(p+1)/4)2 = a(p+1)/2 = a.a(p−1)/2 ≡ a (mod p).

Chứng minh. Vì a là thặng dư bậc hai nên a(p−1)/2 ≡ 1 (mod p). Suy ra

Chú ý rằng điều kiện a(p−1)/2 ≡ 1 (mod p) là đủ để tính x ≡ a(p+1)/4 (mod p),

2.7 Phương trình đồng dư bậc hai tổng quát

nếu x2 ≡ a (mod p) thì ±x là hai nghiệm, nếu không thì x2 ≡ −a (mod p) và ta có thể kết luận phương trình không có nghiệm.

Xét phương trình đồng dư bậc hai tổng quát có dạng:

ax2 + bx + c ≡ 0 (mod m).

(2.17)

Ta có thể đưa nó về dạng y2 ≡ d (mod m(cid:48)).

Trường hợp đơn giản nhất khi (4a, m) = 1, vì ta có thể nhân hai vế của (2.17) với 4a mà không cần thay đổi môđun m, ta nhận được phương

4a2x2 + 4abx + 4ac ≡ 0 (mod m),

trình đồng dư tương đương sau

(2ax + b)2 ≡ b2 − 4ac (mod m).

khi đó,

Đặt y = 2ax + b ta có kết quả sau.

Định lý 2.7.1. Giả sử (4a, m) = 1. Khi đó nghiệm của phương trình đồng

ax2 + bx + c ≡ 0 (mod m)

dư

y2 ≡ b2 − 4ac (mod m), 2ax ≡ y − b (mod m).

có thể tìm được bằng các phương trình đồng dư sau

m với mỗi nghiệm y.

Vì (2a, m) = 1 nên đồng dư tuyến tính có duy nhất nghiệm theo môđun

8x2 + 5x + 1 ≡ 0 (mod 23).

Ví dụ 2.7.2. Giải phương trình đồng dư sau:

(16x + 5)2 ≡ 52 − 32 = −7 ≡ 16 (mod 23).

Giải. Nhân vế trái của phương trình đã cho với 32 ta được

Do đó 16x + 5 ≡ ±4 (mod 23). Giải 16x ≡ −1 (mod 23) ta được x ≡ 10 và 16x ≡ −9 (mod 23), suy ra x ≡ 21. Vậy 10 và 21 chính là hai nghiệm

gốc của phương trình đồng dư đã cho.

ax2 + bx + c ≡ 0 (mod m)

Định lý 2.7.3. Đặt 4a = a1a2 với a2 là số nguyên tố cùng nhau với m. Khi đó tất cả các nghiệm của đồng dư

y2 ≡ b2 − 4ac (mod a1m), 2ax ≡ y − b (mod a1m).

có thể tìm được bằng các phương trình đồng dư sau

ax2 + bx + c ≡ 0 (mod m)

Chứng minh. Theo giả thiết 4a = a1a2 và (4a, m) = 1. Khi đó (a2, m) = 1. Ta có thể nhân cả hai vế của phương trình đồng dư

với a2 mà không thay đổi môđun m, nhưng nếu nhân với a1 thì môđun m thay đổi thành a1m và nhận được phương trình đồng dư tương đương:

4a2x2 + 4abx + 4ac ≡ 0 ( mod a1m).

(2.18)

Phương trình đồng dư (2.18) tương đương với:

(2ax + b)2 ≡ b2 − 4ac ( mod a1m).

(2.19)

Đặt y = 2ax + b, phương trình đồng dư (2.19) tương đương với các phương

y2 ≡ b2 − 4ac (mod a1m), 2ax ≡ y − b (mod a1m).

trình đồng dư sau:

3x2 + 3x + 2 ≡ 0 (mod 10).

Ví dụ 2.7.4. Giải phương trình đồng dư

Giải. Theo Định lý 2.7.3 ta có (4.3, 10) = 2 (cid:54)= 1 nhưng (3, 10) = 1.

(6x + 3)2 ≡ 32 − 4.3.2 = −15 ≡ 25 (mod 40).

Nhân cả hai vế với 4.3 ta có phương trình đồng dư

Phương trình đồng dư y2 ≡ 25 (mod 40) có 4 nghiệm đồng dư theo môđun 40 là 5, 15, 25, 35. Với mỗi nghiệm y ta có thể giải phương trình đồng dư tuyến tính 6x ≡ y − 3 (mod 40). Phương trình này có các nghiệm x ≡ 7, 2, 17, 12 (mod 20). Nghĩa là các nghiệm của phương trình đồng dư ban đầu là x ≡ 2 và x ≡ 7 (mod 10).

Chương 3

Một số ứng dụng của đồng dư đa

thức trong giải toán sơ cấp

Trong phần này chúng tôi trình bày một số ứng dụng của đồng dư đa thức trong giải toán sơ cấp như tìm đa thức dư khi chia f (x) cho g(x),

chứng minh hai đa thức chia hết cho nhau, xét sự tồn tại nghiệm nguyên

của phương trình, đếm số nghiệm, tìm giá trị bé nhất của tổng,....

Trong toàn bộ phần này vành A cho trước là một trường. Do đó, luôn

3.1 Tìm đa thức dư khi chia đa thức f (x) cho g(x) trong

A[x]

tồn tại phép chia có dư của một đa thức bất kì cho một đa thức khác không trong A[x].

f (x) = g(x)q(x) + r(x).

Phương pháp giải. Theo Định lý phép chia với dư, giả sử

Nếu r(x) (cid:54)= 0 thì deg r(x) < deg g(x). Điều này tương đương với

f (x) ≡ r(x) (cid:0)mod g(x)(cid:1)

(3.1)

Do đó để tìm đa thức dư trong phép chia f (x) cho g(x) ta tìm đa thức r(x) có deg r(x) < deg g(x) và thỏa mãn (3.1).

Để xác định đa thức r(x) ta thường dựa vào đa thức g(x) để xác định số tự nhiên n > 0 sao cho xn ≡ 1 hoặc xn ≡ −1 (mod g(x)) và dựa vào các tính chất của đồng dư đa thức để giải.

Bài toán 3.1.1. Tìm đa thức dư của f (x) chia cho g(x) trong Q[x] với f (x) = (x12 + 2x10 − 2x8 − x4 + 3x3 − 2x2 + 4x − 1)2, g(x) = x2 + x + 1.

t(x) ≡ −4x2 + 5x + 3 (mod g(x)).

Giải. Vì x3 − 1 = (x − 1)(x2 + x + 1) nên x3 ≡ 1 (mod g(x)). Suy ra x12 ≡ 1 (mod g(x)), x10 ≡ x (mod g(x)), x8 ≡ x2 (mod g(x)), x4 ≡ x (mod g(x)). Mặt khác x2 + x + 1 ≡ 0 (mod g(x)) nên x2 ≡ −x − 1 (mod g(x)). Đặt t(x) = x12 + 2x10 − 2x8 − x4 + 3x3 − 2x2 + 4x − 1. Ta có

f (x) ≡ (t(x))2 ≡ (9x + 7)2 (mod g(x)).

Hay t(x) ≡ 9x + 7 (mod g(x)). Suy ra

Do đó f (x) ≡ 45x − 32 (mod g(x)).

Vậy dư trong phép chia f (x) cho g(x) là r(x) = 45x − 32.

Bài toán 3.1.2. Tìm đa thức dư của f (x) chia cho g(x) trong Q[x] với f (x) = (x12 − 2x11 + 3x8 − 5x7 + 2x4 − 7x3 + 1)3, g(x) = x4 − x2 + 1.

x4 ≡ x2 − 1 (mod g(x)). Suy ra

x12 ≡ 1 (mod g(x)); x11 ≡ −x5 ≡ −x(x2 − 1) = x − x3 (mod g(x)); x8 ≡ −x2 (mod g(x)); x7 ≡ −x (mod g(x)).

Giải. Vì x6 + 1 = (x2 + 1)(x4 − x2 + 1) nên x6 ≡ −1 (mod g(x)) và

t(x) ≡ 1 − 2(x − x3) + 3(−x2) − 5(−x) + 2(x2 − 1) − 7x3 + 1

≡ −5x3 − x2 + 3x (cid:0)mod g(x)(cid:1).

Đặt t(x) = x12 − 2x11 + 3x8 − 5x7 + 2x4 − 7x3 + 1. Suy ra

≡ [−5x3 − x2 + 3x]3 (cid:0)mod g(x)(cid:1) ≡ −125x9 − 75x8 + 210x7 + 89x6 − 126x5 − 27x4 + 27x3 (cid:0)mod g(x)(cid:1) ≡ 26x3 + 48x2 − 84x − 62 (cid:0)mod g(x)(cid:1).

Do đó f (x) ≡ [t(x)]3 (cid:0)mod g(x)(cid:1)

r(x) = 26x3 + 48x2 − 84x − 62.

Vậy dư trong phép chia f (x) cho g(x) là

Bài toán 3.1.3. Tìm dư trong phép chia 1 + x + x19 + x199 + x1999 cho 1 − x2.

Giải. Ta có x4 − 1 ≡ 0 (mod (1 − x2)) ⇒ x4 ≡ 1 (mod (1 − x2)), suy ra 1 + x + x19 + x199 + x1999 ≡ 3x3 + x + 1 (mod (1 − x2)). Vì 1 − x2 ≡ 0 (mod (1 − x2)) nên 3x3 + x + 1 ≡ 4x + 1 (mod (1 − x2)).

3.2 Chứng minh đa thức f (x) chia hết cho đa thức g(x)

trong A[x]

Vậy dư trong phép chia 1 + x + x19 + x199 + x1999 cho 1 − x2 là 4x + 1.

g(x) trong A[x] ta chứng minh f (x) ≡ 0 (mod g(x)).

Phương pháp giải. Để chứng minh đa thức f (x) chia hết cho đa thức

Chú ý 3.2.1. Sử dụng đồng dư môđun một đa thức ta dễ dàng chứng

minh được các đồng dư sau: + xn − bn ≡ 0 (mod (x − b)). + xn + bn ≡ 0 (cid:0)mod (x + b)(cid:1) nếu n lẻ. + xn − bn ≡ 0 (cid:0)mod (x + b)(cid:1) nếu n chẵn.

Bài toán 3.2.2. Cho m, n, (cid:96) là các số tự nhiên khác 0. Chứng minh rằng đa thức f (x) = x3m + x3n+1 + x3(cid:96)+2 chia hết cho đa thức g(x) = x2 + x + 1 trong Q[x].

Giải. Vì x3 − 1 = (x − 1)(x2 + x + 1) nên x3 ≡ 1 (mod g(x)). Sử dụng

x3m ≡ (x3)m ≡ 1 (cid:0)mod g(x)(cid:1);

x3n+1 ≡ (x3)nx ≡ x (cid:0)mod g(x)(cid:1); x3(cid:96)+2 ≡ (x3)(cid:96)x2 ≡ x2 (cid:0)mod g(x)(cid:1).

các tính chất của đồng dư đa thức ta có

f (x) = x3m + x3n+1 + x3(cid:96)+2 ≡ 1 + x + x2 (cid:0)mod g(x)(cid:1).

Do đó

f (x) ≡ 0 (cid:0)mod g(x)(cid:1).

Suy ra

Vì thế f (x) = x3m + x3n+1 + x3(cid:96)+2 chia hết cho đa thức g(x) = x2 + x + 1 trong Q[x].

f (x) = (x + 1)2n − x2n − 2x − 1

Bài toán 3.2.3. Cho n là số tự nhiên khác 0. Chứng minh rằng đa thức

chia hết cho các đa thức sau trong Q[x]

a) 2x + 1. b) x + 1. c) x.

Giải.

h(x) = (x + 1)2n − x2n = [(x + 1)n − xn][(x + 1)n + xn].

Cách 1. a) Đặt g(x) = 2x + 1 và h(x) = (x + 1)2n − x2n. Ta có

(x + 1)n ≡ (−1)nxn (mod g(x)).

Vì x + 1 = (2x + 1) − x nên x + 1 ≡ −x (mod g(x)). Suy ra

Ta xét các trường hợp sau + Trường hợp 1. Nếu n chẵn thì (x + 1)n ≡ xn (mod g(x)). Suy ra (x + 1)n − xn ≡ 0 (mod g(x)). Do đó h(x) ≡ 0 (mod g(x)). Vì thế f (x) ≡ 0 (mod g(x)).

+ Trường hợp 2. Nếu n lẻ thì (x + 1)n ≡ −xn (mod g(x)). Suy ra (x + 1)n + xn ≡ 0 (mod g(x)). Do đó h(x) ≡ 0 (mod g(x)). Vậy f (x) ≡ 0 (mod g(x)).

f (x) = (x + 1)2n − x2n − 2x − 1

= (x + 1)2n − (x2n + x) − (x + 1).

b) Đặt g(x) = x + 1. Ta có

x2n ≡ 1 (mod g(x)).

Vì x + 1 ≡ 0 (mod g(x)) nên x ≡ −1 (mod g(x)). Do đó

Kéo theo x2n + x ≡ 1 + x (mod g(x)) ≡ 0 (mod g(x)).

(x + 1)2n − 1 ≡ 0 (mod x). Vậy f (x) ≡ 0 (mod x).

Vậy f (x) ≡ 0 (mod g(x)). c) Ta có x + 1 ≡ 1 (mod x). Do đó (x + 1)2n ≡ 1 (mod x). Suy ra

Cách 2. Theo định lý Bezout nếu f (x) ∈ Q[x] và (x − α) ∈ Q[x] thì dư của phép chia f (x) cho x − α là f (α). Do đó f (x) chia hết cho x − α nếu và chỉ nếu f (α) = 0.

f (x) = (x + 1)2n − x2n − 2x − 1,

Với

−

= f (−1) = f (0) = 0.

1 2

dễ thấy (cid:16) (cid:17)

Vậy f (x) chia hết cho 2x + 1, x + 1, x.

g(x) = xp−1 + xp−2 + ... + x + 1

Bài toán 3.2.4. Cho p là số tự nhiên lớn hơn 1. Chứng minh rằng đa thức f (x) = xpa0 + xpa1+1 + ... + xpap−1+p−1 chia hết cho đa thức

trong Q[x].

Giải. Ta có xp − 1 = (x − 1)(xp−1 + xp−2 + ... + x + 1) ≡ 0 (mod g(x)).

xpa0 = (xp)a0 ≡ 1 (mod g(x)) xpa1+1 = x(xp)a1 ≡ x (mod g(x))

........................................................... xpap−1+p−1 = xp−1(xp)ap−1 ≡ xp−1 (mod g(x))

Suy ra xp ≡ 1 (mod g(x)). Khi đó:

Do đó f (x) = xpa0 +xpa1+1+...+xpap−1+p−1 ≡ 1+x+...+xp−1 (cid:0)mod g(x)(cid:1).

Suy ra f (x) chia hết cho g(x) trong Q[x].

Bài toán 3.2.5. Chứng minh rằng với mọi giá trị của k ∈ N, đa thức (x + 1)2k+1 + xk+2 chia hết cho đa thức x2 + x + 1 trong Q[x].

(x + 1)2k+1 ≡ (−1)2k+1x2(2k+1) (cid:0)mod g(x)(cid:1) ≡ −x4kx2 (cid:0)mod g(x)(cid:1).

Giải. Đặt f (x) = (x + 1)2k+1 + xk+2 và g(x) = x2 + x + 1. Ta có x2 + x + 1 ≡ 0(cid:0)mod g(x)(cid:1). Do đó (x + 1) ≡ −x2 (cid:0)mod g(x)(cid:1). Vì thế (x + 1)t ≡ (−1)tx2t. Suy ra

(x + 1)2k+1 ≡ −x4kx2 (cid:0)mod g(x)(cid:1) ≡ −xkx2 (cid:0)mod g(x)(cid:1) ≡ −xk+2 (cid:0)mod g(x)(cid:1).

Mặt khác x3 − 1 = (x − 1)g(x). Suy ra x3 ≡ 1 (cid:0)mod g(x)(cid:1). Do đó x3k ≡ 1 (cid:0)mod g(x)(cid:1). Vì thế

3.3 Tìm điều kiện để f (x) chia hết cho g(x) (cid:54)= 0 trong A[x]

Vậy f (x) ≡ 0 (cid:0)mod g(x)(cid:1).

Phương pháp giải. Các đa thức f (x) trong dạng này thường chứa tham số ở lũy thừa của ẩn x. Ta cần xác định số m nguyên dương bé nhất sao cho xm ≡ 1 (cid:0)mod g(x)(cid:1) hoặc xm ≡ −1 (cid:0)mod g(x)(cid:1). Chia các tham số có mặt trong các lũy thừa của ẩn của f (x) cho m. Giả sử n = mq + r, r = 0, m − 1 xét các trường hợp của các số dư r và sử

dụng tính chất của đồng dư đa thức theo môđun môt đa thức ta sẽ xác định được điều kiện của tham số để f (x) ≡ 0 (cid:0)mod g(x)(cid:1).

f (x) = x3m − x3n+1 + x3(cid:96)+2

Bài toán 3.3.1. Tìm điểu kiện của m, n, (cid:96) ∈ N∗ để đa thức

chia hết cho đa thức g(x) = x2 − x + 1 trong Q[x].

Giải. Vì x3 + 1 = (x + 1)(x2 − x + 1) nên x3 ≡ −1 (mod g(x)). Sử

x3m ≡ (x3)m ≡ (−1)m (mod g(x));

x3n+1 ≡ (x3)nx ≡ (−1)nx (mod g(x));

x3(cid:96)+2 ≡ (x3)(cid:96)x2 ≡ (−1)(cid:96)x2 (mod g(x)).

dụng các tính chất của đồng dư đa thức ta có

f (x) = x3m − x3n+1 + x3(cid:96)+2

≡ (−1)m − (−1)nx + (−1)(cid:96)x2 (mod g(x)).

Do đó

h(x) = (−1)m − (−1)nx + (−1)(cid:96)x2 ≡ 0 (mod g(x)).

Suy ra f (x) ≡ 0 (mod g(x)) khi và chỉ khi

Vậy m, n, (cid:96) cùng chẵn hoặc m, n, (cid:96) cùng lẻ thì đa thức f (x) chia hết cho đa thức g(x) trong Q[x].

f (x) = x3m + x3n+1 + x3(cid:96)+2

Bài toán 3.3.2. Tìm điều kiện của m, n, (cid:96) ∈ N ∗ để đa thức

chia hết cho x4 + x2 + 1 trong Q[x].

Giải. Đặt p(x) = x4 + x2 + 1. Ta có x6 − 1 = (x2 − 1)(x4 + x2 + 1). Do

đó x6 ≡ 1 (mod p(x)).

f (x) ≡ x3(2m1+r)+x3(2n1+s)+1+x3(2(cid:96)1+t)+2 ≡ x3r+x3s+1+x3t+2 (mod p(x)).

Giả sử m = 2m1 + r; n = 2n1 + s; (cid:96) = 2(cid:96)1 + t, với r, s, t = 0, 1

Ta xét các trường hợp sau:

f (x) ≡ x3r + x3s+1 + x3t+2 ≡ 1 + x + x2 (mod p(x)).

+ Trường hợp 1. r = 0, s = 0, t = 0 thì

Suy ra f (x) không chia hết cho p(x).

f (x) ≡ 1 + x + x5 (mod p(x)).

+ Trường hợp 2. Với r = 0, s = 0, t = 1 thì

f (x) ≡ 1 + x − x − x3 (mod p(x)) ≡ 1 − x3 (mod p(x)).

Vì x4 + x2 + 1 ≡ 0 (mod p(x)) nên x4 ≡ −x2 − 1 (mod p(x)). Suy ra x5 ≡ −x3 − x (mod p(x)). Do đó

Vậy f (x) không chia hết cho p(x).

f (x) ≡ 1 + x2 + x4 (mod p(x)).

+ Trường hợp 3. Với r = 0, s = 1, t = 0 thì

Hay f (x) chia hết cho p(x).

f (x) ≡ 1 + x4 + x5 (mod p(x)).

+ Trường hợp 4. Với r = 0, s = 1, t = 1 thì

Do đó f (x) ≡ 1 − x2 − 1 − x3 − x (mod p(x)) ≡ −x3 − x2 − x (mod p(x)). Suy ra f (x) không chia hết cho p(x).

f (x) ≡ x3 + x2 + x (mod p(x)).

+ Trường hợp 5. Với r = 1, s = 0, t = 0 thì

Hay f (x) không chia hết cho p(x).

f (x) ≡ x3 + x + x5 (mod p(x)).

+ Trường hợp 6. Với r = 1, s = 0, t = 1 thì

Hay f (x) ≡ x3 + x − x3 − x (mod p(x)) ≡ 0 (mod p(x)). Suy ra f (x) chia hết cho p(x).

f (x) ≡ x4 + x3 + x2 (mod p(x)) ≡ x3 − 1 (mod p(x)).

+ Trường hợp 7. Với r = 1, s = 1, t = 0 thì

Suy ra f (x) không chia hết cho p(x).

f (x) ≡ x3 + x4 + x5 (mod p(x)).

+ Trường hợp 8. Với r = 1, s = 1, t = 1 thì

Hay f (x) ≡ x3 − x2 − 1 − x − x3 (mod p(x)) ≡ −x2 − x − 1 (mod p(x)). Suy ra f (x) không chia hết cho p(x).

f (x) = x3m + x3n+1 + x3(cid:96)+2

Vậy với m chẵn, n lẻ và (cid:96) chẵn hoặc m lẻ, n chẵn và (cid:96) lẻ thì

chia hết cho x4 + x2 + 1 trong Q[x].

f (x) = (x + 1)m − xm − 1

Bài toán 3.3.3. Tìm điều kiện của m ∈ N để đa thức

chia hết cho x2 + x + 1 trong Q[x].

x3 ≡ 1 (cid:0)mod g(x)(cid:1). (cid:17) Suy ra x6 ≡ 1 (cid:0)mod g(x)

Giải. Đặt g(x) = x2 + x + 1. Vì x3 − 1 = (x − 1)(x2 + x + 1) nên

(cid:17) và x + 1 ≡ −x2 (cid:0)mod g(x)

f (x) = (x + 1)m − xm − 1

= (x + 1)6k − x6k − 1 ≡ −1 (cid:0)mod g(x)(cid:1).

Xét m = 6k + r, r = 0, 1, 2, 3, 4, 5. + Với m = 6k ta có

Suy ra f (x) không chia hết cho g(x)

f (x) = (x + 1)m − xm − 1

= (x + 1)6k+1 − x6k+1 − 1 ≡ (x + 1)(x + 1)6k − xx6k − 1

≡ (x + 1) − x − 1 = 0 (cid:0)mod g(x)(cid:1).

+ Với m = 6k + 1 ta có

f (x) = (x + 1)m − xm − 1

= (x + 1)6k+2 − x6k+2 − 1 ≡ (x + 1)2(x + 1)6k − x2.x6k − 1 ≡ (x + 1)2 − x2 − 1 ≡ 2x (cid:0)mod g(x)(cid:1).

Suy ra f (x) chia hết cho g(x). + Với m = 6k + 2 ta có

Suy ra f (x) không chia hết cho g(x).

f (x) = (x + 1)m − xm − 1

= (x + 1)6k+3 − x6k+3 − 1 ≡ (x + 1)3(x + 1)6k − x3.x6k − 1 ≡ −3 (cid:0)mod g(x)(cid:1).

+ Với m = 6k + 3 ta có

Suy ra f (x) không chia hết cho g(x).

f (x) = (x + 1)m − xm − 1

= (x + 1)6k+4 − x6k+4 − 1 ≡ (x + 1)4(x + 1)6k − x4.x6k − 1 ≡ x2 − x − 1 (cid:0)mod g(x)(cid:1).

+ Với m = 6k + 4 ta có

Suy ra f (x) không chia hết cho g(x).

f (x) = (x + 1)m − xm − 1

= (x + 1)6k+5 − x6k+5 − 1 ≡ (x + 1)5(x + 1)6k − x5.x6k − 1 ≡ −x2 − x − 1 (cid:0)mod g(x)(cid:1).

+ Với m = 6k + 5 ta có

Suy ra f (x) chia hết cho g(x).

Vậy với m = 6k + 1 hoặc m = 6k + 5 thì f (x) chia hết cho g(x).

Bài toán 3.3.4. Tìm tất cả các giá trị của n sao cho x2n + xn + 1 chia hết cho x2 + x + 1 trong Q[x].

Giải. Đặt g(x) = x2 + x + 1. Ta có x3 ≡ 1 (cid:0)mod g(x)(cid:1). Ta xét n = 3k + r với r = 0, 1, 2. + Với n = 3k ta có f (x) = x6k + x3k + 1 ≡ 1 (cid:0)mod g(x)(cid:1). Suy ra f (x)

không chia hết cho g(x).

f (x) = x2(3k+1) + x3k+1 + 1

= x6k+2 + x3k+1 + 1 ≡ x2 + x + 1 (cid:0)mod g(x)(cid:1) ≡ 0 (cid:0)mod g(x)(cid:1).

+ Với n = 3k + 1, ta có

f (x) = x2(3k+2) + x3k+2 + 1

= x6k+4 + x3k+2 + 1 ≡ x2 + x + 1 (cid:0)mod g(x)(cid:1) ≡ 0 (cid:0)mod g(x)(cid:1).

Suy ra f (x) chia hết cho g(x). + Với n = 3k + 2, ta có

Suy ra f (x) chia hết cho g(x).

Vậy f (x) chia hết cho g(x) khi và chỉ khi n có dạng 3k + 1 hoặc 3k + 2.

...g(x) và f (cid:48)(x)

Chú ý 3.3.5. Giả sử f (x), g(x) ∈ A[x], (cid:0)g(x), g(cid:48)(x)(cid:1) = 1. Khi đó f (x) ...g(x) (với f (cid:48)(x) là đạo chia hết cho [g(x)]2 khi và chỉ khi f (x) hàm của f (x)).

f (x) = (x + 1)m − xm − 1

Bài toán 3.3.6. Tìm điều kiện của m ∈ N để đa thức

chia hết cho (x2 + x + 1)2 trong Q[x].

(g(x), g(cid:48)(x)) = 1.

Giải. Đặt g(x) = x2 + x + 1. Ta có g(cid:48)(x) = 2x + 1. Vì thế

f (cid:48)(x) = m(x + 1)m−1 − mxm−1

Suy ra f (x) chia hết cho [g(x)]2 khi và chỉ khi f (x) và f (cid:48)(x) chia hết cho g(x). Theo lời giải của bài toán 3.3.3 ta đã chỉ ra f (x) chia hết cho g(x) khi m = 6k + 1 hoặc m = 6k + 5. Do đó ta xét

với m = 6k + 1 hoặc m = 6k + 5.

+ Với m = 6k + 1 ta có f (cid:48)(x) = (6k + 1)(x + 1)6k − (6k + 1)x6k. Vì x3 ≡ 1 (cid:0)mod g(x)(cid:1) nên x6k ≡ 1 (cid:0)mod g(x)(cid:1), x + 1 ≡ −x2 (cid:0)mod g(x)(cid:1). Suy ra (x + 1)6k ≡ 1 (cid:0)mod g(x)(cid:1). Do đó f (cid:48)(x) ≡ 0 (cid:0)mod g(x)(cid:1). Suy ra f (cid:48)(x) chia hết cho g(x).

+ Với m = 6k + 5 ta có f (cid:48)(x) = (6k + 5)(x + 1)6k+4 − (6k + 5)x6k+4.

(x + 1)6k+4 ≡ (−1)6k+4x2(6k+4) (cid:0)mod g(x)(cid:1) ≡ x12kx8 (cid:0)mod g(x)(cid:1) ≡ x2 (cid:0)mod g(x)(cid:1). x6k+4 ≡ x (cid:0)mod g(x)(cid:1). Suy ra f (cid:48)(x) ≡ (6k + 5)(x2 − x) (cid:0)mod g(x)(cid:1). Hay f (cid:48)(x) không chia hết cho g(x).

Vì x + 1 ≡ −x2 (cid:0)mod g(x)(cid:1) nên

Vậy với m = 6k + 1 thì f (x) chia hết cho [g(x)]2.

f (x) = (x + 1)m + xm + 1

Bài toán 3.3.7. Tìm điều kiện của m ∈ N để đa thức

chia hết cho (x2 + x + 1)2 trong Q[x].

(g(x), g(cid:48)(x)) = 1.

Giải. Đặt g(x) = x2 + x + 1 ta có g(cid:48)(x) = 2x + 1. Suy ra

Do đó f (x) chia hết cho [g(x)]2 khi và chỉ khi f (x) và f (cid:48)(x) chia hết cho g(x). Trước hết ta xét điều kiện để f (x) ...g(x).

x6 ≡ 1 (cid:0)mod g(x)(cid:1) và (x + 1) ≡ −x2 (cid:0)mod g(x)(cid:1). Xét m = 6k + r, r = 0, 1, 2, 3, 4, 5. + Với m = 6k ta có

f (x) = (x + 1)m + xm + 1 = (x + 1)6k + x6k + 1 ≡ 3 (cid:0)mod g(x)(cid:1).

Ta có x3 − 1 = (x − 1)(x2 + x + 1). Suy ra x3 ≡ 1 (cid:0)mod g(x)(cid:1). Do đó

f (x) = (x + 1)m + xm + 1

= (x + 1)6k+1 + x6k+1 + 1 ≡ (x + 1)(x + 1)6k + xx6k + 1 ≡ 2x + 2 (cid:0)mod g(x)(cid:1).

Suy ra f (x) không chia hết cho g(x). + Với m = 6k + 1 ta có

f (x) = (x + 1)m + xm + 1

= (x + 1)6k+2 + x6k+2 + 1 ≡ (x + 1)2(x + 1)6k + x2.x6k + 1 ≡ x2 + x + 1 ≡ 0 (cid:0)mod g(x)(cid:1).

Suy ra f (x) không chia hết cho g(x). + Với m = 6k + 2 ta có

f (x) = (x + 1)m + xm + 1

= (x + 1)6k+3 + x6k+3 + 1 ≡ (x + 1)3(x + 1)6k + x3.x6k + 1 ≡ 1 (cid:0)mod g(x)(cid:1).

Suy ra f (x) chia hết cho g(x) với m = 6k + 2. + Với m = 6k + 3 ta có

f (x) = (x + 1)m + xm + 1

= (x + 1)6k+4 + x6k+4 + 1 ≡ (x + 1)4(x + 1)6k + x4.x6k + 1 ≡ 0 (cid:0)mod g(x)(cid:1).

Suy ra f (x) không chia hết cho g(x). + Với m = 6k + 4 ta có

f (x) = (x + 1)m + xm + 1

= (x + 1)6k+5 + x6k+5 + 1 ≡ x2 − x + 1 (cid:0)mod g(x)(cid:1).

Suy ra f (x) chia hết cho g(x). + Với m = 6k + 5 ta có

Suy ra f (x) không chia hết cho g(x).

f (cid:48)(x) = (6k + 2)(x + 1)6k+1 + (6k + 2)x6k+1

≡ (6k + 2)(x + 1) + (6k + 2)x (cid:0)mod g(x)(cid:1) ≡ (6k + 2)(2x + 1) (cid:0)mod g(x)(cid:1).

Vậy với m = 6k + 2 hoặc m = 6k + 4 thì f (x) chia hết cho g(x). Bây giờ, ta xét f (cid:48)(x) = m(x + 1)m−1 + mxm−1, với m = 6k + 2 hoặc m = 6k + 4. + Với m = 6k + 2 ta có

f (cid:48)(x) = (6k + 4)(x + 1)6k+3 + (6k + 4)x6k+3 Vì x2 + x + 1 ≡ 0 (cid:0)mod g(x)(cid:1) nên (x + 1) ≡ −x2 (cid:0)mod g(x)(cid:1). Suy ra (x + 1)6k ≡ (−1)6kx12k (cid:0)mod g(x)(cid:1) ≡ 1 (cid:0)mod g(x)(cid:1). Do đó

(x + 1)6k+3 ≡ (x + 1)3 (cid:0)mod g(x)(cid:1) ≡ (−1)3x6 (cid:0)mod g(x)(cid:1) ≡ −1 (cid:0)mod g(x)(cid:1).

Suy ra f (cid:48)(x) không chia hết cho g(x). + Với m = 6k + 4 ta có

Kéo theo f (cid:48)(x) ≡ −(6k + 4) + (6k + 4) (cid:0)mod g(x)(cid:1) ≡ 0 (cid:0)mod g(x)(cid:1). Vậy f (cid:48)(x) chia hết cho g(x).

Vậy với m = 6k + 4 thì f (x) chia hết cho [g(x)]2.

3.4 Bài toán về nghiệm của đa thức

Phương pháp giải. Ta áp dụng nhận xét sau Giả sử K là một vành giao hoán chứa A. Nếu f (x) ≡ 0 (mod p(x)) và α ∈ K là nghiệm của p(x) trong K thì α cũng là nghiệm của f (x) trong K.

Nếu f (x) là đa thức có hệ số nguyên và r ∈ Z là nghiệm của f (x) thì f (x) ≡ 0 (mod m) với mọi số nguyên dương m. Do đó, nếu tồn tại m nguyên dương sao cho phương trình f (x) ≡ 0 (mod m) không có nghiệm

thì đa thức không có nghiệm nguyên.

f (x) = xkn1 + xkn2+1 + ... + xknk+k−1,

Bài toán 3.4.1. Cho k là số tự nhiên chẵn và

trong đó ni là số tự nhiên khác 0 với mọi i = 1, k.

Hỏi đa thức f (x) có nghiệm hữu tỉ khác 0 hay không?

Giải. Ta có f (x) = xkn1 + xkn2+1 + ... + xknk+k−1 ≡ 0 (mod p(x)). với p(x) = xk−1 + xk−2 + ... + x + 1 và ni (cid:54)= 0 với mọi i = 1, k. Vì k chẵn nên p(x) = xk−1 + xk−2 + ... + x + 1 ≡ 0 (cid:0)mod (x + 1)(cid:1).

Mặc khác đa thức x + 1 có nghiệm x = −1 nên p(x) có nghiệm x = −1. Do đó đa thức f (x) = xkn1 + xkn2+1 + ... + xknk+k−1 có nghiệm x = −1.

Bài toán 3.4.2. Cho các số tự nhiên m, n, k. Hãy tìm nghiệm nguyên của đa thức f (x) = 3x3n+1 + 6x3m+2 − 12xk − 5.

Giải. Xét phương trình

f (x) = 3x3n+1 + 6x3m+2 − 12xk − 5 ≡ 0 (mod 3).

(3.2)

3.5 Một số bài toán khác

Vì f (x) ≡ 1 (mod 3) nên phương trình (3.2) không có nghiệm nguyên. Do đó, đa thức f (x) = 3x3n+1 + 6x3m+2 − 12xk − 5 cũng không có nghiệm nguyên.

Bài toán 3.5.1. Xác định ba chữ số tận cùng của số n với

n = 3 × 7 × 11 × 15 × ... × 2011

(3.3)

n = 3(4.1 + 3)(4.2 + 3)...(4.502 + 3)

.3 (mod 8)

≡ (3.7)(3.7)...(3.7) (cid:125)

Giải. Dễ thấy n là số lẻ. Gọi a là ba chữ số tận cùng của n. Khi đó n ≡ a (mod 1000). Vì 15, 35, 55 là ba số hạng trong tích (3.3) nên ...125. Do đó a chỉ có thể là những số ...125 và 1000 = 8 × 125. Suy ra a n ...8. Vì ...1000 tương đương với (n − a) 125, 375, 625, 875. Kéo theo (n − a) thế n ≡ a (mod 8). Tiếp theo lấy mônđun 8 các số hạng của n ta được

.3 (mod 8)

.5.3 (mod 8)

≡ 5.5.....5 (cid:124) (cid:123)(cid:122) (cid:125) 251 số ≡ 1.1....1 (cid:124) (cid:123)(cid:122) (cid:125) 125 số ≡ 7 (mod 8).

(cid:124) (cid:123)(cid:122) 251 cặp

Mặt khác trong các số 125, 375, 625, 875 chỉ có duy nhất số 375 là đồng dư với 7 theo môđun 8. Vậy 375 là ba chữ số tận cùng của n.

Bài toán 3.5.2. (Olympic 10-30/4-2008) Tìm tất cả các số nguyên dương m thỏa mãn điều kiện với mọi a, b ∈ Z, a2 ≡ b2 (mod m) thì

a ≡ ±b (mod m).

(3.4)

Giải.

(a − b)(a + b) = a2 − b2 ≡ 0 (mod m).

+ Với m = 1 hoặc m là số nguyên tố thì với mọi a, b ∈ Z, a2 ≡ b2 (mod m) ta có a ≡ ±b (mod m). Thật vậy, ta có Nếu m = 1 thì hiển nhiên (3.4) đúng. Nếu m là số nguyên tố, với a, b ∈ Z thỏa a2 ≡ b2 (mod m) ta có

...m hoặc a + b ...m. Do đó a ≡ ±b (mod m).

Điều này suy ra a − b + Với m (cid:54)= 1 và m không là số nguyên tố. Ta chứng minh số m cần tìm là m = 2p trong đó p là số nguyên tố lẻ. Thật vậy, giả sử (3.4) đúng. Vì m không là số nguyên tố nên ta có m = xy, x, y (cid:54)= 1. Đặt a = x+y, b = x−y. Khi đó a2 − b2 = 4xy = 4m ≡ 0 (mod m). Suy ra a ≡ ±b (mod m) hay ...m 2y = a − b ≡ 0 (mod m) hoặc 2x = a + b ≡ 0 (mod m). Do đó 2x

...m, với m = xy suy ra x = 2 hoặc y = 2. Hay m = 2n, n (cid:54)= 1. Hơn hoặc 2y nữa nếu n là hợp số thì n = kt. Suy ra m = 2kt, k, t (cid:54)= 1 theo trên ta suy ra t = 2 hay m = 4k mâu thuẫn với (3.4) (chọn a = 2k, b = 0). Vậy n = p là số nguyên tố. Hơn nữa nếu p = 2 thì m = 4 không thỏa mãn (3.4). Vậy p là số nguyên tố lẻ.

Ngược lại, giả sử m = 2p với p là số nguyên tố lẻ. Khi đó, theo giả thiết ...2p ...2 và (a − b)(a + b) ...p. Do đó a + b

ta có a2 − b2...2p suy ra (a − b)(a + b) ...2p hay a ≡ ±b (mod m). hoặc a − b

Vậy m = 1, m = 2p hoặc m nguyên tố là những giá trị cần tìm.

Bài toán 3.5.3. (Vietnam MO 2004, Bảng A). Ký hiệu S(n) là tổng tất cả các chữ số của n trong cơ sở 10. Xét tất cả các số nguyên dương n thỏa mãn n là bội của 2003, tìm giá trị bé nhất có thể có của S(n).

Nhận xét 3.5.4. x2 ≡ −1 (mod p) có nghiệm khi và chỉ khi p = 4k + 1.

Giải. Đặt p = 2003, p là số nguyên tố. Rõ ràng S(n) > 1 vì 10k không chia hết cho p. Giả sử tồn tại n là bội của p và S(n) = 2. Suy ra tồn tại k để 10k ≡ −1 (mod p). Chú ý rằng vì 210 = 1024 ≡ 107 (mod p) nên (25k)2 = 210k ≡ 107k ≡ (10k)7 ≡ −1 (mod p). Vậy −1 là thặng dư bậc 2 môđun p. Mâu thuẫn vì p không có dạng 4k + 1.

Tiếp theo ta chứng minh tồn tại n là bội của p mà S(n) = 3. Ta có 107 ≡ 210 (mod p). Suy ra 2.10700 ≡ 21001 = 2(p−1)/2 ≡ −1 (mod p). Vậy n = 2.10700 + 1 là bội của p và S(n) = 3. Vậy giá trị nhỏ nhất của S(n) = 3.

Nhận xét 3.5.5. Cho p là số nguyên tố lẻ (p, 3) = 1. Gọi n là số các số là bội của 3 trong khoảng (p/2; p). Khi đó 3(p−1)/2 ≡ (−1)n ( mod p). Từ đó, ta có hệ quả sau:

3 là số thặng dư bậc hai (mod p) khi và chỉ khi p = 12t ± 1. Bài toán 3.5.6. Xét số Fecma F = Fn = 22n + 1, n (cid:62) 1. Chứng minh rằng F là số nguyên tố khi và chỉ khi 3(F −1)/2 + 1

Nếu p = 6k ± 1 là số nguyên tố thì 3(p−1)/2 ≡ (−1)k ( mod p). Suy ra

...F .

Giải. Dễ thấy F không có dạng 12k ± 1. Do đó nếu F là số nguyên tố thì 3 là số bất thặng dư bậc 2 môđun F . Vậy 3(F −1)/2 ≡ −1 (mod F ) tức là 3(F −1)/2 + 1 ...F .

Ngược lại giả sử 3(F −1)/2 ≡ −1 (mod F ). Gọi h là cấp của 3 (mod F ). Khi đó h|(F −1) = 22n. Vậy h = 2t, t (cid:54) 2n. Nếu t (cid:54) 2n −1 thì h|(F −1)/2. Do đó 3(F −1)/2 ≡ 1 (mod F ). Điều này mâu thuẫn với điều đã giả sử. Vậy t = 2n khi và chỉ khi h = F − 1. Vì h|ϕ(F ) nên (F − 1)|ϕ(F ). Suy ra F − 1 = ϕ(F ). Vậy F là số nguyên tố.

Bài toán 3.5.7. Cho hai số nguyên dương p, q nguyên tố cùng nhau. Chứng minh rằng tồn tại số nguyên k sao cho (pq − 1)nk + 1 là hợp số với mọi số nguyên dương n.

Giải. Vì (p, q) = 1 nên theo Định lý Thặng dư Trung Hoa, tồn tại số

k ≡ 1 (mod p)

nguyên k thỏa mãn:

k ≡ −1 (mod q).

 



...q.

Khi đó - Nếu n chẵn thì (pq − 1)n ≡ 1 (mod q). Do đó (pq − 1)nk ≡ −1 (mod q). Vì thế (pq − 1)nk + 1 - Nếu n lẻ thì (pq − 1)n ≡ −1 (mod p). Do đó (pq − 1)nk ≡ −1 (mod p). Vì thế (pq − 1)nk + 1 ...p.

Vậy (pq − 1)nk + 1 là hợp số với mọi số nguyên dương n.

Nhận xét 3.5.8. Sử dụng Định lý Thặng dư Trung Hoa ta dễ dàng chứng

(pq − 1)nk + 1

minh được bài toán trên. Vấn đề ở đây là để chứng minh

k ≡ 1 (mod p)

là hợp số ta chỉ cần chỉ ra (pq − 1)nk + 1 chia hết cho p hoặc q. Khi phân tích tính chẵn, lẻ của n ta dễ dàng thấy sự xuất hiện của hệ

k ≡ −1 (mod q).

 

2 ...pαk

1 pα2

k . Trong đó p1, p2, ..., pk



Bài toán 3.5.9. Cho số nguyên dương n = pα1 là các số nguyên tố đôi một khác nhau. Tìm số nghiệm của phương trình x2 + x ≡ 0 (mod n)

Giải. Ta có x2 + x ≡ 0 (mod n) khi và chỉ khi x(x + 1) ≡ 0 (mod pαi i ) i ) với mọi i ) với mọi i = 1, k. Theo Định lý Thặng dư

với mọi i = 1, k. Điều này xảy ra khi và chỉ khi x ≡ 0 (mod pαi i = 1, k hoặc x ≡ −1 (mod pαi Trung Hoa mỗi hệ phương trình

x ≡ ai (mod pαi i )

 

ai ∈ {−1, 0}, i = 1, k.



có duy nhất một nghiệm theo mod n và ta có 2k hệ (bằng số bộ (a1, a2, ..., ak), ai ∈ {−1, 0}). Nghiệm của các hệ là khác nhau. Như vậy, phương trình x2 + x ≡ 0 (mod n) có đúng 2k nghiệm.

Kết luận

Trong luận văn này, chúng tôi nghiên cứu một số vấn đề về đồng dư đa

thức. Các kết quả trong luận văn được tham khảo trong các tài liệu [2],

[4], [6], [7]. Cụ thể luận văn đã đạt được một số kết quả chính sau:

- Hệ thống lại một số kiến thức cơ bản về đa thức một ẩn và một số kiến

thức số học có liên quan đến nội dung của luận văn.

- Nghiên cứu về Đồng dư đa thức theo môđun một đa thức. Đưa ra đặc

trưng và một số tính chất cơ bản của đồng dư đa thức theo môđun một

đa thức (Mệnh đề 2.1.2, Định lý 2.1.3). Nghiên cứu trường hợp đặc biệt

của đồng dư đa thức theo môđun một đa thức là môđun số nguyên tố và

lũy thừa của số nguyên tố.

- Đưa ra một số ứng dụng của đồng dư đa thức trong giải toán sơ cấp.

Tài liệu tham khảo

Tiếng Việt

[1] Nguyễn Hữu Điển, Đa thức và ứng dụng, NXB GD, 2003.

Tiếng Anh

[2] L. Ake Lindahl, Lectures on Number theory, Uppsala University Re-

trieved http://www2...,2002-math.uu.se, 2002.

[3] E. J. Barbeau, Polynomials, Springer, 2003.

[4] Lindsay N. Childs, A Concrete Introduction to Higher Algebra, Un-

dergraduate Texts in Mathematics, Springer Science+Business Media

LLC 2009.

[5] V. Dotsenko, Solutions to polynomial congruences, www.maths.

tcd.ie/ vdots/teaching/files/MA2316-1314/Hensel.pdf.

[6] Polynomial congruences to prime power moduli, https://people.

maths.bris.ac.uk/ mazag/nt/lecture7.pdf.

[7] Polynomial congruences, www.math.niu.edu/ richard/Math420/poly-

cong.pdf.

Thái Nguyên, ngày........tháng........năm 2019

Người hướng dẫn Học viên

(Ký và ghi rõ họ tên) (Ký và ghi rõ họ tên)

TS. Nguyễn Thị Kiều Nga Nguyễn Thị Hoàn

Nhận xét của Hội đồng xét duyệt

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Thái Nguyên, ngày ... tháng ... năm 2019

Hội đồng xét duyệt

Luận văn Thạc sĩ Toán học: Về đồng dư đa thức

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC KHOA HỌC --------------------------- NGUYỄN THỊ HOÀN

VỀ ĐỒNG DƯ ĐA THỨC

LUẬN VĂN THẠC SĨ TOÁN HỌC

THÁI NGUYÊN - 2019

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC KHOA HỌC ---------------------------

NGUYỄN THỊ HOÀN

VỀ ĐỒNG DƯ ĐA THỨC

Chuyên ngành: Phương pháp Toán sơ cấp

Mã số: 8 46 01 13

LUẬN VĂN THẠC SĨ TOÁN HỌC

NGƯỜI HƯỚNG DẪN KHOA HỌC TS. Nguyễn Thị Kiều Nga

THÁI NGUYÊN - 2019

Lời cảm ơn

Mục lục

Mở đầu

Chương 1

Kiến thức chuẩn bị

Chương 2

Đồng dư đa thức

Chương 3

Một số ứng dụng của đồng dư đa

thức trong giải toán sơ cấp

Kết luận

Tài liệu tham khảo

Nhận xét của Hội đồng xét duyệt

Có thể bạn quan tâm

Luận văn Thạc sĩ: Quản lý hoạt động phát triển nhận thức cho trẻ mẫu giáo ở các trường mầm non, huyện Hoàng Su Phì, tỉnh Hà Giang

Luận văn Thạc sĩ tóm tắt: Pháp luật về điều kiện đầu tư kinh doanh trong lĩnh vực giáo dục, đào tạo ở Việt Nam

Luận văn Thạc sĩ: Sự nghiệp nghiên cứu phê bình văn học của Hoài Thanh

Luận văn Thạc sĩ: Tiểu thuyết của Đỗ Phấn từ góc nhìn sinh thái

Luận văn Thạc sĩ: Giải pháp ứng phó với nhập cư ở Liên minh Châu Âu

Luận văn Thạc sĩ: Diễn ngôn về giới nữ trong văn xuôi nữ Việt Nam đương đại (khảo sát sáng tác của Dạ Ngân, Y Ban, Lý Lan, Nguyễn Thị Thu Huệ)

Luận văn Thạc sĩ: Xây dựng mức phát thải tham chiếu rừng khu vực huyện Bảo Lâm tỉnh Lâm Đồng

Luận văn Thạc sĩ: Đặc điểm nhân vật chính trong ba tác phẩm của Franz Kafka: Lâu đài, Vụ án, Hóa thân

Kháo luận tốt nghiệp: Vận dụng lí thuyết học tập trải nghiệm vào dạy học Thống kê - Xác suất ở lớp Hai

Luận văn Thạc sĩ: Xây dựng hệ thống điều khiển và thu nhận dữ liệu cho Robot dịch vụ

Luận văn Thạc sĩ: Thế giới nhân vật trong truyện ngắn Lê Minh Khuê sau năm 1975

Luận văn Thạc sĩ: Tác động của cấu trúc vốn đến hiệu quả hoạt động của các ngân hàng thương mại cổ phần niêm yết trên thị trường chứng khoán Việt Nam

Luận văn Thạc sĩ: Kiểm soát rủi ro tín dụng bán lẻ tại Ngân hàng Thương mại Cổ phần Đầu tư và Phát triển Việt Nam chi nhánh Thủ Thiêm

Luận văn Thạc sĩ: Các yếu tố ảnh hưởng đến hiệu quả kinh doanh của ngân hàng thương mại cổ phần niêm yết trên thị trường chứng khoán Việt Nam

Luận văn Thạc sĩ: Các nhân tố ảnh hưởng đến hành vi sử dụng dịch vụ ngân hàng điện tử tại Ngân hàng Thương mại Cổ phần Ngoại thương Việt Nam – Chi nhánh Thủ Đức

Luận văn Thạc sĩ: Các yếu tố tác đồng đến nợ xấu tại Ngân hàng Nông nghiệp và Phát triển Nông thôn - Chi nhánh Tiền Giang

Luận văn Thạc sĩ: Yếu tố ảnh hưởng đến quyết định sử dụng dịch vụ thanh toán không dùng tiền mặt tại Ngân hàng TMCP Công thương Việt Nam (Vietinbank)

Luận văn Thạc sĩ tóm tắt: Pháp luật về du lịch biển, thực tiễn tại tỉnh Bình Định

Luận văn Thạc sĩ: Ảnh hưởng của các yếu tố thương hiệu với vai trò trung gian của Marketing truyền miệng đến quyết định chọn việc làm của nhân viên GenZ tại chuỗi nhà hàng gà rán Popeyes khu vực Thành Phố Hồ Chí Minh

Luận văn Thạc sĩ: Ảnh hưởng của Marketing mix đến ý định học cao học của sinh viên khối ngành kinh tế thuộc Trường Đại học Công nghệ Thành phố Hồ Chí Minh

Tài liêu mới

Luận án Tiến sĩ: Nghiên cứu xây dựng thuật toán thích nghi và học tăng cường cấu trúc Actor - Critic điều khiển bám quỹ đạo cho robot di động đa hướng mecanum

Luận án Tiến sĩ: Cơ cấu bệnh tim mạch và chất lượng cuộc sống của người cao tuổi mắc suy tim, rung nhĩ điều trị tại Bệnh viện Thống Nhất, thành phố Hồ Chí Minh

Tóm tắt Luận án Tiến sĩ: Nghiên cứu hiện tượng nứt dăm đê sông vùng đồng bằng sông Hồng và dự báo khả năng bị nứt của một số đoạn đê

Tóm tắt Luận án Tiến sĩ: Nghiên cứu xây dựng giải pháp đảm bảo an toàn thông tin cho quá trình học liên kết dựa trên mật mã

Tóm tắt Luận án Tiến sĩ: Phát triển năng lực đánh giá công nghệ cho học sinh trong dạy học môn Công nghệ 11 ở trường trung học phổ thông

Tóm tắt Luận án Tiến sĩ: Nghiên cứu phân loại chi cầu diệp – Bulbophyllum Thouars (Orchidaceae) ở vùng Tây Nguyên bằng phương pháp hình thái và phân tử

Tóm tắt Luận án Tiến sĩ: Nghiên cứu đặc điểm phân bố và dinh dưỡng của các loài lưỡng cư ở Vườn Quốc gia Bến En và Khu bảo tồn thiên nhiên Pù Luông, tỉnh Thanh Hóa

Luận án Tiến sĩ: Tổng hợp luật dẫn và điều khiển cho một lớp tên lửa đối hải trên cơ sở ứng dụng mạng nơ ron và hệ mờ

Luận án Tiến sĩ: Nghiên cứu tổng hợp hệ điều khiển góc Pitch tua bin gió trong điều kiện có nhiễu tác động

Luận án Tiến sĩ: Nghiên cứu hóa học lipid của hai loài san hô thủy tức Millepora dichotoma và Millepora platyphylla ở Việt Nam

Luận án Tiến sĩ: Nghiên cứu kiểm soát phân phối công suất kéo trên cầu chủ động của ô tô con bằng ABS

Luận án Tiến sĩ: Ứng dụng phản ứng Domino vào tổng hợp các dẫn xuất Podophyllotoxin, Pyrimidine và đánh giá hoạt tính sinh học của các chất tổng hợp được

Luận án Tiến sĩ: Nghiên cứu thành phần hóa học và một số hoạt tính sinh học của cây chùm ngây (Moringa oleifera)

Tóm tắt Luận án Tiến sĩ: Nghiên cứu thành phần hóa học và ứng dụng ức chế ăn mòn cho thép của cao chiết xuất từ cây Lộc vừng thuộc họ Lecythidaceae

Luận án Tiến sĩ: Nghiên cứu hiện tượng nứt dăm đê sông vùng đồng bằng sông Hồng và dự báo khả năng bị nứt của một số đoạn đê

AI tóm tắt

Giới thiệu tài liệu

Đối tượng sử dụng

Từ khoá chính

Nội dung tóm tắt

Giới thiệu

Về chúng tôi

Việc làm

Quảng cáo

Liên hệ

Chính sách

Thoả thuận sử dụng

Chính sách bảo mật

Chính sách hoàn tiền

DMCA