Chứng minh rằng : Trong n số tự nhiên bất kỳ bao giờ cũng chọn được 2 số có hiệu chia hết cho n-1

Để chứng minh rằng trong n số tự nhiên bất kỳ luôn có thể chọn được 2 số có hiệu chia hết cho n-1, ta sẽ sử dụng nguyên lý Dirichlet.

Giả sử ta có n số tự nhiên: a1, a2, a3, ..., an. Khi chia mỗi số a_i (với i = 1, 2, ..., n) cho (n-1), ta sẽ nhận được một trong các số dư từ 0 đến n-2. Điều này có nghĩa là có tổng cộng (n-1) số dư khác nhau mà chúng ta có thể nhận được khi chia cho (n-1).

Bây giờ, vì chúng ta có n số (a1, a2, ..., an), nhưng chỉ có (n-1) số dư, theo nguyên lý Dirichlet, sẽ có ít nhất hai trong số các số này có cùng một số dư khi chia cho (n-1). Giả sử rằng a_i và a_j (với i ≠ j) là hai số có cùng số dư r khi chia cho (n-1).

Điều này có thể được biểu diễn như sau:

a_i ≡ r (mod (n-1))
a_j ≡ r (mod (n-1))

Từ đó, ta có thể viết:

a_i - a_j ≡ 0 (mod (n-1))

Điều này suy ra rằng:

a_i - a_j = k(n-1) cho một số nguyên k nào đó.

Nói cách khác, hiệu của hai số a_i và a_j chia hết cho (n-1).

Vì vậy, ta đã chứng minh rằng trong n số tự nhiên bất kỳ, luôn có thể chọn được hai số có hiệu chia hết cho (n-1).