Xem mẫu
ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH
ĐẠI HỌC KHOA HỌC TỰ NHIÊN
KHOA TOÁN-TIN HỌC
BÁO CÁO TIỂU LUẬN
MÔN HỌC:
ĐỀ TÀI:
SỐ HỌC VÀ LOGIC
ĐỒNG DƯ VÀ CÁC ĐỊNH LÝ ĐỒNG DƯ
Họ và tên sinh viên:
Đỗ Thị Thu Hiền 1311106
Bùi Thị Yến Duyên 1311046
Trần Thị Ngọc Cẩm 1311026
Lê Thị Hiền Diệu 1311038
Khóa học: 2015-2016
Giảng viên phụ trách: Trần Nam Dũng
THÀNH PHỐ HỒ CHÍ MINH-NĂM 2015
1
I. CƠ SỞ KHOA HỌC
1. Cơ sở lý luận.
Lý thuyết đồng dư được xây dựng trên nền tảng là phép chia trên vành số nguyên. Là một
nội dung được suy luận một cách lôgic, chặt chẽ.
2. Cơ sở thực tiễn
Lý thuyết đồng dư sẽ cho ta phương pháp đồng dư, đố là một động tác có tính chất kỷ thuật giúp chúng ta bổ sung giải quyết vấn đề chia hết trong vành số nguyên.
II. NỘI DUNG
1. Đồng dư
1.1. Định nghĩa và tính chất
1.1.1 Định nghĩa
Cho m ∈ ℤ, m >1 ta nói a và b đồng dư theo môđun m và viết a ≡ b (mod m) nếu a và b
có cùng số dư khi chia cho m hay nói cách khác a – b ⋮ m
Ta có : a ≡ b (mod m) a – b ⋮ m
Ví dụ: 19 3 (mod 8); -25 3 (mod 4)
Chứng minh: Giả sử chia a và b cho n và thu được các thương nguyên và phần dư. Các
phần dư nằm giữa 0 và n – 1, nghĩa là a = q1n + r và b = q2n + r2 . Trong đó 0 r n −1 và
0 r2 n −1. Khi đó có thể dễ dàng thấy rằng a b mod n khi và chỉ khi r = r2 . Như vậy:
a b mod n khi và chỉ khi a mod n =b mod n.
1.1.2 Tính chất cơ bản của đồng dư
Tính chất 1:
a ≡ b (mod m) c ≡ d (mod m)
2
Thì a+c ≡ b+d (mod m)
a.c ≡ b.d (mod m)
≡
Chứng minh: + Từ giả thuyết ta có a = mt + b và c= d+ ms, suy ra a+c = b+d + (t+s).m điều này có nghĩa là a+c ≡ b+d (mod m)
+ Từ giả thuyết ta có a = mt + b và c= d+ ms, suy ra a.c = b.d + (bs+td+mts). n điều này có nghĩa là a.c ≡ b.d (mod m)
Tính chất 2:
a. c ≡ b.d (a,m) = 1
Thì b ≡ c (mod m)
Tính chất 3:
Xét ℤ và quan hệ ≡ trên ℤ, ≡ là một quan hệ tương đương
i. Phản xạ : a ≡ a (mod m)
ii. Đối xứng a≡ b => b ≡ a
iii. Bắc cầu a≡ b, b≡ c => a ≡ c
2. Hệ thặng dư đầy đủ
Một họ gồm m đại diện lấy từ m lớp thặng dư được gọi là một hệ thặng dư đầy đủ module m
2.1 Định nghĩa : , ,… là hệ thặng dư đầy đủ mod m
∀ ∈ ℤ,∃! ∈ 1,2, … , , ≡ (mod m)
Ví dụ: {-4, 5, 10, 15} là một hệ thặng dư đầy đủ theo modul 4.
Ví dụ: {0, 1, 2, 3, 4} là một hệ thặng dư đầy đủ không âm bé nhất modul 5.
3
Ta có nhận xét: Một tập hợp m số (m > 1) đôi một không đồng dư theo modul m lập thành một hệ thặng dư đầy đủ theo modul m.
2.2 Tiêu chuẩn : hệ thặng dư đầy đủ
ó ℎầ ử
ℎ ℎầ ử ấ ì ℎô đồ ư
2.3 Tính chất
Nếu { , ,… , } là HTDĐĐ module m thì
+ { + , + ,… , + } là một hệ thặng dư đầy đủ mô-đun m với mọi số nguyên b
+ (a,m)=1
{ , ,… , } là một hệ thặng dư đầy đủ mô-đun m với mọi số nguyên a nguyên tố cùng nhau
3. Các định lý đồng dư
3.1 Định lý Wilson
Với p ∈ Ν∗, p>1, p là số nguyên tố(p-1) !+1 ⋮ p
(p là hợp số thì (p-1) !+1 không chia hết cho p)
Ví dụ:
p = 17
1 ≡ 1 (mod 17)
16 ≡ -1 (mod 17)
2.9 ≡ 1 (mod 17)
4
3.6 ≡ 1 (mod 17)
4.13 ≡ 1 (mod 17)
5.7 ≡ 1 (mod 17)
8.15 ≡ 1 (mod 17)
10.12 ≡ 1 (mod 17)
11.14 ≡ 1 (mod 17)
Ta có 16 ! ≡ (- 1).17
16 !+ 1 ⋮ 17
3.2 Định lý Fermat
- Định lý Fermat 1
Cho p là một số tự nhiên khác và a là một số nguyên không chia hết cho m.
Khi ấy ta có:
ap - 1 1 (mod p)
- Định lý Fermat 2
Cho p là một số nguyên tố, a là một số nguyên bât kỳ.
Khi ấy ta có:
ap - 1 a (mod p)
-Định lý fermat nhỏ:
p ∈ ℘ a ∈ ℤ
a p –a ⋮ p
5
...
- tailieumienphi.vn
nguon tai.lieu . vn