nguyên lí đrích-lê

[huradeli]

[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!

ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.

1,chứng minh rằng tồn tại số tự nghiên k sao cho $ 2013^k-1$ chia hết cho 107
2,cho tập hợp $X={1;2;3;4;...;2009}$, chon trong $X$ 1006 số. chứng minh rằng:trong 1006 số đo tồn tại ít nhất 2 số có tổng 2010

 

[tanngoclai]

Bài 2 :

Ta có : $2010 = 1 + 2009 = 2 + 2008 = 3 + 2007 = ... = 1004 + 1006$ ( có 1004 cặp số )

Gọi các cặp số là : $(a_1;b_1);(a_2;b_2);(a_3;b_3);...;(a_{1004};b_{1004})$ sao cho $a_n + b_n = 2010$ hay các phần tử có cùng chỉ số sẽ có tổng bằng 2010.

$ \rightarrow X = \left \{ a_1;a_2;...;a_{1004};b_1;b_2;...;b_{1004};1005 \right \}$

Gọi tập gồm 1006 số chọn ra là A.

Lại có : A gồm 1006 phần tử nên A sẽ có ít nhất 1005 phần tử mang chỉ số ( tức là có ít nhất 1005 phần tử khác 1005 ).

Mà chỉ có 1004 chỉ số ( từ 1 đến 1004 ) nên theo nguyên lí Dirichlet thì trong 1005 phần tử luôn tồn tại 2 phần tử có cùng chỉ số.

$\rightarrow$ A luôn tồn tại 2 số có tổng là 2010.

 

[huynhbachkhoa23]

Bài 1:

Theo nguyên lý Dirichlet thì tồn tại $a,b$ tự nhiên và $a \ne b$ sao cho $2013^a \equiv 2013^b \pmod{107}$
Giả sử $a>b$
Ta có $2013^a-2013^b\equiv 0 \pmod{107}$ hay $2013^{b}(2013^{a-b}-1) \equiv 0\pmod{107}$

Vì $(2013;107)=1$ nên $2013^{a-b}-1 \equiv 0 \pmod{107}$

Từ đây ta có điều phải chứng minh.