Toán 9 Đồng dư

[Game là dễ]

[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.

CMR nếu [tex](a,b)=1[/tex] (với [tex]a[/tex], [tex]b[/tex] nguyên) thì tồn tại một số [tex]c[/tex] sao cho [tex]ac \equiv 1[/tex] (mod [tex]b[/tex])

 

[7 1 2 5]

Chọn b - 1 số [tex]c_i[/tex] sao cho [tex]c_i=i\forall 1\leq i\leq b-1[/tex] . Ta sẽ có b - 1 số dư khi chia [tex]ac_i[/tex] cho b.
Khi đó, nếu không tồn tại [TEX]c_i[/TEX] để [TEX]ac_i \equiv 1(mod b)[/TEX] thì b - 1 số [TEX]ac_i[/TEX] sẽ chia cho b dư từ 2 tới b - 1(loại 1 và b vì [TEX]c_i < b,(a,b)=1[/TEX])
Từ đó tồn tại 2 số khác nhau có cùng số dư hay [tex]ac_m-ac_n\vdots b\Rightarrow a(c_m-c_n)\vdots b(m > n)[/tex].
Mà [TEX](a,b)=1; [TEX]0 < c_m-c_n < b[/TEX][/TEX] nên vô lý. Vậy ta có đpcm.