đồng dư và các ứng dụng của đồng dư

Tập H gồm nhũng số nguyên lấy ra ở mỗi lớp thặng dư của Z một và chỉ một số được gọi là một hệ thặng dư đầy đủ môđun m.Như vậy: m Tập hợp H gồm những số nguyên là một hệ thặng dư đầy đủ

MỤC LỤC

A CƠ SỞ LÝ THUYẾT 1

1 ĐỊNH NGHĨA ĐỒNG DƢ 1

2 CÁC TÍNH CHẤT CỦA QUAN HỆ ĐỒNG DƢ 1

3 CÁC ĐỊNH LÝ ĐỒNG DƢ 4

4 HỆ THẶNG DƢ ĐẦY ĐỦ - HỆ THẶNG DƢ THU GỌN 5

B ỨNG DỤNG 8

1 TÌM SỐ DƢ CỦA PHÉP CHIA 8

2 TÌM CHỮ SỐ TẬN CÙNG 10

3 CHỨNG MINH SỰ CHIA HẾT 11

4 PHÂN VÙNG BỘ NHỚ 14

5 KÝ SỐ KIỂM TRA ( CHECK DIGITS) 15

6 ỨNG DỤNG TRONG MÃ HÓA THÔNG TIN 18

C TRÒ CHƠI ĐỒNG DƢ 21

MỘT SỐ TRÒ CHƠI CÓ LỜI GIẢI: 21

MỘT SỐ TRÒ CHƠI THAM KHẢO VÀ THỬ THÁCH ĐỘC GIẢ 25

D TÀI LIỆU THAM KHẢO 26

số nguyên p1, p2, r với 0  r < m sao cho a = mq1 + r và b = mq2 + r

Khi a và b đồng dư với nhau theo môđun m, ta viết a ≡ bmod m

Nếu a không đồng dư với b theo môđun m thì ta viết a  bmod m

Định lý

Các mệnh đề sau là tương đương

i a và b đồng dư với nhau theo môđun m;

ii a – b chia hết cho m (kí hiệu là m|(a-b));

iii Tồn tại số nguyên t sao cho a = b+mt

Chứng minh

i  ii Ta có a ≡ bmod m a = mq1 + r và b = mq2 + r, với q1,q2,rZ, 0  r < m Suy ra abm(q1q2) Do q1,q2Znên m|(a - b)

ii iii Giả sử m|(a-b) Khi ấy tồn tại số t Zsao cho a-b  mt, tức là a = b + mt

iii i Giả sử có số t  sao cho a = b + mt Gọi r là số dư trong phép chia a cho m, nghĩa

là amq1rvới q1,rZ, 0  r < m Khi ấy: bmtamq1r haybm(q1t)r

trong đó (q1t)Z, 0  r < m Chứng tỏ số dư trong phép chia b cho m cũng là r, tức là

a ≡ b mod m

2 CÁC TÍNH CHẤT CỦA QUAN HỆ ĐỒNG DƢ

a) Quan hệ đồng dư là một quan hệ tương đương trên tập Z:

i Phản xạ: Với mọi a  Z : a ≡ a mod m;

ii.Đối xứng: Với mọi a ,b  Z: a ≡ b mod m khi và chỉ khi b ≡ amod m;

iii.Bắc cầu: Với mọi a, b, c  Z : a  b mod m , b  c mod m 

suy ra a  c mod m

Chứng minh

i Vì a – a chia hết cho m nên a  a mod m 

ii Từ a  b mod m  ta có m|(a - b) Do đó m|(b – a ) b ≡ a mod m

iii Ta có a ≡ bmod m và b ≡ cmod m nên m|( a - b)và m|(b - c)

Khi đó m|((a- b )+(b- c)) hay m|(a- c) Vậy a ≡ c mod m

b) Ta có thể cộng hoặc trừ từng vế của nhiều đồng dư thức theo cùng một môđun

Cụ thể là, nếu a1b1(modm)và a2 b2(modm)thì ta có:a1a2b1b2(modm)

Chứng minh

Từ a1 b1(modm),a2 b2(modm)suy ra tồn tại t1,t2Zsao choa1b1mt1,

2 2

a   Do đó a1a2 b1b2m(t1t2)với t1,t2Z Vậy

)(mod

2 1 2

c) Ta có thể nhân từng vế của nhiều đồng dư thức theo cùng một môđun

Cụ thể là, nếu a1 b1(modm), a2 b2(modm)thì a1a2 b1b2(modm)

Chứng minh

Từ a1 b1(modm),a2 b2(modm)suy ra tồn tại t1,t2Z sao cho a1b1mt1,

2 2

a   Do đó a1a2 b1b2 m(b2t1b1t2mt1t2), với b2t1b1t2mt1t2 Vậy a1a2 b1b2(modm)

Thật vậy, a ≡ bmod m, km ≡ 0mod m Vậy a ± km ≡ bmod m

iv a ≡ bmod m an ≡ bnmod m n Z+

Chứng minh

Ta có a ≡ bmod m ; a ≡ bmod m; a n b n (mod m)

v Giả sử f(x) là một đa thức với hệ số nguyên và   mod m Khi ấy

f(α) ≡ f(β)mod m Đặc biệt, nếu f(α) ≡ 0mod m thì f(α + km) ≡ 0mod m

với mọi k Z

Chứng minh:

Thật vậy, giả sử f(x) = a0 + a1x + a2x2 + + anxn Từ giả thiết α ≡ βmod m

suy ra a ii a ii (mod m) với i = 1, 2, , n

Do đó:

nghĩa là f(α) ≡ f(β) mod m

Đặc biệt, vì  k Z nên f(α)≡ f(α + km)mod m Nhưng f(α) ≡ 0modm nên ta có f(α + km) ≡0mod m với mọi k  Z

vi Ta có thể chia hai vế của một đồng dư thức cho một ước chung của chúng nguyên tố cùng nhau với môđun m:

ac ≡ bc mod mvà UCLN(c, m)=1  a ≡ bmod m

1 1 1 1 1 1 1

a



viii Nếu hai số đồng dư với nhau theo một môđun thì chúng cũng đồng

dư theo môđun là ước của môđun ấy:

a ≡ b mod m, δ|m, δ > 0  a ≡ bmod δ 

Chứng minh

Từ a ≡ bmod m m|(a - b), mà δ|m  δ|(a - b) a ≡ b(mod δ)

ix Nếu hai số đồng dư với nhau theo nhiều môđun thì chúng đồng dư với nhau

theo môđun là bội chung nhỏ nhất của các môđun ấy:

)(modm i b

a với mọi i 1, , k a ≡ bmod m với m=BCNN(m1,m2, ,m k)

Với p là số nguyên tố, ta có a p a (mod p)

Đặc biệt nếu (a, p) =1 thì a p11(mod p)

b) Định lý Euler:

 Hàm số phi Euler- (m)

 Hàm nhân tính số học : Một hàm xác định trên tập hợp các số nguyên dương được gọi là hàm số học

Hàm số học f được gọi là nhân tính nếu với mọi cặp số nguyên m, n

p1  3 

3 2 2

) (

Cho m là một số nguyên dương Tập H gồm nhũng số nguyên lấy ra ở mỗi lớp thặng

dư của Z một và chỉ một số được gọi là một hệ thặng dư đầy đủ môđun m.Như vậy: m Tập hợp H gồm những số nguyên là một hệ thặng dư đầy đủ môđun m khi và chỉ khi:

- Các phần tử của H đôi một không đồng dư với nhau theo môđun m

- Mỗi số nguyên đều đồng dư theo môđun m với một số nào đó thuộc H

- Mỗi một số nguyên của H được gọi là một thặng dư

Ví dụ với m = 8 ta có: Z8  0,1,2,3,4,5,6, }là một hệ thặng dư đầy đủ môđun 8, nó được gọi là hệ thặng dư đầy đủ không âm nhỏ nhất Còn hệ{3,2,1,0,1,2, } là một

hệ thặng dư môđun 8, hệ này được gọi là hệ thặng dư đầy đủ giá trị tuyệt đối nhỏ

nhất

Tổng quát

 H ={0, 1, ., m - 1} là một hệ thặng dư đầy đủ môđun m và nó là hệ

thặng dư đầy đủ không âm nhỏ nhất

1

;2





H là một hệ thặng dư đầy đủ môđun m

được gọi là hệ thặng dư đầy đủ giá trị tuyệt đối nhỏ nhất

 Với m là một số chẵn, ta có

2

; ;

12

;2

m m

m

H    là hệ thặng dư đầy đủ giá trị tuyệt đối nhỏ nhất

 Tính chất 1

Mỗi hệ thặng dư đầy đủ môđum m đều gồm m phần tử

Chứng minh Hiển nhiên vì tập m có m phần tử

 Cho m là một số nguyên dương Tập hợp K gồm những số nguyên được lấy ra

ở mỗi lớp nguyên tố cùng nhau với môđun m một và chỉ một số được gọi là một hệ thặng dư thu gọn môđun m Vậy một tập hợp K gồm những số nguyên được gọi là một hệ thặng dư thu gọn môđun m nếu và chỉ nếu:

- Các phần tử thuộc K đôi một không đồng dư với nhau theo môđun m

- Các phần tử thuộc K nguyên tố cùng nhau với môđun m

- Mỗi số nguyên tùy ý nguyên tố cùng nhau với môđun m đều đồng dư với 1số nào đó thuộc K

Nhận xét

Mỗi hệ thặng dư đầy đủ đều chứa duy nhất một hệ thặng dư thu gọn

Hệ thặng dư thu gọn không âm nhỏ nhất{r1,r2, ,r(m)} thu gọn gồm các phần

tử 0r i m, {r1,r2, ,r(m)}nguyên tố cùng nhau với m Ta có khái niệm hệ thặng dư thu gọn môđun m có trị tuyệt đối nhỏ nhất

Giả sử b là một số nguyên bất kì Khi ấy nếu x chạy qua một hệ thặng

dư thu gọn môđun m thì x + b cũng chạy qua một hệ thặng dư thu gọn môđun m

B ỨNG DỤNG

Đồng dƣ là một khái niệm toán học cơ bản, đơn giản và sơ cấp nhưng cũng rất quan trọng

trong số học Lý thuyết đồng dư thường được giảng dạy trong chương trình trung học cơ sở, làm khuôn khổ để phát biểu và chứng minh một trong những định lý toán học thực sự đầu tiên mà học sinh được học, đó là định lý Fermat nhỏ

Lý thuyết đồng dư cho ta phương pháp đồng dư (phương pháp mô – đu – lô) , một phương pháp có tính kỹ thuật giúp chúng ta giải quyết một số bài toán với số nguyên Sau đây, chúng tôi xin đề cập đến 3 dạng toán cơ bản có thể giải quyết dễ dàng bằng phương pháp đồng dư Đồng thời phần này cũng đề cập đến nhiều ứng dụng của động dư trong thực tế

1 TÌM SỐ DƢ CỦA PHÉP CHIA

 MỘT SỐ BÀI TẬP CÓ LỜI GIẢI

Bài 1: Tìm số dƣ trong phép chia cho 11

Giải:

Ta có: 2002 11

=> 2004 – 2 11

=>

Do đó,

Theo định lí Euler:

=>

Vậy chia 11 dƣ 5 Bài 2: Tìm số dƣ khi A = chia 7 Ta có

=>

Theo định lí Euler:

=>

Vậy chia 7 dƣ 5 Bài 3: Tìm số dƣ của A = khi chia cho 3 và chia cho 5? + Tìm số dư khi A chia cho 3 Ta có: =>

Theo định lí Euler: =>

Ta có: =>

Ta có: =>

 Vậy A = chia 3 dư 2 + Tìm số dư khi A chia 5 Ta có: =>

Ta có: =>

Theo định lí Euler: =>

Ta có: =>

Theo định lí Euler: =>

=>

 Vậy A= chia 5 dư 2

 MỘT SỐ BÀI TẬP TỰ LUYỆN

Bài 4: Tìm số dƣ của phép chia chia cho 14?

Bài 5: Tìm số dƣ của B = chia cho 111?

Bài 6: Tìm số dƣ của C = khi chia cho 11 và 13?

Tài liệu tham khảo:

Nguyễn Duy Đông , Chuyên đề BDHSG THCS 2014- THCS Yên Lạc

2 TÌM CHỮ SỐ TẬN CÙNG

Phương pháp: Để tìm n chữ số tận cùng của một số nguyên A, ta tìm số dư của A khi

chia cho

 MỘT SỐ BÀI TẬP CÓ LỜI GIẢI

Bài 1: Tìm 1 chữ số tận cùng (chữ số hành đơn vị) của ?

Ta có:

=>

Mà:

Vậy có chữ số hàng đơn vị là 9 Bài 2: Tìm 2 chữ số tận cùng của ?

Ta có:

=>

Ta có:

=>

Vậy 2 chữ số tận cùng của là 43 Bài 3: Tìm 2 chữ số tận cùng của A = ?

Ta có: A =

Ta có:

=>A =

Vậy A = có 2 chữ số tận cùng là 32  MỘT SỐ BÀI TẬP TỰ LUYỆN Bài 4: Tìm chữ số hàng chục của ?

Bài 5: Tìm 2 chữ số tận cùng của ?

Bài 6: Tìm 2 chữ số tận cùng của

Tài liệu tham khảo: Nguyễn Duy Đông , Chuyên đề BDHSG THCS 2014- THCS Yên Lạc http://www.vietmaths.net/2015/05/xem-ly-thuyet-ong-du-va-ung-dung-trong.html 3 CHỨNG MINH SỰ CHIA HẾT  MỘT SỐ BÀI TẬP CÓ LỜI GIẢI Bài 1: Chứng minh:

Theo định lí Fermat nhỏ ta có: Với p là số nguyên tố và a không chia hết cho p thì

Ta nhận thấy 2003 là số nguyên tố Các số 1, 2, 3, …, 2002, 2004,…, 2008 nguyên tố cùng nhau với 2003 Đặt S = {1, 2, …, 2002, 2004, …, 2008} Với mọi

Và 2003

Do đó:

(mod 2003)

 (mod 2003) (có 2007 số)

Nguyễn Duy Đông , Chuyên đề BDHSG THCS 2014- THCS Yên Lạc

Bài 3 : Chứng minh rằng: chia hết cho 11

Theo định lí Fermat, ta có: Nếu p là số nguyên tố và a là số nguyên bất kì thì

Theo định lí Fermat, ta có:







Mà 1991

Suy ra:

Do đó:

Vậy

http://dethi.violet.vn/present/show/entry_id/6091851/cm_id/3153671 Bài 4: Chứng minh

Đặt A=

Ta chứng minh A

Ta có: =>

Suy ra:

http://www.vietmaths.net/2015/05/xem-ly-thuyet-ong-du-va-ung-dung-trong.html  MỘT SỐ BÀI TẬP TỰ LUYỆN Bài 5: Cho số nguyên dương n >1 Chứng minh rằng không chia hết cho (Đề nghị Olympic 30-4 toán 10 năm 2013 THPT Chuyên Lương Văn Chánh, Phú Yên) Bài 6: Tìm tất cả các số tự nhiên n để chia hết cho 5 Bài 7: (Russia MO 1997) Cho m, n là hai số nguyên dương sao cho chia hết cho Chứng minh rằng n chia hết cho m(

4 PHÂN VÙNG BỘ NHỚ

Giả sử mỗi hồ sơ khách hàng trong công ty bạn được gán bằng một chuỗi số có độ dài bằng 10 ký số Để truy xuất dữ liệu hồ sơ khách hàng một cách nhanh chóng, ta không muốn phải tìm kiếm từng hồ sơ một Vì như vậy khi tìm kiếm sẽ rất mất thời gian.Để tránh tình trạng này ta sẽ sử dụng một số nguyên nhỏ hơn để liên kết với mỗi chuỗi mã này Việc làm này giống như việc ta phân loại những đồ dùng có cùng tính chất vào cùng một tủ Vì thế việc tìm kiếm sẽ trở nên dễ dàng hơn Vậy làm sao để phân loại các chuỗi mã này ?

Bằng việc ứng dụng lý thuyết động dư ta thấy

Với k là mỗi chuỗi mã của từng hồ sơ khách hàng Xét hàm :

h(k) = k mod m ( m là số lượng vùng nhớ có sẵn)

Với cách làm này ta có thể phân các chuỗi mã vào các lớp thặng dư modulo m Nói cách khác các chuỗi mã số đã được phân vào các vùng bộ nhớ được đánh số từ 0 đến m-1.Ta thấy đây là một toàn ánh, nghĩa là mọi chuỗi mã đều được phân vào một lớp thặng dư nào đó Vì thế, thay vì tìm kiếm từng chuỗi mà như ban đầu ta có thể tìm kiếm thông qua mỗi vùng bộ nhớ mà không cần quan tâm đến các chuỗi ở các vùng còn lại Việc làm này sẽ tiết kiệm rất nhiều thời gian

Ví dụ: Tìm vùng bộ nhớ của hồ sơ khách hàng có mã số 0987654321 và 0123456789 Biết rằng hồ sơ được phân theo hàm h(k) = k mod 113

5 KÝ SỐ KIỂM TRA ( CHECK DIGITS)

Các mã nhận diện có thể thấy ở khắp mọi nơi trong cuộc sống ngày nay Từ các loại sản phẩm, hàng hóa, thẻ ATM đến giấy phép lái xe, tiền tệ Một trong những ứng dụng khá phổ biến của đồng dư chính là tạo ra các ký số kiểm tra cho các loại mã này Thông qua ký số này người ta có kiểm tra xem các mã được gán cho một loại sản phẩm hàng hóa là đúng hay sai Để từ đó có sự điều chỉnh, thay thế phù hợp Một kỹ thuật phổ biến cho việc dò ra lỗi sai trong các loại mã này là thêm vào một ký số bổ sung vào phía cuối của chuỗi Ký tự kiểm tra này được tính bằng một hàm cụ thể đối với từng loại mã khác nhau Sau đây là một số mã phổ biến

Mã UPCs ( Universal Product Codes – mã sản phẩm chung)

Đây là mã được in trên các loại sản phẩm bán lẻ với dạng thông dụng nhất có 12

ii Để kiểm tra liệu 041331021641 có hợp lệ không, ta sẽ thay các ký số này vào đồng dư thức ở trên để kiểm tra

Rút gon ta có :

Vậy mã trên không hợp lệ

Mã ISBNs (international standard book number – mã sách chuẩn quốc tế)

Đây là mã được in trên các loại sách được ấn định bởi các nhà xuất bản Có hai loại ISBN-10 và ISBN-13 tương ứng có 10 và 13 ký số Với ký số kiểm tra đặt ở cuối cùng có dạng một chữ số hoặc chữ cái X (thay cho chữ số 10) Ở đây chúng

ta sẽ tìm hiểu dựa trên mã ISBN-10

Gọi các ký số trong mã ISBNs lần lượt là x1, x2, , x10 Ký số kiểm tra được tính bằng đồng dư thức sau :

∑

Hoặc

∑

Ta có

x10 1.x1 + 2.x2 + 3.x3 + 4.x4 + 5.x5 + 6.x6 + 7.x7 + 8.x8 + 9.x9 1.0 + 2.0 + 3.7 + 4.2 + 5.8 + 6.8 + 7.0 + 8.0 + 9.8

189 Vậy ký số kiểm tra là 2

ii Thay mã 084930149X vào công thức:

∑

Ta có

1.x1 + 2.x2 + 3.x3 + 4.x4 + 5.x5 + 6.x6 + 7.x7 + 8.x8 + 9.x9 + 10.x10 1.0 + 2.8 + 3.4 + 4.9 + 5.3 + 6.0 + 7.1 + 8.4 + 9.9 + 10.10

Vậy mã 084930149X không là mã ISBN hợp lệ

Một số mã khác

 Mã USPS ( Bưu chính hoa kỳ)

Ký số kiểm tra : ∑

 Mã ISSN ( Mã số tạp chí quốc tế)

Ký số kiểm tra: ∑ Nếu x8 ta ký hiệu x8 là chữ X

6 ỨNG DỤNG TRONG MÃ HÓA THÔNG TIN

Mã hóa là một bài toán đã được con người đặt ra cách đây hàng ngàn năm Mật mã đầu tiên được đưa ra bởi Julius Caesar cách đây hơn 4000 ngàn năm Mã hóa ngày nay có những bước phát triển vượt bậc Đây là một chủ đề rộng lớn Trong phần này chúng tôi chỉ giới thiệu một số loại mật mã cũng như việc ứng dụng lý thuyết đồng dư vào việc tạo ra chúng Một số ứng dụng phổ biến của các loại mã này có thể được tìm thấy trong các trò chơi giải mật thư, trò chơi trạm của các tổ chức đoàn thể, trong các dịp cắm trại

Mật mã thay thế ( Shift Cipher )

Mã này được xây dựng trên mô hình mà Caesar đã đưa ra Ông đã tạo ra một bức thư bí mật bằng cách thay thế mỗi chứ cái bằng chữ cái cách nó ba vị trí về phía sau trong bảng chữ cái alphabet Ví dụ A được thay bởi D, B được thay bởi E Đối với ba chữ cái cuối cùng X, Y, Z lần lượt được thay bởi A, B, C

Một cách tổng quát

Biểu diễn mỗi chữ cái trong bản chữ cái alphabet là một phần tử của Z26: A = 0, B

= 1, , Y = 24, Z = 25.Ánh xạ f biến một số nguyên không âm p < 26 thành số nguyên f(p) trong tập {0,1,2, ,25} với

f (p) = ( p + k ) mod 26 ( k được gọi là khóa)

Trong văn bản mã hóa, các chữ cái được biểu diễu bởi p sẽ được thay bằng chữ

cái được biểu diễn bởi ( p + k ) mod 26