Bài giảng Lớp ghép và định lý Lagrange - PGS TS Trần Đan Thư

LLớớp ghp ghéép vp vàà đ địịnh lý nh lý Lagrange Lagrange

PGS TS Trầần n ĐĐan Th an Thưư PGS TS Tr tdthu@fit.hcmus.edu.vn tdthu@fit.hcmus.edu.vn

i dung TTóóm tm tắắt nt nộội dung

• Cấp của một phần tử • Khái niệm về lớp ghép và tính chất • Định lý Lagrange • Định lý Fermat nhỏ • Định lý Euler • Bài tập • Thuật ngữ

22

nh nghĩĩa (ca (cấấp cp củủa pha phầần tn tửử)) ĐĐịịnh ngh • Cho nhóm (G, o) và a∈G. Xét nhóm con sinh bởi a là

H = < {a} > = { ar / r∈ℤ}. – Trường hợp H hữu hạn: cấp của a là |H|, tức là số phần tử của

nhóm con sinh bởi a.

– Trường hợp H vô hạn: ta nói a có cấp vô hạn.

• Nhận xét:

– Nếu G hữu hạn thì hiển nhiên cấp a hữu hạn. – Nếu H hữu hạn tồn tại i và k (với i ≠ k) sao cho ai = ak, ta suy ra a|i-k| = e. Vậy tồn tại số nguyên dương m = |i-k| sao cho am = e. – Nếu H vô hạn, không thể tìm được số nguyên dương m sao cho

am = e, vì nếu ngược lại thì:

H = { ar / r∈ℤ} = {e, a, a2, …, am-1} hữu hạn.

33

nh chấất (vt (vềề ccấấp cp củủa pha phầần tn tửử)) TTíính ch Giả sử a∈G, a có cấp hữu hạn. Gọi n là số nguyên dương nhỏ nhất sao cho an = e (a) H = { ar / r∈ℤ} = {e, a, a2, …, an-1} có đúng n

phần tử. (b) Cấp a bằng n. (c) Nếu am = e thì n là ước số của m.

Chứng minh: Xem trình bày trên bảng. Ghi chú: Đối với nhóm ký hiệu + cũng tương tự.

44

VVíí ddụụ -- CCấấp php phầần tn tửử

• Phần tử -1 có cấp 2 trong nhóm nhân các số

thực khác không, vì: (-1)2 = 1

• Phần tử i có cấp 4 trong nhóm nhân các số

i2 = -1 ≠ 1 ; i3 = -i ≠ 1; i4 = 1

phức khác không, vì:

• Phần tử⎯2 có cấp 4 trong (ℤ8 , +) vì:

55

2⎯2 = ⎯4 ≠ ⎯0 3⎯2 = ⎯6 ≠ ⎯0 4⎯2 = ⎯8 = ⎯0

p (coset) LLớớp ghp ghéép (coset) Cho nhóm (G, o) và nhóm con H≤G và a∈G. •

Tập hợp aH = { a o h / h∈ H} được gọi là một lớp ghép (coset, lớp ghép trái) của H trong G.

– Ta luôn có: aH = bH ⇔ a -1 o b ∈ H.

•

•

Nếu aH = bH thì b = b o e ∈ bH = aH ⇒ b = a o h với h ∈ H. Do đó a -1 o b = h ∈ H. Nếu a -1 o b ∈ H, ta đặt h = a -1 o b ∈ H, lúc đó với mọi x ∈ H ta có: b o x = (a o h) o x = a o (h o x) ∈ aH, do đó bH ⊂ aH. Tương tự: aH ⊂ bH. Vậy: aH = bH. – Suy ra: nếu aH ∩ bH ≠ ∅ thì aH = bH.

•

-1 ∈ H ⇒ aH = bH.

Nếu aH ∩ bH ≠ ∅, ta lấy c∈ aH ∩ bH ⇒ c = a o h1 = b o h2 , với h1, h2 ∈ H. Do đó: a -1 o b = h1 o h2

66

• Nhận xét (với mọi a, b∈G):

TTíính ch

nh chấất ct củủa la lớớp ghp ghéépp

• Với mỗi a∈G, ánh xạ fa: H → aH với fa(h) = a o h là một song ánh, tức là |H| = | aH |, đặc biệt khi H hữu hạn thì H và aH có cùng số phần tử.

• Trên G, ta định nghĩa quan hệ ~ như sau: a ~ b ⇔ aH = bH, ∀a, b∈G.

Quan hệ này có các tính chất: – Phản xạ – Đối xứng – Bắc cầu Nên là một quan hệ tương đương.

•

Lớp tương đương của a chính là tập aH : ⎯a = aH. Trường hợp đặc biệt nếu a ∈ H thì aH=H.

• Nếu số lượng lớp tương đương là hữu hạn (điều này cũng xảy ra khi G hữu hạn) thì con số này ký hiệu là (G : H) và được gọi là chỉ số của H trong G (“the index of H in G”).

Định lý Lagrange

77

nh lý Lagrange ĐĐịịnh lý Lagrange

Cho G là nhóm hữu hạn và nhóm con H≤G.

|G| = (G : H).|H|,

Tức là cấp |H| luôn là ước số của |G|.

Hệ quả 1. Nhóm G cấp n, ta có xn = e, ∀x∈G. Hệ quả 2. Nếu nhóm G cấp p nguyên tố thì:

(a) G chỉ có 2 nhóm con là {e} và chính bản thân G. (b) G sinh bởi một phần tử, tức là có a∈G sao cho a có

cấp p và G = < {a} >.

Chứng minh: Xem trình bày trên bảng.

88

ĐĐịịnh lý Fermat nh

nh lý Fermat nhỏỏ

Giả sử p nguyên tố ≥ 2. Ta có (a) xp-1 =⎯1 với mọi x ∈ ℤp ; x ≠⎯0 . (b) xp = x với mọi x ∈ ℤp .

– Nếu p không ước của x thì xp-1 ≡1 [mod p] ; – Ta luôn có: xp ≡ x [mod p].

Ghi chú: Phát biểu dưới dạng cổ điển

99

Ngoài ra, từ (a) ta dễ dàng suy ra (b).

nh lý Fermat nhỏỏ

ng minh đđịịnh lý Fermat nh

ChChứứng minh Đặt Zp* = ℤp \ {⎯0 }. Bước 1. Chứng minh (Zp*, .) là nhóm. Chỉ cần chứng minh mọi x∈Zp* đều khả nghịch. Xét x =⎯m ≠ ⎯0 thì (m, p)=1 do p nguyên tố. Tồn tại a, b nguyên: am + bp = 1 ⇒ ⎯a ⎯m = ⎯1 .

Bước 2. Như Zp* là nhóm cấp p-1, theo hệ quả

xp-1 =⎯1 với mọi x ∈ Zp*.

1010

của định lý Lagrange ta có:

nh lý Euler ĐĐịịnh lý Euler

Giả sử n nguyên ≥ 2.

Đặt ϕ(n) là số các số k sao cho: 1 ≤k ≤n, (k, n)=1. Ta có: xϕ(n) =⎯1 với mọi x =⎯m ∈ ℤn ; (m, n)=1.

số học cổ điển.

1111

Ghi chú: Phát biểu dưới dạng cổ điển – Nếu (x, n) = 1 thì xϕ(n) ≡1 [mod n] . – Hàm ϕ(n) (gọi là hàm phi-ơ-le) được tính như trong

nh lý Euler ng minh đđịịnh lý Euler ChChứứng minh Đặt U(Zn) = {⎯m ∈ ℤn / (m, n)=1 }. • Bước 1: Chứng minh (U(Zn) , .) là nhóm. • Bước 2: Áp dụng hệ quả của định lý

Lagrange (tương tự như trong chứng minh định lý Fermat nhỏ).

(Xem trình bày chi tiết trên bảng.)

1212

BBàài ti tậậpp

Xem danh sách bài tập:

Tập tin Lec3_Probs.pdf

1313

c thuậật ngt ngữữ chchíínhnh

CCáác thu • Order of an element: cấp của một phần tử • Coset, left coset: lớp ghép (trái) • Index of H in G: chỉ số của nhóm con H trong

nhóm G

• A devides B: A chia hết B (A ước số B)

(tương đương với: B is divisible by A)

(p is a prime number ; p is a prime…)

• divisor: số chia, ước số • Prime: số nguyên tố

1414

• x relatively prime to y; x and y are relatively prime numbers: x và y nguyên tố cùng nhau