CHIA HAI VẾ VÀ MÔĐUN CỦA MỘT ĐỒNG DƯ CHO MỘT ƯỚC DƯƠNG CHUNG CỦA C...

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 mk k mod 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:

(

²²²²

⁵⁵⁵⁵

⁺⁵⁵⁵⁵

²²²²

)

^7Hướng dẫn giải Ta có: ^{2222≡3 mod 7}

( )

hay ^{2222≡ −4 mod 7}

( )

^⇒2222

⁵⁵⁵⁵

^{≡ −}

( ) (

⁴

⁵⁵⁵⁵

^{mod 7}

)

(*)Mặt khác ^{5555≡4 mod 7}

( )

^⇒5555

²²²²

^≡4

²²²²

(

^{mod 7}

)

^(**)Từ (*) và (**)

CH IN H P H Ụ C K Ỳ T H I H Ọ C S IN H GI Ỏ I C ẤP H AI

( ) ^{( ) ( )}

 ⇒ + ≡ − + 

5555

222

5555

2222

2222 5555 4 4 mod 7

( ) ( ) ^{( )}

⇒ + ≡ − −

5555

222

2222

3333

2222 5555 4 4 1 mod 7Ta lại có: ⁴

³³³³

⁼

( )

⁴

³

¹¹¹¹

⁼⁶⁴

¹¹¹¹

^{mà 64≡1 mod 7}

^{( )}

^⇒4

³³³³

^{≡1 mod 7}

^{( )}

⇒ − ≡ ⇒ − − ≡

3333

2222

3333

4 1 0 mod 7 4 4 1 0 mod 7Do vậy

(

²²²²

⁵⁵⁵⁵

⁺⁵⁵⁵⁵

²²²²

)

^{≡0 mod 7}

^{( )}

^hay

(

²²²²

⁵⁵⁵⁵

⁺⁵⁵⁵⁵

²²²²

)

^7Bài toán 2. Chứng minh rằng: ^A=

(

^7.5

²

ⁿ

^+12.6

ⁿ

)

^19Ta có:

( )

n

n

n

n

n

= = ⇒ = +

2

2

5 5 25 7.25 12.6A

( ) ( ) ( ) ( )

≡ ⇒ ≡ ⇒ ≡ + ⇔ ≡

n

n

n

n

n

A A25 6 mod19 25 6 mod19 7.6 12.6 mod19 19.6 mod19⇒ ≡ ⇒ 0 mod19 19Bài toán 3. Chứng minh rằng 12

²ⁿ⁺¹

+ 11

ⁿ⁺²

 133 ( n ∈ N) Cách 1:Ta có 12

²

= 144 ≡ 11(mod 133) ; 11

²

= 121 ≡ –12(mod 133) Do đó 12

²ⁿ⁺¹

= 12.

( )

¹²

²

ⁿ

^{≡ 12. 11}

ⁿ

^{(mod 133)} 11

ⁿ⁺²

= 11

²

. 11

ⁿ

≡ –12. 11

ⁿ

(mod 133) Do đó 12

²ⁿ⁺¹

+ 11

ⁿ⁺²

≡ 12. 11

ⁿ

– 12. 11

ⁿ

≡ 0 (mod 133). Vậy với n ∈ N thì 12

²ⁿ⁺¹

+ 11

ⁿ⁺²

 133 . Cách 2: Ta có 12

²

= 144 ≡ 11(mod 133) ⇒12

²ⁿ

≡ 11

ⁿ

(mod 133) (1) Mà 12 ≡ – 11

²

(mod 133) (2) Nhân vế với vế của (1) và (2) ta có : 12

²ⁿ

. 12 ≡ 11

ⁿ

. (– 11

²

) (mod 133) ⇒ 12

²ⁿ⁺¹

≡ –11

ⁿ⁺²

(mod 133) 12

²ⁿ⁺¹

+ 11

ⁿ⁺²

≡ 0 (mod 133) hay 12

²ⁿ⁺¹

+ 11

ⁿ⁺²

 133.

CH UY ÊN Đ Ề S Ố H Ọ C

Bài toán 4. Chứng minh rằng: ^A=

(

²

²

²

ⁿ

^{+5 7}

)

^

⁽

^{∀ ∈n N}

⁾

Ta có ²

³

^{= ≡8 1 mod 7}

( )

Ta đi tìm số dư của 2

²

ⁿ

khi chia cho 3 (đây chính là điểm mấu chốt của bài toán). Vì ^{4≡1 mod 3}

( )

^⇒4

ⁿ

^{≡1 mod 3}

( )

^⇒2

²

ⁿ

^{≡1 mod 3}

( )

^{hay n} chia cho 3 dư 1.Giả sử: ²

²

ⁿ

^=3k+1

(

^k∈N

)

Khi đó ta có: A=2

³

^k

⁺

¹

+ =5 2.8

^k

+5 Vì ⁸

^k

^{≡1 mod 7}

( )

^⇒2.8

^k

^{≡2 mod 7}

( )

^⇒2.8

^k

^{+ ≡ +5 2 5 mod 7}

( )

0 mod 7⇒ ≡AVậy A7 Dạng 2: Sử dụng đồng dư thức tìm số dư * Cơ sở phương pháp: Với hai số nguyên a và m, m > 0 luôn có duy nhất cặp số nguyên q,r sao cho a = mq + r, 0≤ <r m. Để tìm số dư r trong phép chia a cho m ta cần tìm r sao cho  ≡a r(mod m) ≤ < . 0 r mBài toán 1. Tìm số dư khi chia 3

²⁰⁰⁰

cho 7. Ta có

2

6

2

3

≡ ⇒ ≡ ≡3 2 mod 7 3 3 1 mod 7

( ) ^{( ) ( )}

6

333

1998

⇒ ≡ ⇔ ≡3 1 mod 7 3 1 mod 7Mặt khác ³

²

^{≡2 mod 7}

( )

^⇒3

²⁰⁰⁰

^≡3

¹⁹⁹⁸

^.3

²

^{≡1.2 mod 7}

( )

^⇒3

²⁰⁰⁰

^{: 7 dư 2.}Nhận xét: Để tìm số dư khi chia a

ⁿ

cho b>0, ta lấy lũy thừa với số mũ tăng dần của a chia cho b để tìm số dư. Ta sẽ dừng lại để xem xét khi tìm được số dư có giá trị tuyệt đối nhỏ hoặc là một giá trị đặc biệt có liên quan đến bài toán. Bài toán 2. Tìm số dư trong phép chia 5

⁷⁰

+7

⁵⁰

cho 12.

( ) ( ) ^{( ) ( )( )}

2

2

35

70

≡ ⇒ ≡ ⇔ ≡5 1 mod12 5 1 mod12 5 1 mod12 *

2

2

25

50

7 1 mod12 7 1 mod12 7 1 mod12 **Từ

( ) ( )

^{* ; ** ⇒ 5}

⁷⁰

⁺⁷

⁵⁰

cho 12 dư 2.Bài toán 3. Tìm số dư của số A=3

²⁰⁰⁵

+4

²⁰⁰⁵

khi chia cho 11 Ta có ³

⁵

=243 1 mod11≡

( )

⇒

( )

3

⁵

⁴⁰¹

≡1 mod11

^{( )}

⇒3

²⁰⁰⁵

≡1 mod11 1

^{( )( )}

Mặt khác ⁴

⁵

^{=1024≡1 mod11}

( )

^⇒

( )

⁴

⁵

⁴⁰¹

^{≡1 mod11}

^{( )}

^⇒4

²⁰⁰⁵

^{≡1 mod11 2}

^{( )( )}

Từ

( ) ( )

^{1 ; 2 ⇒} số dư của số A=3

²⁰⁰⁵

+4

²⁰⁰⁵

khi chia cho 11 là 2.Bài toán 4. a) Tìm số dư trong phép chia 1532

⁵

– 1 cho 9. b) Tìm số dư trong phép chia 2016

²⁰¹⁸

+ 2 cho 5a) Ta có 1532 = 9.170 + 2 ≡ 2 (mod 9) do đó 1532

⁵

≡ 2

⁵

(mod 9)⇒ 1532

⁵

– 1 ≡ 2

⁵

– 1 (mod 9) . Vì 2

⁵

– 1 = 31 ≡ 4 (mod 9). Do đó1532

⁵

– 1 ≡ 4 (mod 9). Vậy số dư cần tìm là 4. b) Ta có 2016 ≡ 1 (mod 5) do đó 2016

²⁰¹⁸

≡ 1

²⁰¹⁸

(mod 5)suy ra 2016

²⁰¹⁸

+ 2 ≡ 1

²⁰¹⁸

+ 2 (mod 5) . Vì 1 + 2 = 3 ≡ 3 (mod 5). Do đó 2016

²⁰¹⁸

+ 2 ≡ 3 (mod 5). Vậy số dư cần tìm là 3.  Dạng 3: Tìm điều kiện của biến để chia hết * Cơ sở phương pháp: Dựa vào tính chất của đồng dư thức về số dư để tìm ra điều kiệncủa ẩn để biểu thức chia hết. Bài toán 1. Tìm số tự nhiên n sao cho: a.

(

²

³

ⁿ

⁺

⁴

⁺³

²

ⁿ

⁺

¹

)

^{19 b.}

(

^n.2

ⁿ

^{+1 3}

)

^a. Ta có 2

³

ⁿ

⁺

⁴

+3

²

ⁿ

⁺

¹

=16.8

ⁿ

+3.9

ⁿ

Vì ^{16≡ −3 mod19}

( )

^⇒16.8

ⁿ

^{≡ −3.8}

ⁿ

(

^mod19

)

⇒ + ⇔ − + ≡