Chuyên đề Bồi dưỡng HSG Các phương pháp giải bài toán chia hết

Cách 5: Dùng nguyên tắc Dirichlet:
Nguyên tắc Dirichlet phát biểu dưới dạng hình ảnh như sau:
Nếu nhốt k chú thỏ vào m chuồng mà k> m thì phải nhốt ít nhất hai chú thỏ vào chung một chuồng.
Ví dụ: Chứng minh rằng trong m + 1 số nguyên bất kì thế nào cũng có hai số có hiệu chia hết cho m.
Giải: Chia một số nguyên bất kì cho m ta được số dư là một trong m số 0; 1 ; 2; 3; ...; m - 1. Theo nguyên tắc Dirichlet, chia m + 1số cho m thì phải có ít nhất hai số có cùng số dư . Do đó hiệu của hai số này sẽ chia hết cho m.