1. TÌM S Ố DƯ KHI CHIA A CHO B > 0 N ẾU A ≡ R ( MOD B ) VÀ...

2.1. Tìm s ố dư khi chia a cho b > 0

N ếu ^{a ≡ r} ( ^{mod b} ) ^{và 0 ≤ < r b thì r là s} ố dư khi chia a ^cho b .

Ví d ụ 4. Tìm s ố dư khi chia 3

²⁰⁰⁰

cho 7.

Gi ải

Ta có: ³

²

^{≡ 2 mod 7} ( ) ^{⇒ 3}

⁶

⁼ ( ) ³

²

³

^{≡ 1 mod 7 ( )}

( ) ³

⁶

³³³

^{1 mod 7 ( )}

⇒ ≡ hay ³

¹⁹⁹⁸

^{≡ 1 mod 7.} ( )

M ặt khác: ³

²

^{≡ 2 mod 7} ( ) ^{nên 3}

²⁰⁰⁰

^{= 3}

^{1998 2}

^{3 ≡ 1.2 mod 7} ( )

hay 3

²⁰⁰⁰

chia cho 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 các tình huống của bài toán.