Báo cáo tiểu luận môn học: Số học và logic - Đồng dư và các định lý đồng dư giới thiệu tới người đọc kiến thức cơ bản về đồng dư, hệ thặng dư đầy đủ, các định lý đồng dư, ứng dụng của đồng dư. Mời các bạn cùng tham khảo.
AMBIENT/
Chủ đề:
Nội dung Text: Báo cáo tiểu luận môn học: Số học và logic - Đồng dư và các định lý đồng dư
- ĐẠ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: SỐ HỌC VÀ LOGIC
ĐỀ TÀI: ĐỒ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 r1 và b q 2 n r2 . Trong đó 0 r1 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 r1 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
- (a,p) =1
ap-1 ≡ 1 (mod p)
!
Bổ đề : = ⋮ với 1≤ ≤ −1
!( )!
Ví dụ 1: Tìm 32012 mod 7
Giải: lấy 2012 chia cho 6, ta có: 2012=6.335+2 vậy thì
32012 = 36.335 + 2 = (36)335.32 =
Ví dụ 2: Chứng minh rằng nếu a1 + a2 + a3 + a4 + a5 ≡ 0 (mod 5) thì a15 + ... + a55 ≡ 0
(mod 5)
Giải: 5 là số nguyên tố Þ theo định lý Fermat nhỏ:
≡ ( 5); = 1,5
⇒ ≡ ( 5) ≡ 0 ( 5)
Ví dụ 3: Chứng minh rằng =1 +2 + ⋯ + 11 không chia hết cho 11
Giải: Với mọi = 1,2, … ,10 ℎì ( , 10) = 1. Do đó theo định lý Fermat nhỏ thì ≡
1( 11) ⇒ ≡1( 11) với mọi = 1,2, … ,10 à 11 ≡0( 11). Như
vậy
≡ 1 + 1 + ⋯+ 1 + 0 ( 11)
10 số 1
≡ 10 ( 11) ⇒ ℎô ℎ ℎế ℎ 11
3.3 Định lý Euler
Cho m là một số tự nhiên khác 0 và a là một số nguyên tố với m.
( )
Khi ấy ta có: ≡ 1 (mod m)
6
- Ví dụ 1: Tìm số dư trong phép chia 109345 chia cho 14
Giải:
Ta có: 109 -3 (mod 14)
=> 109345 (-3)345 (mod 14)
Ta lại có: ( -3; 14 ) = 1
1 1
Hơn nữa: µ(14) = 14.(1 )(1 ) 6
2 7
Nên: (-3)6 1 (mod 14) (theo đ ịnh l ý Ơle)
=> (-3)345 (-3)3 (mod 14)
Mặt khác: (-3)3 = -27 1 (mod 14)
Vậy số dư trong phép chia 109345 chia cho 14 là 1
34 n 1
Ví dụ 2: Chứng minh 2 311 với n là số tự nhiên
1 1
Giải: Ta có: µ(11) = 10; µ(10) = 10(1 )(1 ) = 4.
2 5
Áp dụng ĐL Eucler ta có: (3; 10) = 1 => 3µ(10) 1 (mod 10)
34 1 (mod 10) => 34n + 1 3 (mod 10)
Đặt 34n + 1 = 10.k + 3 với k N.
34 n 1
Khi đó ta có: 2 3 210.k 1 3
Áp dụng định lý Eucler ta có: (2; 11) = 1
Nên 2µ(11) 1 (mod 11)
210 1 (mod 11) => 210.k +3 23 (mod 11)
7
- 34 n 1
=> 210.k +3 + 3 23 +3 (mod 11) 2 3 0 (mod 11)
34 n 1
Vậy 2 311
Ví dụ 3: Tìm 2 chữ số tận cùng của 20092010
Giải: Ta có: 20092010 92010 (mod 100)
Áp dụng định lý Eucler ta có: (9; 100) =1
µ(100) 1 1
Nên: 9 1 (mod 100). Mà µ(100) = 100.(1 )(1 ) 40
2 5
Hay: 940 1 (mod 100) => 92010 910 (mod 100)
Mà 910 = 3486784401 1 (mod 100).
3.4 Định lý Trung hoa về số dư
Cho n số nguyên dương m1 , m2 ,..., mn số nguyên dương đôi một nguyên tố cùng nhau.
Khi đó hệ đồng dư tuyến tính
x ai (mod mi )
i 1, n
có nghiệm duy nhất mođun M m1m2 ...mn .
4. Ứng dụng
4.1. Tìm số dư trong phép chia
Ví dụ1 : Tìm số dư trong phép chia: 29455 – 3 chia cho 9
Giải: Ta có: 2945 2 (mod 9)
=> 29455 – 3 25 – 3 (mod 9)
8
- Mà 25 – 3 2 (mod 9)
Vậy số dư của 29455 – 3 chia cho 9 là 2
Ví dụ 2:Tìm số dư trong phép chia: (19971998 + 19981999 +19992000 )10 chia cho 111
Giải: Ta có: 1998 0 (mod 111)
=> 1997 -1 (mod 111) và 1999 1 (mod 111)
Nên ta có: 19971998 + 19981999 +19992000 2 (mod 111)
(19971998 + 19981999 +19992000 )10 210 (mod 111)
Mặt khác ta có: 210 = 1024 25 (mod 111)
Vậy (19971998 + 19981999 +19992000 )10 chia cho 111 có số dư là 25
Ví dụ 3: Chứng minh 62n + 1 + 5n + 2 chia hết cho 31 với mọi n là số tự nhiên
Giải:
Ta có: 62 5 (mod 31) => 62n 5n (mod 31)
Mặt khác: 6 - 52 (mod 31)
Nên: 62n + 1 -5n + 2 (mod 31)
Vậy 62n + 1 + 5n + 2 chia hết cho 31.
4.2. Chứng minh chia hết
Ví dụ 1: Chứng minh: 3100 – 3 chia hết cho 13
Giải.
Ta có: 33 = 27 1 (mod 13)
=> 3100 = 3.399 3.1 (mod 13)
=> 3100- 3 0 (mod 13). Vậy 3100-3 chia hết cho 13
9
- 4.3. Tìm chữ số tận cùng
Ví dụ 1: tìm 2 chữ số tận cùng của 19 2015
Ta có 19 ≡ 19 (mod 100)
19 2 ≡ 61 (mod 100)
193 ≡ 21 (mod 100)
…
1920 ≡ 01 (mod 100)
192015 =(1920)100. 1915 = 1915 (mod 100)
Vậy 2 chữ số tận cùng là 99
5. Một số bài tập
5.1. Tìm số dư trong các phép chia:
a) 6635 chia cho 11
b) 171999 chia cho 6
c) 270 + 370 chia cho 13.
d) 53999 chia cho 17.
5.2. Tìm 2 chữ số tận cùng bên phải của các số sau trong hệ thập phân:
a) 21999
b) 999
c) 262000
d) 72003
5.3 (IMO 1989) : Chứng minh rằng với mọi số nguyên dương n bất kì, luôn tồn tại n số
nguyên dương liên tiếp mà trong đó không có số nào là lũy thừa của một số nguyên tố.
10
- 5.4. Cho m, n là 2 số tự nhiên lớn hơn 1 và (m,n) = 1.
Chứng minh: mj(n) + nj(m) ≡ 1 (mod mn)
5.5. Chứng minh: 12000 + 22000 + 32000 + ... + 102000 ≡ -1 (mod 11)
5.6. Cho (a,m) = 1 và a, b là 2 số tự nhiên sao cho a º b (mod j(m)) với j(m): hàm
Euler. Chứng minh: aa º ab (mod m).
5.7. Cho p nguyên tố. Chứng minh: [(p!)2 - p2] ⋮ p3.
5.8. Cho ∈ ; ≥ 5. Chứng minh rằng nếu n+2 nguyên tố thì (n!-1) là hợp số.
5.9. Tìm các số nguyên tố p, q thỏa mãn (7p−5p)(7q−5q) chia hết cho pq.
5.10. Tìm các số nguyên tố p, q thỏa mãn 2p+2q chia hết cho pq.
5.11. Tìm số nguyên dương n thỏa mãn: Với mọi cặp số nguyên a, b thỏa
mãn a2b+1 chia hết cho n ta luôn có a2+b chia hết cho n
5.12. Cho số nguyên tố lẻ p và các số nguyên dương a, b, n thỏa mãn (a, p)=1 và ap ≡ bp
(mod pn+1) Chứng minh rằng: a ≡ b (mod pn)
Bài tập về định lý số dư Trung hoa
1.Chứng minh rằng tồn tại số nguyên k sao cho 2 n k 1 là hợp số với mọi số nguyên
dương n.
2. 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) n k 1 là hợp số với mọi số nguyên dương n.
3. Cho số nguyên dương n p1 p2 ... pk , trong đó p1 , p2 ,..., pk là các số nguyên tố đôi
1 2 k
một khác nhau. Tìm số nghiệm của phương trình đồng dư x 2 x 0(mod n) .
4. Tìm số nguyên dương n lẻ sao cho với mọi hệ thặng dư thu gọn mođun n
a , a ,..., a ta có a a ...a
1 2 (n) 1 2 ( n) 1(mod n) .
5. . Chứng minh rằng với mọi số tự nhiên n, luôn tồn tại n số tự nhiên liên tiếp sao cho
bất kì số nào trong các số đó cũng đều là hợp số.
11
- 6. Chứng minh rằng với mọi số tự nhiên n, luôn tồn tại n số tự nhiên liên tiếp sao cho
bất kì số nào trong các số đó cũng đều không phải là luỹ thừa (với số mũ nguyên lớn
hơn 1) của một số nguyên tố.
7. . Chứng minh rằng với mỗi số tự nhiên n, tồn tại một cấp số cộng gồm n số hạng
sao cho mọi số hạng của nó đều là luỹ thừa của một số tự nhiên với số mũ lớn hơn 1.
8. Cho A là tập con khác rỗng của N. Chứng minh rằng tồn tại số nguyên dương n sao
cho nA {nx | x A} là tập hợp là luỹ thừa của một số tự nhiên với số mũ lớn hơn 1.
Tài liệu tham khảo
[tl1]: Châu Hoàng Lâm 2015 lý thuyết đồng dư và một số ứng dụng
http://violet.vn/chauhoanglam2012/present/same/entry_id/7634554
[tl2]: Lê Văn Ngọc 2015 lý thuyết đồng dư và một số ứng dụng
http://www.slideshare.net/thuvienso24h/l-thuyt-ng-d-v-ng-dng
[tl3]: Đồng dư thức 2015 http://documents.tips/documents/dong-du-thuc.html
[tl4] 2015 http://websrv1.ctu.edu.vn/coursewares/supham/sohoc/sohoc_6-2.htm
12
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
