Khóa luận tốt nghiệp

Trường ĐHSP Hà Nội 2

MỞ ĐẦU

Trong Đại số giao hoán, khi nghiên cứu vành đa thức một biến
[ ] (với

là một trường), ta đã biết mọi iđêan đa thức

một đa thức
∈

đều sinh bởi

nào đó mà ta gọi đó là phần tử sinh của . Vì vậy với

[ ] bất kì, ta thực hiện phép chia đa thức

cho đa thức

theo

thuật toán Euclide để tìm đa thức dư , đa thức này xác định duy nhất và
∈ I khi và chỉ khi
thức nhiều biến

= 0. Một lẽ rất tự nhiên khi mở rộng lên vành đa

[ ,…,

], để xác định một đa thức

bất kì có thuộc iđêan đa thức

⊆ [ ,…,

không, ta sẽ đi tìm tập các phần tử sinh {

∈ [ ,…,

] cho trước nào đó hay
,…,

∈ , và sau đó thực hiện phép chia đa thức

} ≔ , trong đó các
cho tập các đa thức .

Tuy nhiên, liệu rằng có thực hiện được phép chia đa thức
đa thức

để tìm đa thức dư

]

cho tập các

hay không? Và đa thức dư này vẫn còn


xác định duy nhất? Thuật toán chia có thay đổi ra sao so với thuật toán
Euclide? Liệu

∈ I khi và chỉ khi

= 0?... Cơ sở Gröbner trong Đại số

máy tính cho phép giải đáp được tất cả những thắc mắc trên.
Được sự động viên, giúp đỡ của thầy, cô giáo khoa Toán, đặc biệt là
các thầy cô tổ Đại số, em đã chọn đề tài: “Cơ sở Gröbner và ứng
dụng”.
Nội dung của đề tài trình bày về những khái niệm cơ sở của lí
thuyết Gröbner và ứng dụng của nó. Xây dựng quan hệ thứ tự trên tập
các đơn thức nhiều biến, từ đó, chúng ta thấy được và làm rõ cách thức
mở rộng thuật toán chia đa thức một biến ở trung học cơ sở sang trường
hợp đa thức nhiều biến. Qua đó, người ta xác định phương hướng để giải
quyết một số bài toán về iđêan trong vành đa thức nhiều biến.
Đỗ Thị Mùi

1

K35A – SP Toán


Khóa luận tốt nghiệp

Trường ĐHSP Hà Nội 2

Đề tài được trình bày trong hai chương:
Chương 1. Cơ sở Gröbner.

Chương này đề cập đến khái niệm thứ tự từ, xuất phát điểm để xây
dựng cơ sở Gröbner. Từ đó, người ta đưa ra khái niệm iđêan khởi đầu, từ
khởi đầu, cũng như định nghĩa và một số tính chất cơ bản của cơ sở
Gröbner. Tiếp đó, tác giả trình bày việc mở rộng thuật toán chia với dư
trong vành đa thức nhiều ẩn. Cuối cùng, chúng ta đề cập tới thuật toán
Buchberger.
Chương 2. Một số ứng dụng của Cơ sở Gröbner.
Nội dung chủ yếu của chương này trình bày ứng dụng của cơ sở
Gröbner để giải quyết một số bài toán về iđêan trong vành đa thức nhiều
biến.
Mặc dù có nhiều cố gắng song còn nhiều hạn chế về thời gian và
kiến thức, khóa luận này không thể tránh khỏi những thiếu sót, em rất
mong nhận được ý kiến đóng góp của các thầy giáo, cô giáo và các bạn
sinh viên để khóa luận của em được hoàn thiện.

Đỗ Thị Mùi

2

K35A – SP Toán


Khóa luận tốt nghiệp

Trường ĐHSP Hà Nội 2

CHƯƠNG 1. CƠ SỞ GRÖBNER

1.1 Thứ tự từ
1.1.1 Thứ tự, giả thứ tự

Định nghĩa 1.1:
Cho tập
trên

≠ ∅. Quan hệ hai ngôi

là một quan hệ thứ tự bộ phận

nếu và chỉ nếu các điều kiện sau thỏa mãn:
∈ :

i)

Với

ii)

Với mọi ,

(tính chất phản xạ)
∈ : nếu

và

thì

=

(tính chất phản


đối xứng)
iii)

Với mọi , , ∈

: nếu

và

thì

(tính chất bắc

cầu)
Ta thường kí hiệu quan hệ thứ tự là ≤, ≥.
Nhận xét: Nếu

là một quan hệ thứ tự bộ phận thì:

= {( , )|( , ) ∈ } cũng là quan hệ thứ tự bộ phận và gọi là thứ tự
ngược của . Nếu kí hiệu

là ≤ thì

được kí hiệu là ≥.

Ví dụ
 Quan hệ ≤ trong tập hợp các số tự nhiên N là một quan hệ thứ
tự.
 Quan hệ chia hết trong N là một quan hệ thứ tự bộ phận.

Định nghĩa 1.1.2
Nếu trên

có một thứ tự bộ phận ≤ ta nói

phận. Khi đó, với mọi ,

∈

thì

≤

hoặc

là tập được sắp bộ

≤ , hoặc , không so

sánh được với nhau.
Quan hệ thứ tự ≤ trên
phần tử của

được gọi là thứ tự toàn phần nếu mọi cặp

đều so sánh được với nhau. Khi đó, ta nói

là tập được

sắp hoàn toàn.

Đỗ Thị Mùi

3

K35A – SP Toán


Khóa luận tốt nghiệp

Trường ĐHSP Hà Nội 2

Quan hệ hai ngôi chỉ thỏa mãn tính chất phản xạ và bắc cầu được
gọi là giả bộ thứ tự.
Ví dụ
 (N, ≤) là tập sắp thứ tự toàn phần.
 (R, ≤) là tập sắp thứ tự toàn phần vì mọi phần tử trong R đều so
sánh được với nhau. Tuy nhiên, (C, ≤) được xác định như sau:
+

≤ +

≤
≤

⟺

là quan hệ thứ tự bộ phận trên ℂ.

 Quan hệ chia hết là một thứ tự bộ phận trên tập N nhưng chỉ là
giả thứ tự bộ phận trên Z.

là tập đơn thức của vành [ ] với quan hệ xác định như sau:


≤
1, …

,

=

…

,

=

…

, nếu

≤

,∀ =

là quan hệ thứ tự bộ phận trên . Với số biến là 1 thì quan hệ là

quan hệ thứ tự toàn phần.
Định nghĩa 1.1.3
Cho ( , ≤) là tập được sắp bộ phận, Ø ≠
∈


i)

nếu với mọi
ii)
∈

mọi

∈

được gọi là phần tử tối tiểu (tương ứng tối đại) trong ,
∈

(tương ứng

≤ ) thì

= .

là phần tử bé nhất (tương ứng lớn nhất) trong
≤

ta có

∈

≤

ta có


iii) Phần tử
với mọi

⊆

ta có

(tương ứng

∈

nếu với

≤ ).

là chặn trên (tương ứng chặn dưới) của , nếu
≤

≤ ).

(tương ứng

iv) Tập

được gọi là bị chặn nếu nó vừa bị trên, vừa bị chặn dưới

v) Tập

được gọi là sắp thứ tự tốt nếu nó được sắp hoàn toàn và


mọi tập con khác rỗng của

để có phần tử bé nhất.

Ví dụ

Đỗ Thị Mùi

4

K35A – SP Toán


Khóa luận tốt nghiệp
 (N, |),

Trường ĐHSP Hà Nội 2

={ ∈ℕ∶

> 1}. Các phần tử tối tiểu là các số

nguyên tố.
 (ℝ, ≤),

= [1,2],

nhất, lớn nhất của .


= (1,2). Khi đó: 1,2 lần lượt là phần tử bé

không có phần tử bé nhất, lớn nhất, tối tiểu, tối

đại nhưng bị chặn trên và bị chặn dưới trong ℝ.
 (ℕ, ≤) là tập được sắp thứ tự tốt vì (ℕ, ≤) được sắp hoàn toàn
và mọi bộ phận khác rỗng của N đều có phần tử bé nhất. Tuy nhiên,
(ℤ, ≤)

không

= { | ∈ ℤ,

phải

là

tập

được

sắp

thứ

tự

tốt

vì


tập

< −2} không có phần tử bé nhất.

Bổ đề 1.1.1 ( Bổ đề Zorn)
Nếu

là tập được sắp (bộ phận) sao cho mọi tập con khác rỗng

được sắp hoàn toàn của nó bị chặn trong

thì

có phần tử tối đại.

1.1.2 Thứ tự từ
Định nghĩa 1.1.4
Cho

là tất cả các đơn thức của [ ]. Thứ tự toàn phần ≤ trên tập

được gọi là thứ tự từ nếu:
i) Với mọi

∈

,1 ≤

ii) Với mọi


,

,

.

∈

à

≤

thì

≤

.

Ví dụ: Quan hệ theo bậc của đơn thức một biến là một thứ tự từ.
Bổ đề 1.1.2
Một thứ tự toàn phần ≤ trên

là thứ tự tốt khi và chỉ khi mọi dãy

đơn thức thực sự giảm:
>

>


>⋯

sẽ dừng (sau hữu hạn phần tử).
Chứng minh
⊆

Giả sử ≤ không là thứ tự tốt trên
sao cho

Đỗ Thị Mùi

, tức là tồn tại tập con

không có phần tử bé nhất. Lấy
5

là một phần tử bất
K35A – SP Toán


Khóa luận tốt nghiệp
kì trong . Vì
, với

Trường ĐHSP Hà Nội 2
<

không có phần tử bé nhất nên tìm được
<


ta tìm được

trong

. Lặp lại quá trình trên mãi mãi ta nhận

được một dãy vô hạn các đơn thức thực sự giảm:
>
-

>

>⋯>

>⋯

Ngược lại, nếu có một dãy vô hạn các đơn thức thực sự giảm thì

dãy đó không có phần tử bé nhất. Vì vậy, thứ tự đã cho không là thứ tự
tốt.
Bổ đề 1.1.3
Mọi thứ tự từ là thứ tự tốt. Ngược lại, mọi thứ tự tốt trên

thỏa

mãn điều kiện ii) của Định nghĩa 1.1.4 là thứ tự từ.
Chứng minh
Cho ≤ là thứ tự từ. Giả sử ∅ ≠

-


đơn thức sinh bởi
,…,

∈

⊆

, gọi

. Theo Bổ đề Dickson tồn tại hữu hạn phần tử

sao cho : = (

,…,

).

Vì ≤ là thứ tự toàn phần nên có thể giả thiết
≤ . Ta chứng tỏ
∈ , vì

=(

là phần tử bé nhất của

,…,

, với mọi


. Thật vậy, với mọi

sao cho

nên theo tính chất của

=

, với

là đơn thức nào

hay ≤ là thứ tự tốt.

Ngược lại, giả sử ≤ là thứ tự tốt và tồn tại đơn thức

1>

≤

) nên theo bổ đề về tính chia hết của iđêan

đơn thức, ta tìm được ≤
đó. Vì 1 ≤

⊆ [ ] là iđêan

sao cho :

. Khi đó, theo tính chất ii) của Định nghĩa 1.1.4 ta có :

1>
-

=

.1 >

.

=

,

=

.

>

.

=

,…

Cứ tiếp tục như vậy ta nhận được một dãy vô hạn đơn thức thực

sự giảm: 1 >

>


>

> ⋯ Theo bổ đề về tính tương đương của

iđêan đơn thức, điều này trái với giả thiết ≤ là thứ tự tốt. Suy ra, 1 ≤
với mọi

∈

. Vậy ≤ thỏa mãn cả hai tính chất của Định nghĩa 1.1.4,

hay ≤ là thứ tự từ.
Đỗ Thị Mùi

6

K35A – SP Toán


Khóa luận tốt nghiệp

Trường ĐHSP Hà Nội 2

1.1.3 Một số thứ tự từ quan trọng
Trong phần này, chúng ta sẽ xét xem những thứ tự từ quan trọng mà
những phần tiếp theo chúng ta sẽ thường xuyên sử dụng đến chúng. Đó
là thứ tự từ điển, thứ tự từ điển phân bậc, thứ tự từ điển ngược.
Cho ≤ là một thứ tự từ. Bằng cách thay đổi chỉ số biến nếu cần thiết
>


có thể giả thiết :

>⋯>

.

Định nghĩa 1.1.5
i) Thứ tự từ điển, kí hiệu là ≤
…

<

…

bên trái của véctơ (
nếu tồn tại 0 ≤ <

−

, được xác định như sau :

nếu thành phần đầu tiên khác không kể từ
,…,

) là một số âm. (Nói cách khác,

−
=


sao cho

,…,

=

ii) Thứ tự từ điển phân bậc, kí hiệu là ≤
…

sau :
…

<

…

+ ⋯+

một số âm. Nói cách khác, nếu
+⋯+

=

+ ⋯+

…

và

≤


iii) Thứ tự từ điển ngược, kí hiệu là ≤
…

<

…

…

(

nếu
(

hoặc

(

…

đầu tiên khác không kể từ bên trái của véctơ (

)<

…

và là thành phần
−


,…,

<

+ ⋯+

−

hoặc

…

…

)<
…

và

thành phần đầu tiên khác không kể từ bên phải của véctơ (
,…,
⋯+
=

−

) là số dương. Nói cách khác, nếu

hoặc


+ ⋯+

,…,

=

=
nhưng

+ ⋯+
>

) là

, được xác định như sau :

)=

…

).

, được xác đinh như

nếu
)=

…

hoặc deg(


<

nhưng

+⋯+

và tồn tại 1 ≤ ≤

<

−
+

sao cho

.

Nhận xét : Dễ dàng chứng minh 3 thứ tự kể trên là thứ tự từ.
Ví dụ

Đỗ Thị Mùi

7

K35A – SP Toán


Khóa luận tốt nghiệp


Trường ĐHSP Hà Nội 2
>

 Trong cả 3 thứ tự trên ta luôn có :
,

 Cho các đơn thức :
>

,

>⋯>
,

.

. Sắp xếp các biến

> :
- Đối với thứ tự từ điển:
>

>

>

- Đối với thứ tự từ điển phân bậc:
>

>


>

- Đối với thứ tự từ điển ngược:
>

>

>

1.2 Iđêan khởi đầu, cơ sở Gröbner
1.2.1 Từ khởi đầu, đơn thức đầu
Định nghĩa 1.2.1
Cho ≤ là một thứ tự từ và
hiệu là

∈

[ ]. Từ khởi đầu của đa thức

( ), là từ lớn nhất của đa thức
( )= .

Nếu
đầu và

( )=

,0 ≠


∈

đối với thứ tự từ ≤.
( )=

thì

là đơn thức đầu của

được gọi là hệ số

đối với thứ tự từ ≤.

Nếu thứ tự từ ≤ đã được xác định rõ ràng ta thường viết gọn
(tương ứng

( ),

( )) thay cho

, kí

( ) (tương ứng

( ),

( )

( )).


Chú ý
 Từ khởi đầu của đa thức 0 là không xác định, nó có thể nhận giá
trị tùy ý.
 Trong biểu diễn chính tắc của đa thức
thứ tự giảm dần thì

nếu ta viết các từ theo

( ) sẽ xuất hiện đầu tiên.

Ví dụ
Cho đa thức
thứ tự giảm dần với

=3
>

+

−6

+

− 2 . Viết theo

> , ta có:
( )=3

Đỗ Thị Mùi


8

K35A – SP Toán


Khóa luận tốt nghiệp

Trường ĐHSP Hà Nội 2
( )=
( ) = −6

Bổ đề 1.2.1:
Cho ,

∈ [ ] và

∈

. Khi đó:

i)

(

)=

( ) ( )

ii)


(

)=

.

( )

iii)

( + )≤

{

( ),

( )}. Dấu < xảy ra khi và chỉ khi

( ) = − ( ).
Chứng minh
=

Giả sử:
<

( )+∑

( ), trong đó
i) Với
( )<


,

và

( ) ( ) ≠ 0,

( ) ( ). Do đó,

(

)=

( )

∑

+∑

nên điều chứng minh được suy ra từ i).

( )>

( ) thì ta có :

( )>

. Ta có :

)=


+

( )>

( )>

nghĩa từ khởi đầu, ta có :
tổng

( )≥

+

. Vậy,

( )+

=
( )>

nên

( )

( )=

{

 Nếu


( )=

( )
Do

nên lại có:
Đỗ Thị Mùi

( ),

( )+∑
( )+

( ) là từ lớn nhất trong
( +

( )}.
( )
+∑

( )=

( )≠− ( )

và

( ) ≠ 0 và

( + )=


( )+

. Theo định

và không giản ước được với bất kì từ nào khác, nên

( )+

và

( ) ( ) là từ lớn nhất của

và

iii) Không giảm tính tổng quát, ta có thể giả sử
 Nếu

( ) ( )

<

( ) ( ).

( )=

ii) Vì

,


( ) ( ) không thể giản ước được

với bất kì từ nào của khai triển tích
. Vậy

( )+∑

=

là các từ có thể bằng 0. Khi đó:

, :

mọi

( ) và

<

thì

+

=

.
( )>
{
9


( ),

,

( )=

( )>

( )}.
K35A – SP Toán


Khóa luận tốt nghiệp
( ) = − ( ) thì ta có:

 Nếu
đó,

+

Trường ĐHSP Hà Nội 2

( + )=

= 0 hoặc

( ). Vậy,

<


(

)<

( + )<

{

+

=∑

+∑

( ), hoặc
( ),

. Khi

( + )=

( )}. Đó là điều

phải chứng minh.
1.2.2 Iđêan khởi đầu
Định nghĩa 1.2.2
Cho là iđêan của [ ] và ≤ là một thứ tự từ. Iđêan khởi đầu của ,
( ), là iđêan của

kí hiệu


[ ] sinh bởi các từ khởi đầu của các phần

tử thuộc . Nghĩa là:
( )=(

( )| ∈ ).

Nhận xét
( ) là iđêan đơn thức.




( ) nếu thứ tự ≤ đã xác định.

( ) thay vì

Ta cũng sẽ viết

Bổ đề 1.2.2
Cho ≤ là một thứ tự từ và , là hai iđêan của . Khi đó :
i) Tập tất cả các đơn thức trong
ii) Nếu là iđêan đơn thức thì
iii) Nếu
( ) thì

⊆

( )⊆


thì

( ) là tập {

( )| ∈ }.

( )= .

( ). Hơn nữa, nếu

⊆

và

( )=

= .

iv)

( ) ( )⊆

v)

( )+

( ).

( )⊆


( + ).

Chứng minh
i) Nếu

∈

( ) thì theo bổ đề về các điều kiện tương đương của

iđêan đơn thức, ta có :
{

=

( )

và

∈ . Vậy

∈

( )| ∈ I}. Điều ngược lại hiển nhiên đúng.

Đỗ Thị Mùi

10

K35A – SP Toán



Khóa luận tốt nghiệp
ii) Vì

là iđêan đơn thức nên

thức. Với mỗi
∈

sử

Trường ĐHSP Hà Nội 2

∈ ,

=

sinh ra một tập

( )∈

( ), nên ⊆

( ). Ngược lại, giả

là một phần tử tùy ý thì theo bổ đề về tính chia hết, các điều
( ) chia hết cho đơn thức

kiện tương đương của iđêan đơn thức,

∈

nào đó. Lại theo bổ đề về tính chia hết của iđêan đơn thức,

( ) ∈ . Suy ra,

( ) ⊆ , tức là

( )= .
( )⊆

iii) Theo định nghĩa, rõ ràng ⊆ kéo theo
( )=
{

( ), ⊂ . Theo Bổ đề 1.1.3, tìm được
( )| ∈ ∖ }. Vì

( )=

∈

( )∈

( )=

( ). Ta có thể giả thiết

như vậy ta chia ,
,


nào đó các đơn

cho

( ). Giả sử,

∈ ∖ để

( ) nên tồn tại

( )=

∉ ,

∈

để

− , ta có:

nên ℎ ∉ . Vậy ℎ ∈ ∖

(ℎ) <

. Mặt khác, theo Bổ đề 1.2.1 iii), ta có:

∈

( ) = 1 (vì nếu không


( ), ( ) tương ứng). Đặt ℎ =

nên ℎ ∈ nhưng mặt khác

( )=

( ). Mâu thuẫn với

việc chọn . Vậy = .
iv) Ta có:
,

( ) ( ) sinh bởi các từ

∈ . Mặt khác, theo Bổ đề 1.2.1 i),
( ) ( )⊆

ngay
v)

(

( ) ( ), trong đó
)=

∈

( ) ( ) nên ta có


( ).

, ⊆ + nên theo iii) ta có ngay

( )+

( )⊆

( + ). □

1.2.3 Cơ sở Gröbner
Định nghĩa 1.2.3
Cho ≤ là một thứ tự từ,
đa thức khác không

,…,

đối với thứ tự từ ≤ nếu:

là một iđêan của
∈

[ ]. Tập hữu hạn các

được gọi là một cơ sở Gröbner của

( )=

(


), … ,

( ) .

[ ]. Nếu

,…,

Định lí 1.2.1
Cho

là một iđêan tùy ý của

Gröbner đối với thứ tự nào đó thì

,…,

là một cơ sở

là một cơ sở của .

Chứng minh
Đỗ Thị Mùi

11

K35A – SP Toán


Khóa luận tốt nghiệp

:= (

Đặt
( )⊆

Trường ĐHSP Hà Nội 2
)⊆ .

,…,

( ) nên

( )=

( )=

Vì

(

), … ,

( ) ⊆

( ). Theo Bổ đề 1.2.2 iii), ta có

= .

□


Nhận xét
Như vậy, việc xác định iđêan khởi đầu tương đương với việc tìm
một cơ sở Gröbner của đối với một thứ tự nào đó. Tuy nhiên, việc làm
này không hề đơn giản vì không phải mọi cơ sở của

đều là cơ sở

Gröbner của . Hơn nữa, một cơ sở đã cho của có thể là cơ sở Gröbner
đối với thứ tự này nhưng không là cơ sở Gröbner đối với thứ tự khác.
Ví dụ
là iđêan của vành [ ]. Ta biết rằng trên vành này chỉ có một



[ ], =

thứ tự từ là thứ tự từ phân bậc của đa thức. Ta có, với mọi ⊆
( ),

[ ]. Từ đó,

∈

={ ,



( )=

}∈


( ) .

[ , ],

=

+

−

,

=

−

Đối với 3 thứ tự : thứ tự từ điển, thứ tự từ điển phân bậc, thứ tự
( )=

từ điển ngược, ta có :
=

−

(

∈ nhưng

( )=


,

)=

∉

. Mặt khác, ta có :

( ). Vậy { ,

} không là cơ

sở Gröbner của .

>

={ − , +

> . Ta chứng tỏ

với mọi đa thức 0 ≠

}⊆

[ , , ]. Đối với thứ tự từ điển mà

− , +

là cơ sở Gröbner của . Thật vậy,


∈ có dang :
= ( − ) + ℎ( +

Nếu

( ) không chứa biến

= ( ). Chọn

=− ,

= . 0 + ℎ. 0, vô lí. Vậy
hay

− , +

=−

,

thì

)
chỉ chứa biến , tức là

thay vào biểu diễn của

( )∈( , )=


( − ),

ta có :
( +

)

là cơ sở Gröbner của đối với thứ tự từ điển.

Định nghĩa 1.2.4

Đỗ Thị Mùi

12

K35A – SP Toán


Khóa luận tốt nghiệp

Trường ĐHSP Hà Nội 2

Cơ sở Gröbner tối tiểu của

đối với thứ tự ≤ đã cho là một sở

⊆ sao cho :

Gröbner


( ) = 1, với mọi

i)

∈ .

∈ , không tồn tại

ii) Với mọi

∈

mà

( )| ( ).

Hệ quả 1.2.1
Cho ≤ là một thứ tự từ. Khi đó, mọi iđêan có cơ sở Gröbner tối tiểu
và mọi cơ sở Gröbner tối tiểu đều có chung số phần tử và chung tập từ
khởi đầu.
Nhận xét
Dựa vào thuật toán tìm tập sinh đơn thức tối tiểu của iđêan đơn thức
ta có ngay cách xây dựng cơ sở Gröbner tối tiểu xuất phát từ một cơ sở
Gröbner nào đó. Sau đây là thuật toán tìm cơ sở Gröbner tối tiểu.
Thuật toán 1.2.1 (Thuật toán tìm cơ sở Gröbner tối tiểu)
Tìm cơ sở Gröbner tối tiểu CSGRTT( , … , ) ≔ {
Gröbner

} từ cơ sở


,…,
,…,

Input :

,…,

: đa thức trong [ ]

Output:

,…,

: đa thức trong [ ]

FOR ≤

DO

≔ ⁄ ( ),

≔

( )

≔ 0; ≔ 1
WHILE ≤

DO


≔ +1
WHILE ≤
IF

|

DO
THEN
≔ + 1;

≔ +1

ELSE

Đỗ Thị Mùi

13

K35A – SP Toán


Khóa luận tốt nghiệp

Trường ĐHSP Hà Nội 2
|

WHILE

DO


≔ ; ≔ −1
≤

WHILE

DO

≔

;

≔

;

−

+ ,

,−

=(

−

≔

+1

≔ +1

≔ + 1;

≔ ; ≔ +1

Ví dụ
Cho

={

−

,

cơ sở Gröbner của iđêan

,

, − ,

} là

,−

+ ). Tìm cơ sở

−

Gröbner tối tiểu của .
Áp dụng thuật toán 1.2.1 tìm cơ sở Gröbner tối tiểu của như sau :
Với


=

−

,

=

− ,

=

,

,

=

,

=

=
=−

−

+ ,


=

,

= −

,
=

. Ta có các từ tương ứng là :

,

=

,

= ,

=

,

=

.

Vòng lặp thứ 1 : ≔ 0; ≔ 1;
Đầu tiên ( = 1) <= (7 = ) nên
Kiểm tra


∤

≔ 2. Vì ( = 2) <= (7 = ).

1 = 3. Ta có : ( = 3) <= (7 = ) kiểm tra
2;

∤

, thực hiện lệnh else kiểm tra
|

≔ +1=

thì

≔ + 1 = 4. Ta lại có : ( = 4) <= (7 = ) kiểm tra
∤

thực hiện lệnh else kiểm tra
( = 5) <= (7 = ) kiểm tra

|

nên

kiểm tra

∤


kiểm tra

∤

≔ + 1 = 1;

∤

∤

thì

≔ + 1 = 5. Lại có :

thì ≔ + 1 = 3;

Tiếp tục ( = 6) <= (7 = ) kiểm tra

≔ +

nên

≔ + 1 = 6.

, thực hiện lệnh else

nên ≔ + 1 = 7. Cuối cùng, ( = 7) <= (7 = )
nên
≔


≔ + 1 = 8 > (7 = ), thoát.
; ≔4

Vòng lặp thứ 2 : = 1; = 4;

Đỗ Thị Mùi

14

K35A – SP Toán


Khóa luận tốt nghiệp

Trường ĐHSP Hà Nội 2

Đầu tiên, ( = 4) <= (7 = ) nên
|

kiểm tra

≔ + 1 = 5;

nên

(7 = ), kiểm tra

∤


≔ = 6; ≔ − 1 = 6,
,

≔

≔ 5. Vì ( = 5) <= (7 = ),

≔ + 1 = 6. Ta có : ( = 6) <=

thực hiện lệnh else kiểm tra
= 6 <= ( = 6)

≔

thì

|

nên

,

=

+ 1 = 7, ≔ + 1 = 7 > (6 = ), thoát,

≔ + 1 = 2;

≔


; ≔ + 1 = 6;

Vòng lặp thứ 3 : = 2; = 6;
Kiểm tra thấy ( = 6) <= (6 = ) nên

≔ + 1 = 7 > (6 = )

thoát.
≔ + 1 = 3;

≔

; ≔ + 1 = 7 > (6 = ). Kết thúc thuật toán.

Vậy cơ sở Gröbner tối tiểu của là: {

, − ,

}.

Định nghĩa 1.2.5
Cơ sở Gröbner rút gọn của iđêan

đối với thứ tự đã cho là một cơ

sở Gröbner của thỏa mãn các tính chất:
( ) = 1, với mọi

i)


ii) Với mọi
{ } mà

∈ .

∈ , với mọi từ

của , không tồn tại

∈

∖

( )| .

Nhận xét : Mọi cơ sở Gröbner rút gọn là cơ sở Gröbner tối tiểu.
Định lí 1.2.2
Cho ≠ 0. Khi đó, mọi thứ từ từ

có duy nhất một cơ sở Gröbner

rút gọn.
Chứng minh
 Sự tồn tại:
Cho
trong

là một cơ sở Gröbner tối tiểu của . Ta nói:

∈


rút gọn

nếu không có từ nào của , trừ từ khởi đầu của nó chia hết cho

các từ khởi đầu của đa thức khác trong

Đỗ Thị Mùi

15

( ) ≔ { ( )| ∈ }. Chúng

K35A – SP Toán


Khóa luận tốt nghiệp
ta sẽ biến đổi

Trường ĐHSP Hà Nội 2

sao cho nhận được cơ sở Gröbner mà mọi phần tử của

nó đều rút gọn.
Ta có nhận xét rằng : Nếu

rút gọn trong

trong mọi cơ sở Gröbner tối tiểu


thì

cũng rút gọn

của (vì ,

bất kì chứa

có cùng

số phần tử và chung tập của từ khởi đầu).
∈

Giả sử:
0≠

là một phần tử không rút gọn trong

( ),

≠

∈ ,

∈

, lớn nhất của

∈


∖ { } để

≥

( ) nên theo Bổ đề 1.2.1 iii)

( )| . Đặt

= ( ∖ { }) ∪ {
( )=

,

=

sao cho tồn tại:
⁄ ( ). Vì

−
(

)=

( )=

) < ( ). Thật vậy, giả sử

đơn thức của

( )>


( ). Do đó,

} là cơ sở Gröbner tối tiểu. Hơn nữa, nếu đặt

là đơn thức được chọn như trên thì hoặc

, hoặc (

. Chọn từ

không rút gọn. Nếu (

chia hết cho từ khởi đầu của

∗

không thể là ( ) vì ( ) đã bị triệt tiêu nên (
= ( ). Vậy ta luôn có: (
tìm được đơn thức

rút gọn trong

∈

nào đó thì từ này

)≤ ( ) | ( )<

) < ( ) nếu (


), ( ) tồn tại, tức là

theo cách trên. Tiếp tục lặp lại quá trình trên, vì

thứ tự là thứ tự từ tốt nên đến một lúc nào đó ta nhận được:
( ∖ { }) ∪ { } mà không còn ( ). Tức là,

rút gọn trong

Lặp lại quá trình trên với tất cả các từ chưa rút gọn trong
được cơ sở Gröbner
Định lí 1.2.5,

) là

=

.
ta nhận

mà mọi phần tử của nó đều rút gọn. Khi đó, theo

là cơ sở Gröbner rút gọn.

 Tính duy nhất:
Giả sử
,

,


là hai cơ sở Gröbner rút gọn. Theo Hệ quả 1.2.1,

chung số phần tử và tập từ khởi đầu. Lấy

được
( )=
từ của

∈

sao cho

( )=

( ). Nếu ℎ ≠ 0 thì
, nhưng khác

Đỗ Thị Mùi

( ). Đặt ℎ =

∈

tùy ý, khi đó tìm

−

, ta có :


(ℎ) ≠

(ℎ) hoặc là một từ của , hoặc là một

( ). Theo định nghĩa cơ sở Gröbner,
16

(ℎ)

K35A – SP Toán


Khóa luận tốt nghiệp

Trường ĐHSP Hà Nội 2
(

chia hết cho một từ khởi đầu

,

∗

∈

nào đó. Điều này mâu thuẫn

là cơ sở Gröbner rút gọn. Vậy, ℎ = 0, từ đó :

với giả thiết

, tức là

∗ ),

⊆

=

∈

. Chứng minh hoàn toàn tương tự, bằng cách đổi vai trò
⊆ . Vậy

ta chứng minh được

=

.

□

1.3 Thuật toán chia
1.3.1 Phép chia với dư trong vành đa thức một biến
Cấu trúc iđêan của vành đa thức một biến trên một trường khá đơn
giản. Đó là do vành đa thức một biến thỏa mãn định lí chia đa thức. Mặc
dù kết quả đơn giản nhưng chứng minh của nó chứa đựng ý tưởng sâu
sắc để mở rộng cho trường hợp nhiều biến. Trong phần này chúng ta sẽ
chứng minh mọi iđêan của vành một biến đều sinh bởi một đa thức.
Định lí 1.3.1 (Định lí chia đa thức một biến)
Cho


là một trường và ( ) là một đa thức khác 0 của

đó, với mọi đa thức ( ) ∈

[ ]. Khi

[ ] có thể biểu diễn duy nhất dưới dạng :

( ) = ( ) ( ) + ( ),
( ), ( ) ∈

trong đó :

[ ] và hoặc

( ) = 0 hoặc deg ( ) <

deg ( ). Hơn nữa, ( ), ( ) được xác định duy nhất.
Chứng minh
Với mọi

∈

[ ], có thể biểu diễn dưới dạng :
=

trong đó :

= deg ,


.

+

.

+…+

,

≠ 0.

Ta sẽ chứng minh sự tồn tại của , bằng quy nạp theo deg
sau : Nếu deg

< deg , đặt

= 0 và

=

.

Giả sử định lí đúng với mọi đa thức có bậc ≤
≥ deg . Ta sẽ chứng minh nó đúng với đa thức
Xét đa thức

Đỗ Thị Mùi


=

−

. Ta có :

< deg

17

như

− 1, trong đó :

tùy ý có deg

= .

= . Theo giả thiết quy

K35A – SP Toán


Khóa luận tốt nghiệp
,

nạp, tồn tại
Đặt :

=


+

, ta sẽ có :
,

deg , thì ta có : −
≠

deg( −

= 0 hoặc deg < deg

sao cho

Giả sử tồn tại

Nếu

Trường ĐHSP Hà Nội 2

=

sao cho :
=(

+ và
=

=


và

+ .

= 0 hoặc deg < deg .
+

= 0 hoặc deg

và

<

− ) .
− ) ≥ deg , trong khi

thì deg(

) < deg . Vô lí. Vậy

=

và do đó

−

=

= 0 hoặc


.

□

Từ đó, ta có thuật toán chia đa thức một biến như sau:
Thuật toán 1.3.1 (Thuật toán chia đa thức một biến)
Tìm thương và đa thức dư CHIA( , ) ≔ ( , ) khi chia

cho

Input: ,
Output: ,
≔ 0; ≔
WHILE

≠ 0 AND deg

≔

( )⁄ ( )

+

≤ deg DO

≔ + ( ( )⁄ ( ))
Nhận xét
Thuật toán trên đây sẽ dừng sau số bước tối đa bằng bậc của đa
thức ( ).

Hệ quả
Vành đa thức một biến

[ ] trên một trường tùy ý là một vành các

iđêan chính, nghĩa là mọi iđêan đều sinh bởi một đa thức.
Chứng minh
Giả sử ⊆
Nếu
mọi

[ ]. Nếu = 0 thì = (0).

≠ 0, gọi ℎ là đa thức bậc bé nhất trong ∖ {0}. Khi đó, với

∈ , theo định lí chia đa thức, tồn tại , ∈ [ ]:

= 0 và deg < deg ℎ. Vì

Đỗ Thị Mùi

là iđêan, nên ℎ ∈

18

và

= ℎ+
=


và

− ℎ∈ .

K35A – SP Toán


Khóa luận tốt nghiệp

Trường ĐHSP Hà Nội 2

≠ 0 thì mâu thuẫn với cách chọn ℎ. Vậy

Nếu

= ℎ, hay

∈ (ℎ). Do

nên ta có: ⊆ (ℎ).

tính tùy ý của

Ngược lại, nếu ℎ ∈ thì hiển nhiên (ℎ) ⊆ . Vậy = (ℎ).

□

Nhận xét
Hệ quả này chỉ khẳng định một iđêan bất kì của vành đa thức một
biến là iđêan chính chứ không phải cho ta tìm iđêan chính đó. Để làm

được điều này, chúng ta cần thêm khái niệm ước chung lớn nhất của đa
thức và thuật toán tìm UCLN của đa thức.
Định nghĩa 1.3.1
,…,

Ước chung lớn nhất của đa thức

∈ [ ] là đa thức ℎ sao

cho:
-

ℎ chia hết

,…,
=

-

Nếu

nghĩa là :

ℎ ,…,

=

ℎ ;

,…,

,…,

là đa thức khác chia hết

hiệu: ℎ =UCLN( , … ,

∈
thì

[ ].
chia hết ℎ. Kí

).

Mệnh đề 1.3.1
Cho

,…,

∈

i) UCLN( , … ,

[ ],

≥ 2. Khi đó:

) tồn tại và duy nhất (sai khác một hằng số khác

0 của ).

ii) ( , … ,
iii) Với

)=(UCLN( , … ,
≥ 3: UCLN( , … ,

)).
) =UCLN(UCLN( , … ,

),

).

Chứng minh
Xét iđêan
cho = (ℎ). Vì
hết cho

,…,

= ( ,…,

∈ (ℎ) nên ℎ chia hết cho
, tức là tồn tại

. Vì ℎ ∈ nên ℎ =

Đỗ Thị Mùi

). Theo Hệ quả 1.3.2, tồn tại ℎ ∈ [ ] sao


+ ⋯+

,…,
,

19

, = 1,2, … Giả sử

∈

[ ] để

,…,

∈

=

,…,

chia
=

[ ], tức là:

K35A – SP Toán



Khóa luận tốt nghiệp
ℎ=

Trường ĐHSP Hà Nội 2
=(

+ ⋯+

chia hết cho ℎ. Vậy, ℎ = UCLN( , … ,

hay

Giả sử ℎ = UCLN( , … ,
ℎ = ℎ ,0 ≠

,

Do (ℎ,

) thế thì ℎ, ℎ chia hết lẫn nhau, nên
). Vì (ℎ) = ( , … ,

). Theo ii) ta có: ( , … ,

) = (UCLN( , … ,

UCLN(ℎ,

).


∈ . Vậy i) và ii) được chứng minh.

Đặt ℎ = UCLN( , … ,
( ,…,

)

+ ⋯+

) = (UCLN( , … ,

,

)=
)).

)). Lại theo ii) ta có: UCLN( , … ,

)=UCLN(UCLN( , … ,

Theo i) ta có: UCLN( , … ,
Như chúng ta đã biết ,

) nên (ℎ,

),

).

)=

□

) =UCLN(UCLN( , … ,

),

).

là hai đa thức của vành đa thức một biến thì ta

có: UCLN( , )=UCLN(g, Rem( , )). Từ đó, ta có thuật toán Euclide
tìm ước chung lớn nhất của hai đa thức.
Thuật toán 1.3.2 (Thuật toán Euclide)
Tìm UCLN( , ) ≔ ℎ
Input: ,
Output: ℎ
ℎ≔
≔
WHILE <> 0 DO
≔

(ℎ; )

ℎ≔
≔
Ví dụ
Áp dụng định lí chia đa thức, tìm thương và dư của phép chia đa
thức

( ) cho đa thức


( ( ), ( )), với ( ) = −

Đỗ Thị Mùi

( ). Tìm phần tử sinh của iđêan
+2

−2

20

+ 3, g( ) =

=

+ 1.

K35A – SP Toán


Khóa luận tốt nghiệp

Trường ĐHSP Hà Nội 2

Đa thức bị chia (trung gian) p
− +2 −2 +3
−(− − )
2
−(2


Đa thức chia
+1
− +2

Phần dư

− +3
+ 2)
−

+1

−

0
Vậy ( ) = (−

+ 2) ( ) + (−

+ 1 = (−

Ta có:
−

+ 1 (chuyển từ p)

+ 1)

+ 1)(− ) + ( + 1)


+ 1 = ( + 1)(− + 1)

Vậy =

+ 1.

1.3.2 Phép chia với dư trong vành đa thức nhiều biến
Trong phần trên, chúng ta đã thấy được vai trò quan trọng của định
lí chia đa thức một biến để nghiên cứu cấu trúc của vành đa thức một
biến. Khi sang đến vành nhiều biến công cụ này không thể giải quyết
trọn vẹn được vấn đề này. Ý tưởng trong việc mở rộng này là dùng thứ
tự từ thay cho bậc của đa thức. Bằng cách này không những có thể mở
rộng ra trường hợp nhiều biến mà còn chia cho được nhiều đa thức cùng
một lúc. Mặc dù việc mở rộng này làm đa thức dư và các đa thức thương
không còn xác định duy nhất như trong trường hợp chia cho một đa thức
một biến.
Định lí 1.3.2 (Định lí chia đa thức)
Cố định một thứ tự từ ≤ trên
[ ,…,
=

]. Khi đó, mọi đa thức
+ ⋯+

= { ,…, } ⊂

và cho
∈


+ (∗), trong đó:

=

có thể viết được dưới dạng:
, ∈

thỏa mãn các điều kiện

sau:
i) Hoặc
các từ khởi đầu
Đỗ Thị Mùi

= 0, hoặc không có từ nào của
,…,

. Hơn nữa,
21

<

chia hết cho một trong
.
K35A – SP Toán


Khóa luận tốt nghiệp

Trường ĐHSP Hà Nội 2


≠ 0 thì

ii) Nếu

(

)≤

( ), = 1, … , .

Định nghĩa 1.3.2
Đa thức
khi chia cho

trong biểu diễn trên gọi là đa thức dư hoặc phần dư của
và kí hiệu là

=

( ).

theo (∗) được gọi là biểu diễn chính tắc của

Biểu diễn của

theo

,…, .
Nhận xét

( ) không xác định duy nhất.



Đa thức



Các đa thức

,…,

đóng vai trò như các đa thức thương

nhưng chúng không quan trọng đối với lí thuyết trình bày nên không
được đặt tên gọi riêng.
Chứng minh (Định lí 1.3.2)
Định lí được chứng minh bằng thuật toán sau:
Thuật toán 1.3.3 (Thuật toán chia đa thức)
Tìm PHANDU( ; , … , ) ≔
,…, ,

Input:

,…,

Output:

≔ 0; … ;


khi chia

cho

,…,

∈ [ ];
, ∈

[ ];

≔ 0; ≔ 0;

≔
WHILE

≠ 0 DO

≔1
Chiahet := false
WHILE ≤
IF

AND Chiahet = false DO

( )| ( ) THEN
( )⁄ ( )

≔


+

≔

− ( ( )⁄ ( ))

Chiahet := true
Đỗ Thị Mùi

22

K35A – SP Toán


Khóa luận tốt nghiệp

Trường ĐHSP Hà Nội 2

ELSE
≔ +1
IF Chiahet = false THEN
≔ +

( )

≔

( )

−


Để chứng tỏ đầu ra của thuật toán chính là những đa thức thỏa mãn
định lí chia đa thức, trước hết ta chứng tỏ rằng mỗi bước của thuật toán
luôn có:
=

+ ⋯+

( , ), … ,

+

( , ),

+ ,

( )≤

(1)

( ),

(2)

Ta sẽ chứng minh bằng quy nạp theo số bước thực hiện thuật toán.
=⋯=

Theo cách đặt ban đầu:

=


= 0,

=

nên lúc đầu (1),(2)

đúng.
Giả sử các hệ thức (1),(2) đúng ở một bước nào đó. Nếu ở bước tiếp
theo vẫn còn thực hiện tiếp phép chia mà chưa thay đổi
( )| ( ). Khi đó,
=

nhận giá trị:
+
Vì các

=(

nhận giá trị mới:

=

thì tồn tại để
( )⁄ ( ) và

+

− ( ( )⁄ ( )) . Do đó:
( )⁄ ( )) +


+

, ≠ và

−( ( )⁄ ( )) =

+ .

không đổi, nên (1) vẫn đúng ở bước này. Từ Bổ đề

1.2.1 và theo giả thiết quy nạp, ta có:
(

)≤
{

=
Hơn nữa, vì
(

=

),

(

),

− ( ( )⁄ ( ))


( )⁄ ( )) ( ) =
( )≤

(

( ( ) ) ( )
( )} ≤
và

( )
(( ( )⁄ ( )) ) =

( ), nên từ Bổ đề 1.2.1 suy ra:

( )<

( ). Như vậy, (2) cũng đúng ở bước này.

Nếu ở bước tiếp theo không thực hiện phép chia mà chỉ đổi phần dư
thì giá trị mới của
Đỗ Thị Mùi

,

tương ứng là
23

=


−

( ) và

= +

K35A – SP Toán


Khóa luận tốt nghiệp
( ). Vì:

+

Trường ĐHSP Hà Nội 2

=

( ) +

−

+

( ) =

+

và


,…,

không đổi nên ta vẫn có (1) ở bước này. Từ Bổ đề 1.2.1 cũng suy ra ngay
( )<

( )≤

( ) và do đó, (2) cũng đúng.

Vì vậy, theo Nguyên lí quy nạp (1),(2) đúng ở mọi bước và nếu
= 0 thì (1) trở thành:

thuật toán dừng tức

=
Vì

+

bắt đầu từ 0 và chỉ tăng thêm khi lệnh thử Chiahet := false, tức
( ) nào chia hết cho

là khi không có
chính là

+ ⋯+

( ) nên

( ). Do đó, từ thêm vào


thỏa mãn điều kiện i) của định lí chia. Điều kiện ii)

suy ra ngay từ (2).
Bây giờ ta sẽ chứng minh thuật toán dừng sau hữu hạn bước. Nếu kí
hiệu

= ,

, ≥ 1 là đa thức

theo chứng minh trên:

( )>

khi thay đổi lần thứ
( )>

thì ta có ngay

( )>⋯

Vì thứ tự là thứ tự tốt nên theo Bổ đề 1.1.2, dãy này phải dừng, tức
là tồn tại để

= 0, hay thuật toán dừng.

Sau đây, chúng ta sẽ xét một số ví dụ minh họa cho thuật toán trên.
 Cho


( , )=

+

− 1, ( , ) =

+

+ 1. Hãy

thực hiện phép chia đa thức ( , ) cho ( , ). Sắp xếp các từ của đa
thức theo thứ tự từ điển với

> , ta có thể thực hiện phép chia hai đa

thức như sau:
Đa thức bị chia (trung gian)
+
−1
−(
+
+
)

Đa thức chia Phần dư
+
+1
− +1

−

+
−
−1
−(−
−
− )
+
−
+ −1
−(
+
+ 1)
−
−
+
−2
0
Đỗ Thị Mùi

−
−
+
− 2(chuyển từ )
24

K35A – SP Toán


Khóa luận tốt nghiệp


Trường ĐHSP Hà Nội 2
−1=(

+

Vậy:

+

+ 1)(

−

+

−

+ 1) +

−

− 2.

 Bây giờ ta sẽ xét một ví dụ khác để thấy được sự mở rộng định
lí chia đa thức cho trường hợp nhiều đa thức chia. Để đơn giản, chúng ta
xét trường hợp có hai đa thức chia.
( , )=

+2


− 1; ( , ) =

+3
( , )=

+ ;

+

Đối với thứ tự từ điển phân bậc mà

> . Phép chia được thực

hiện như sau:
Đa thức bị chia (trung gian) Đa thức chia
+2
−(

+3

+
+

−1

+

)

+3 −1

−(
+
)
−
+3 −1
−(−
− )
3

+

3
−(3

Phần dư

+
−

−1
−1
+3 )

(chuyển từ )

+
3
−3 −1 (chuyển từ )

−3 − 1

0
Vậy
+2

+3
3(

=(

+ )(

+

−1=(
+ )+(

+ )(

+

)+(

+ )(− ) +

− 3 − 1)

+ 3) + (− )(

+ )+(


− 3 − 1).

Để thấy được đa thức dư không xác định duy nhất khi có nhiều đa
thức chia. Chúng ta xét lại ví dụ trên nhưng đổi chỗ hai đa thức chia cho
nhau. Quá trình thực hiện như sau:

Đỗ Thị Mùi

25

K35A – SP Toán