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

[Math04]

Cho $n$ là số nguyên lớn hơn $1$, $k$ là số các ước nguyên tố phân biệt của $n$. Chứng minh rằng tồn tại số nguyên $a$, $1<a<\frac{n}{k}+1$ sao cho $n|(a^2-a)$.

[nhungvienkimcuong]

Cho $n$ là số nguyên lớn hơn $1$, $k$ là số các ước nguyên tố phân biệt của $n$. Chứng minh rằng tồn tại số nguyên $a$, $1<a<\frac{n}{k}+1$ sao cho $n|(a^2-a)$.

Bài này nhìn tưởng đơn giản nhưng để thỏa mãn điều kiện bất đẳng thức thì rắc rối ghê 

 

Đặt phân tích ra thừa số nguyên tố của $n$ là $p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k}$. Theo định lí thặng dư Trung Hoa, với mỗi $i\in \{1,2,\dots,k\}$ thì tồn tại số nguyên $x_i$ thỏa mãn

\[\left\{\begin{array}{l}x_i\equiv 1\pmod{p_i^{\alpha_i}}\\ x_i\equiv 0\pmod{\frac{n}{p_i^{\alpha_i}}}\end{array}\right..\]

Nhận xét (NX). Cho tổng $X=\sum_{i=1}^k\epsilon_ix_i$, trong đó $\epsilon_i\in \{0,1\}$ với mọi $i$.

1. $n\mid X^2-X$.
2. Nếu $X$ chia $n$ dư $0$ hoặc $1$ thì $\epsilon_1=\epsilon_2=\dots=\epsilon_k$.

NX1 là dễ thấy vì với mọi $i$ thì $X\equiv 0,1\pmod{p_i^{\alpha_i}}$.

 

Tiếp theo ta chứng minh NX2. Giả sử tồn tại $i\neq j$ sao cho $\epsilon_i\neq \epsilon_j$, giả sử luôn là $\epsilon_i=1$ và $\epsilon_j=0$.

• Trường hợp $X\equiv 0\pmod{n}$. Xét theo modulo $p_i^{\alpha_i}$ thì $X\equiv 1\pmod{p_i^{\alpha_i}}$ (mâu thuẫn).
• Trường hợp $X\equiv 1\pmod{n}$. Xét theo modulo $p_j^{\alpha_j}$ thì $X\equiv 0\pmod{p_j^{\alpha_j}}$ (mâu thuẫn).

 

Với mỗi $i\in \{1,2,\dots,k\}$, gọi $X_i$ là số tự nhiên nhỏ nhất thỏa mãn

\[X_i\equiv x_1+x_2+\dots+x_i\pmod{n}.\]

Theo NX2 thì $X_i\neq 0$ với mọi $i=\overline{1,k}$ và ngoài ra $X_k=1$. Bổ sung thêm $X_0=0$. Xét $k+1$ số $X_0,\ X_1,\ \dots,\ X_k$, theo định lí Dirichlet sẽ tồn tại $0\le c<d\le k$ sao cho

\[X_c,\ X_d\in\left [ \frac{jn}{k},\frac{(j+1)n}{k} \right ).\]

Nghĩa là $|X_d-X_c|<\frac{n}{k}$, theo NX2 ta có $X_d-X_c\notin \{0,1\}$. Cuối cùng ta chia ra hai trường hợp sau

$\bullet$ TH1: $X_d-X_c>1$ thì đặt

$$a_1=x_{c+1}+x_{c+2}+\dots+x_d=X_d-X_c\in\left(1,\frac{n}{k}\right).$$

Ngoài ra theo NX1 thì $n\mid a_1^2-a_1$ nên $a_1$ thỏa đề.

$\bullet$ TH2: $X_d-X_c<0$ thì đặt

$$a_2=(x_1+x_2+\dots+x_c)+(x_{d+1}+x_{d+2}+\dots+x_k)=X_k-(X_d-X_c)\in\left(1,1+\frac{n}{k}\right).$$

Ngoài ra theo NX1 thì $n\mid a_2^2-a_2$ nên $a_2$ thỏa đề.

Bài viết đã được chỉnh sửa nội dung bởi nhungvienkimcuong: 04-12-2022 - 21:44

[Math04]

Bài này nhìn tưởng đơn giản nhưng để thỏa mãn điều kiện bất đẳng thức thì rắc rối ghê 

 

Đặt phân tích ra thừa số nguyên tố của $n$ là $p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k}$. Theo định lí thặng dư Trung Hoa, với mỗi $i\in \{1,2,\dots,k\}$ thì tồn tại số nguyên $x_i$ thỏa mãn

\[\left\{\begin{array}{l}x_i\equiv 1\pmod{p_i^{\alpha_i}}\\ x_i\equiv 0\pmod{\frac{n}{p_i^{\alpha_i}}}\end{array}\right..\]

Nhận xét (NX). Cho tổng $X=\sum_{i=1}^k\epsilon_ix_i$, trong đó $\epsilon_i\in \{0,1\}$ với mọi $i$.

1. $n\mid X^2-X$.
2. Nếu $X$ chia $n$ dư $0$ hoặc $1$ thì $\epsilon_1=\epsilon_2=\dots=\epsilon_k$.

NX1 là dễ thấy vì với mọi $i$ thì $X\equiv 0,1\pmod{p_i^{\alpha_i}}$.

 

Tiếp theo ta chứng minh NX2. Giả sử tồn tại $i\neq j$ sao cho $\epsilon_i\neq \epsilon_j$, giả sử luôn là $\epsilon_i=1$ và $\epsilon_j=0$.

• Trường hợp $X\equiv 0\pmod{n}$. Xét theo modulo $p_i^{\alpha_i}$ thì $X\equiv 1\pmod{p_i^{\alpha_i}}$ (mâu thuẫn).
• Trường hợp $X\equiv 1\pmod{n}$. Xét theo modulo $p_j^{\alpha_j}$ thì $X\equiv 0\pmod{p_j^{\alpha_j}}$ (mâu thuẫn).

 

Với mỗi $i\in \{1,2,\dots,k\}$, gọi $X_i$ là số tự nhiên nhỏ nhất thỏa mãn

\[X_i\equiv x_1+x_2+\dots+x_i\pmod{n}.\]

Theo NX2 thì $X_i\neq 0$ với mọi $i=\overline{1,k}$ và ngoài ra $X_k=1$. Bổ sung thêm $X_0=0$. Xét $k+1$ số $X_0,\ X_1,\ \dots,\ X_k$, theo định lí Dirichlet sẽ tồn tại $0\le c<d\le k$ sao cho

\[X_c,\ X_d\in\left [ \frac{jn}{k},\frac{(j+1)n}{k} \right ).\]

Nghĩa là $|X_d-X_c|<\frac{n}{k}$, theo NX2 ta có $X_d-X_c\notin \{0,1\}$. Cuối cùng ta chia ra hai trường hợp sau

$\bullet$ TH1: $X_d-X_c>1$ thì đặt

$$a_1=x_{c+1}+x_{c+2}+\dots+x_d=X_d-X_c\in\left(1,\frac{n}{k}\right).$$

Ngoài ra theo NX1 thì $n\mid a_1^2-a_1$ nên $a_1$ thỏa đề.

$\bullet$ TH2: $X_d-X_c<0$ thì đặt

$$a_2=(x_1+x_2+\dots+x_c)+(x_{d+1}+x_{d+2}+\dots+x_k)=X_k-(X_d-X_c)\in\left(1,1+\frac{n}{k}\right).$$

Ngoài ra theo NX1 thì $n\mid a_2^2-a_2$ nên $a_2$ thỏa đề.

Bạn có thể chia sẻ quá trình nghĩ ra lời giải này không nhỉ? Cám ơn bạn nhé!

[nhungvienkimcuong]

Bạn có thể chia sẻ quá trình nghĩ ra lời giải này không nhỉ? Cám ơn bạn nhé!

Điều kiện chia hết đơn giản, điều kiện còn lại khá khó nên mình cần xem xét tất cả số $a$ thỏa mãn $n\mid a^2-a$. Có đúng $2^k$ số (xét theo modulo $n$) thỏa mãn $n\mid a^2-a$, chính là các số có dạng $\sum \epsilon_ix_i$ với $\epsilon_i\in \{0,1\}$.

 

Điều kiện còn lại thì mình nghĩ tới việc chỉ ra hai số cùng thuộc $\left[ \frac{jn}{k},\frac{(j+1)n}{k} \right )$ nên xét $k+1$ số $X_i$ như trên. Phần còn lại là làm sao cho hợp lí, dẫn đến việc cần chứng minh nhận xét.

[Math04]

Bài này nhìn tưởng đơn giản nhưng để thỏa mãn điều kiện bất đẳng thức thì rắc rối ghê 

 

Đặt phân tích ra thừa số nguyên tố của $n$ là $p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k}$. Theo định lí thặng dư Trung Hoa, với mỗi $i\in \{1,2,\dots,k\}$ thì tồn tại số nguyên $x_i$ thỏa mãn

\[\left\{\begin{array}{l}x_i\equiv 1\pmod{p_i^{\alpha_i}}\\ x_i\equiv 0\pmod{\frac{n}{p_i^{\alpha_i}}}\end{array}\right..\]

Nhận xét (NX). Cho tổng $X=\sum_{i=1}^k\epsilon_ix_i$, trong đó $\epsilon_i\in \{0,1\}$ với mọi $i$.

1. $n\mid X^2-X$.
2. Nếu $X$ chia $n$ dư $0$ hoặc $1$ thì $\epsilon_1=\epsilon_2=\dots=\epsilon_k$.

NX1 là dễ thấy vì với mọi $i$ thì $X\equiv 0,1\pmod{p_i^{\alpha_i}}$.

 

Tiếp theo ta chứng minh NX2. Giả sử tồn tại $i\neq j$ sao cho $\epsilon_i\neq \epsilon_j$, giả sử luôn là $\epsilon_i=1$ và $\epsilon_j=0$.

• Trường hợp $X\equiv 0\pmod{n}$. Xét theo modulo $p_i^{\alpha_i}$ thì $X\equiv 1\pmod{p_i^{\alpha_i}}$ (mâu thuẫn).
• Trường hợp $X\equiv 1\pmod{n}$. Xét theo modulo $p_j^{\alpha_j}$ thì $X\equiv 0\pmod{p_j^{\alpha_j}}$ (mâu thuẫn).

 

Với mỗi $i\in \{1,2,\dots,k\}$, gọi $X_i$ là số tự nhiên nhỏ nhất thỏa mãn

\[X_i\equiv x_1+x_2+\dots+x_i\pmod{n}.\]

Theo NX2 thì $X_i\neq 0$ với mọi $i=\overline{1,k}$ và ngoài ra $X_k=1$. Bổ sung thêm $X_0=0$. Xét $k+1$ số $X_0,\ X_1,\ \dots,\ X_k$, theo định lí Dirichlet sẽ tồn tại $0\le c<d\le k$ sao cho

\[X_c,\ X_d\in\left [ \frac{jn}{k},\frac{(j+1)n}{k} \right ).\]

Nghĩa là $|X_d-X_c|<\frac{n}{k}$, theo NX2 ta có $X_d-X_c\notin \{0,1\}$. Cuối cùng ta chia ra hai trường hợp sau

$\bullet$ TH1: $X_d-X_c>1$ thì đặt

$$a_1=x_{c+1}+x_{c+2}+\dots+x_d=X_d-X_c\in\left(1,\frac{n}{k}\right).$$

Ngoài ra theo NX1 thì $n\mid a_1^2-a_1$ nên $a_1$ thỏa đề.

$\bullet$ TH2: $X_d-X_c<0$ thì đặt

$$a_2=(x_1+x_2+\dots+x_c)+(x_{d+1}+x_{d+2}+\dots+x_k)=X_k-(X_d-X_c)\in\left(1,1+\frac{n}{k}\right).$$

Ngoài ra theo NX1 thì $n\mid a_2^2-a_2$ nên $a_2$ thỏa đề.

À bạn giải thích rõ chỗ "theo định lí Dirichlet sẽ tồn tại $0\le c<d\le k$ sao cho

\[X_c,\ X_d\in\left [ \frac{jn}{k},\frac{(j+1)n}{k} \right ).\]" giúp mình với. Bạn áp dụng nguyên lí định lí Dirichlet như thế nào nhỉ

Bài viết đã được chỉnh sửa nội dung bởi Math04: 31-12-2022 - 14:03