Ứng dụng đồng dư thức trong giải toán số học

BỒI DƯỠNG HỌC SINH GIỎI CẤP 2 |

CHUYÊN ĐỀ SỐ HỌC

A. KiÕn thøc cÇn nhí

1. Định nghĩa

Cho ,a b là các số nguyên và n là số nguyên dương. Ta định nghĩa a đồng dư với

b theo môđun n và kí hiệu là: ( ) mod a b n ≡ , nếu a và b có cùng số dư khi chia cho n.

Chú ý : a) a b(mod m) ≡ là một đồng dư thức với a là vế trái, b là vế phải.

b) a b(mod m) ≡ ⇔ a – b  m ⇔ t Z ∃∈ sao cho a = b + mt.

c) Nếu a và b không đồng dư với nhau theo môđun m ta ký hiệu :

a ≡/ b (mod m).

d) Nếu a chia cho b dư r thì ( ) mod a r b ≡

2. Tính chất

1. Tính chất phản xạ : a ≡ a (mod m).

2. Tính chất đối xứng : a ≡ b (mod m) ⇒ b ≡ a (mod m).

3. Tính chất bắc cầu :

a ≡ b (mod m); b ≡ c (mod m) ⇒ a ≡ c (mod m).

4. Cộng hay trừ từng vế của đồng dư thức có cùng môđun :

a ≡ b (mod m) ; c ≡ d (mod m) ⇒ a ± c ≡ b ± d (mod m)

Tổng quát : i i a b ≡ (mod m), i = 1; 2; ...; k ⇒ 1 2 1 2 ... ... k k a a a b b b ± ± ± = ± ± ± (mod m).

5. a) Nhân hai vế của đồng dư thức với một số nguyên :

a ≡ b (mod m) ⇒ ka ≡ kb (mod m) với k ∈Z

b) Nhân hai vế và môđun của đồng dư thức với một số nguyên dương:

a ≡ b (mod m) ⇒ ka ≡ kb (mod km) với k ∈N*

6. Nhân từng vế của nhiều đồng dư thức có cùng môđun :

a ≡ b (mod m) ; c ≡ d (mod m) ⇒ ac ≡ bd (mod m)

Tổng quát i i a b ≡ (mod m), i = 1; 2; ...; k ⇒ 1 2 1 2 ...a ... k k a a b b b ≡ (mod m).

7. Nâng hai vế của một đồng dư thức lên cùng một lũy thừa :

a ≡ b (mod m) ⇒ ak ≡ bk (mod m) (k ∈N*)

CHỦ ĐỀ

5

ỨNG DỤNG ĐỒNG DƯ THỨC

TRONG GIẢI TOÁN SỐ HỌC

.119 | CHUYÊN ĐỀ SỐ HỌC

| CHỦ ĐỀ 5: ỨNG DỤNG ĐỒNG DƯ THỨC TRONG GIẢI TOÁN SỐ HỌC

CHINH PHỤC KỲ THI HỌC SINH GIỎI CẤP HAI

8. 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à BCNN của các môđun ấy:

a ≡ b (mod i m ), i = 1; 2; ...; k ⇒ a ≡ b (mod [ ] 1 2 ; ;...; k m m m ).

Đặc biệt nếu ( ) , 1 i j m m = (i, j = 1; 2;...; k) thì

a ≡ b (mod i m ) ⇒ a ≡ b (mod 1 2 . .... k m m m ).

9. Nếu a ≡ b (mod m) thì tập hợp các ước chung của a và m bằng tập hợp các ước

chung của b và m.

Đặc biệt : a ≡ b (mod m) ⇒ (a, m) = (b, m)

10. Chia hai vế và môđun của một đồng dư cho một ước dương chung của chúng :

a ≡ b (mod m) , k ∈ UC(a,b,m), k > 0 ⇒ a b m mod k k k   ≡    

Đặc biệt : ac ≡ bc (mod m) ⇒ a ≡ b m mod (c,m)      

B. CÁC DẠNG TOÁN THƯỜNG GẶP

 Dạng 1: Sử dụng đồng dư thức trong các bài toán chứng minh chia hết

* Cơ sở phương pháp: Khi số dư trong phép chia a cho m bằng 0 thì a  m. Như vậy để

chứng tỏ a  m ta chứng minh a ≡ 0 (mod m)

* Ví dụ minh họa:

Bài toán 1. Chứng minh rằng: ( ) 5555 2222 2222 5555 7 + 

Hướng dẫn giải

Ta có: ( ) 2222 3 mod7 ≡ hay ( ) ( ) ( ) 5555 5555 2222 4 mod7 2222 4 mod7 ≡− ⇒ ≡− (*)

Mặt khác ( ) ( ) 2222 2222 5555 4 mod7 5555 4 mod7 ≡ ⇒ ≡ (**)

Từ (*) và (**)

( ) ( ) ( )

( ) ( )( )

5555 5555 222 2222

5555 222 2222 3333

2222 5555 4 4 mod7

2222 5555 4 4 1 mod7

  ⇒ + ≡ − +  

⇒ + ≡− −

Ta lại có: ( ) 1111 3333 3 1111 4 4 64 = = mà ( ) ( ) 3333 64 1 mod7 4 1 mod7 ≡ ⇒ ≡

( ) ( ) ( ) 3333 2222 3333 4 1 0 mod7 4 4 1 0 mod7 ⇒ −≡ ⇒− − ≡

Do vậy ( ) ( ) 5555 2222 2222 5555 0 mod7 + ≡ hay ( ) 5555 2222 2222 5555 7 + 

Bài toán 2. Chứng minh rằng: ( ) 2 7.5 12.6 19 n n A = + 

TỦ SÁCH CẤP 2| 120