Chủ đề này có 1 trả lời

[reddevil1998]

Bài toán : Cho $p\geq 3$ là số nguyên tố và$a_{1},a_{2},...,a_{p-2}$ là dãy các số tự nhiên sao cho $p$ không chia hết $a_{k}$ và $a_{k}^{k}-1$ .CM ta có thể chọn ra một số số hạng của dãy số để tích của chúng có số dư là $2$ khi chia cho$p$.

[nguyenta98]

Bài toán : Cho $p\geq 3$ là số nguyên tố và$a_{1},a_{2},...,a_{p-2}$ là dãy các số tự nhiên sao cho $p$ không chia hết $a_{k}$ và $a_{k}^{k}-1$ .CM ta có thể chọn ra một số số hạng của dãy số để tích của chúng có số dư là $2$ khi chia cho$p$.

Giải như sau:
Mục đích chính là cm tồn tại một tập hợp gồm $p-1$ số hạng sao cho mỗi số hạng đồng dư với tích của một số số $a_i$ và mỗi số hạng của tập trên không đồng dư với nhau đôi một $mod(p)$
Gọi $A_k$ là tập chứa đúng $k$ phần tử sao cho mỗi phần tử đồng dư với tích một số số $a_i$ sao cho mỗi phần tử của $A_k$ không đồng dư với nhau đôi một $mod(p)$ giả sử tập $A_k$ là $(x_1,x_2,...,x_k)$ với $2\le k\le p-1$
Với $k=2$ thì hiển nhiên tồn tại $x_1 \equiv a_2 \pmod{p}$ và $x_2 \equiv a_1a_2 \pmod{p}$ khi ấy hiển nhiên nếu $x_1 \equiv x_2 \pmod{p}$ thì $x_2-x_1 \vdots p \Rightarrow a_2(a_1-1) \vdots p \Rightarrow a_1-1 \vdots p$ vô lí vì $a_1-1 \not \vdots p$ theo đề
Giả sư đúng đến $k$ hay tồn tại $A_k$ sao cho $(x_1,x_2,...,x_k)$ là các phần tử của $A_k$ mà $x_i \not \equiv x_j \pmod{p}$ và $x_i$ đồng dư với tích một số số $a_i$
Ta sẽ cm đúng đến $k+1$ hay tồn tại $A_{k+1}$ sao cho $x_1',x_2',...,x_{k+1}'$ thỏa mãn
Ta chọn $(x_1',x_2',...,x_{k+1}')=(x_1,x_2,...,x_k,a_k.x_i)$ với $1\le i\le k$
Hiển nhiên $(x_1',x_2',...,x_k')=(x_1,x_2,...,x_k)$ thỏa đề do $x_i \not \equiv x_j \pmod{p}$ nên $x_i' \not \equiv x_j' \pmod{p}$
Giờ ta xét $x_{k+1}'=a_k.x_i$ với $1\le i\le k$
Dễ thấy $(a_k.x_1)(a_k.x_2)...(a_k.x_k) \not \equiv (x_1.x_2...x_k) \pmod{p}$ vì ngược lại suy ra $a_k^k \equiv 1 \pmod{p}$ nên $a_k^k-1 \vdots p$ vô lí với đềbài
Nên tồn tại $a_k.x_i \not \equiv x_j \pmod{p}$ với $1\le i,j\le k$ vì giả sử ngược lại $a_k.a_i \equiv x_j \pmod{p}$ thì do $a_k.a_i \not \equiv a_k.a_t \pmod{p}$ vì ngược lại $x_i \equiv x_t \pmod{p}$ vô lí với điều kiện của tập $A_k$ với $1\le i,t\le k$ nên với mỗi $a_k.x_i$ tồn tại đúng một số $j$ sao cho $1\le j\le k$ sao cho $a_k.x_i \equiv x_j \pmod{p}$ khi ấy $(a_k.x_1).(a_k.x_2)...(a_k.x_k) \equiv (x_1.x_2...x_k) \pmod{p} \Rightarrow a_k^k \equiv 1 \pmod{p}$ suy ra $a_k^k-1 \vdots p$ vô lí
Tóm lại tồn tại $x_i$ sao cho $a_k.x_i \not \equiv x_j \pmod{p}$
Khi ấy tập $A_{k+1}=(x_1,x_2,...,x_k,(a_k.x_i))$ là tập thỏa đề
Quy nạp cho đến $A_{p-1}=(x_1,x_2,...,x_{p-1})$ với $x_i \not \equiv x_j \pmod{p}$ nên nó là hệ thu gọn $mod(p)$ nên mang đủ số dư từ $1,2,3,...,p-1$ hẳn phải tồn tại $x_t \equiv 2 \pmod{p}$ khi ấy tồn tại tích một số số của $a_1,a_2,...,a_{p-2}$ đồng dư $2$ mod $(p)$ nên đó là $đpcm$

Bài viết đã được chỉnh sửa nội dung bởi nguyenta98: 25-11-2012 - 19:22