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

[Minhnguyenthe333]

 

Bài 48: Giải phương trình nghiệm nguyên $x^5+1=y^2$

Lời giải bài 48:

$PT<=>x^5=(y-1)(y+1)$

Xét $y=\pm 1=>x=0$

Đặt $d=(y-1,y+1)=>d\in \{1;2\}$

$TH1:d=1$

$=>y=2<=>x^5=3$ (vô lí)

$TH2:d=2$

$=>y=3<=>x^5=8$ (vô lí)

 

@Ego: Lời giải của bạn quá tắt, và có vấn đề.

Bài viết đã được chỉnh sửa nội dung bởi Ego: 07-06-2016 - 12:01

[IMOer]

Lời giải bài 48:

Bổ đề: Với ${{a}^{5}}+{{b}^{5}}={{c}^{2}}$ và $\gcd \left( a,b \right)=1$ thì $5|c$ hoặc $a+b$ là một số chính phương.

Chứng minh bổ đề: Ta có: ${{c}^{2}}=\left( a+b \right)\left( {{a}^{4}}-{{a}^{3}}b+{{a}^{2}}{{b}^{2}}-a{{b}^{3}}+{{b}^{4}} \right)$

Gọi $d=\gcd \left( a+b,{{a}^{4}}-{{a}^{3}}b+{{a}^{2}}{{b}^{2}}-a{{b}^{3}}+{{b}^{4}} \right)$ thì suy ra: $d|5{{a}^{4}}$ và $d|5{{b}^{4}}$.

Mà $\gcd \left( a,b \right)=1$ suy ra: $d|5$.

Nếu $d=1$ thì suy ra: $a+b$ là một số chính phương.

Nếu $d=5$ thì suy ra: $5|c$.

 

Quay lại bài toán, ta có:

Nhận thấy nếu $(x,y)$ là nghiệm thì $(x,-y)$ cũng là nghiệm nên ta sẽ chỉ xét $y\ge0$.

Với $y=0$ thì ta suy ra: $x=-1$

Với $y=1$ thì ta suy ra: $x=0$

Với $y\ge 2$ thì ta cũng suy ra: $x\ge 2$.

Ta có: ${{y}^{2}}={{x}^{5}}+1=\left( x+1 \right)\left( {{x}^{4}}-{{x}^{3}}+{{x}^{2}}-x+1 \right)$

Nếu $x+1$ là số chính phương thì ta suy ra: ${{x}^{4}}-{{x}^{3}}+{{x}^{2}}-x+1$ cũng là số chính phương.

Với $x\ge 2$ thì ${{\left( 2{{x}^{2}}-x \right)}^{2}}<4\left( {{x}^{4}}-{{x}^{3}}+{{x}^{2}}-x+1 \right)<{{\left( 2{{x}^{2}}-x+1 \right)}^{2}}$ nên trường hợp này vô nghiệm.

Nếu $x+1$ không là số chính phương thì theo bổ đề ta có: $5|y$.

Lại có: ${{x}^{5}}=\left( y-1 \right)\left( y+1 \right)$.

Nếu $2|y$ thì suy ra: $\left\{ \begin{array}{l}y-1={{a}^{5}} \\y+1={{b}^{5}}\end{array} \right.$ với $a,b\in \mathbb{N},\ \gcd \left( a,b \right)=1$.

Khi đó suy ra: ${{b}^{5}}-{{a}^{5}}=2$, dễ thấy vô nghiệm.

Nếu $2\nmid y$ thì ta có 2 trường hợp sau:

Trường hợp 1: $y+1=2{{a}^{5}};\ y-1=16{{b}^{5}}$ với $a,b\in \mathbb{N},\ \gcd \left( a,b \right)=1,\ a$ lẻ. Khi đó dễ dàng suy ra được: $a>b\Rightarrow a-1\ge b$.

Ta có: ${{a}^{10}}-{{\left( 2b \right)}^{5}}={{\left( \frac{y+1}{2} \right)}^{2}}-2\left( y-1 \right)={{\left( \frac{y-3}{2} \right)}^{2}}$

Vì $\frac{y-3}{2}\in \mathbb{N}$ và không chia hết cho 5 nên theo bổ đề ta có: ${{a}^{2}}-2b$ là số chính phương, vô lý vì: ${{a}^{2}}>{{a}^{2}}-2b\ge {{a}^{2}}-2\left( a-1 \right)>{{\left( a-1 \right)}^{2}}$.

Trường hợp 2: $y+1=16{{a}^{5}};\ y-1=2{{b}^{5}}$ với $a,b\in \mathbb{N},\ \gcd \left( a,b \right)=1,\ b$ lẻ. Giải quyết tương tự suy ra trường hợp này vô nghiệm.

 

Bằng một cách tương tự, ta cũng có thể giải quyết được bài toán sau:

"Phương trình $x^{2017}+1=y^2$ chỉ có các nghiệm nguyên $(x,y)=(-1;0)$ và $(x,y)=(0;\pm1)$.

 

Bài 49: (Nguồn: Sưu tầm)

Cho $S$ là tập khác rỗng các số nguyên tố thoả mãn với $n\ge 1$ và $p_1,p_2,...,p_n\in S$ thì mọi ước nguyên tố của $p_1p_2...p_n+1$ cũng thuộc $S$.

Chứng minh rằng mọi số nguyên tố đều thuộc $S$.

[Ego]

Bài 49: (Nguồn: Sưu tầm)

Cho $S$ là tập khác rỗng các số nguyên tố thoả mãn với $n\ge 1$ và $p_1,p_2,...,p_n\in S$ thì mọi ước nguyên tố của $p_1p_2...p_n+1$ cũng thuộc $S$.

Chứng minh rằng mọi số nguyên tố đều thuộc $S$.

Lời giải bài 49.

Bổ đề 1. Cho $i \in \{0, 1, 2, \cdots , p - 1\}$ với $p \in \mathbb{P}$. Ký hiệu $A_{p} \subset \{0, 1, 2, \cdots , p - 1\}$ là tập hợp chứa các phần tử đôi một không đồng dư nhau modulo $p$. Khi đó nếu $|A_{p}| \le \frac{p - 1}{2}$ thì tồn tại $a \in \mathbb{A_{p}}$ sao cho $a + 1\not\in A_{p}$.

Bổ đề 2. Có đúng $\frac{p - 1}{2}$ thặng dư chính phương modulo $p$ với $p$ nguyên tố.
Quy ước $A_{p}$ là số các lớp đồng dư modulo $p$ đôi một khác nhau.

i) Ta sẽ chứng minh $\mathbb{S}$ chứa vô hạn phần tử. Thật vậy, nếu chúng chỉ có hữu hạn thì ta suy ra tồn tại một số nguyên tố $p \mid P + 1$ với $P$ là tích tất cả các phần tử của $\mathbb{S}$, mặt khác, $p \in \mathbb{S}$ nên $p\mid 1$, vô lý.

ii) Giả sử phản chứng, giả sử $p$ là số nguyên tố không là phần tử của $\mathbb{S}$. Ta đã biết rằng theo định lý Dirichlete rằng tồn tại vô hạn số nguyên tố có dạng $mp + n$ với $n = 1, 2, \cdots p - 1$.
Do tập $\mathbb{L} = \{1, 2, \cdots , p - 1\}$ chỉ có hữu hạn nên tồn tại $x_{1}\in\mathbb{L}$ sao cho $q\in\mathbb{S} \equiv x_{1}\pmod{p}$ là vô hạn. Ta sẽ tìm thêm $x_{2}$ suy từ $x_{1}$ thỏa $x_{2}\neq x_{1}$ và $q \in\mathbb{S} \equiv x_{2}\pmod{p}$ cũng vô tận. Tương tự cho $x_{3}$ suy từ $x_{2}$, .... Ký hiệu $p_{x_{i}}$ là các số nguyên tố thuộc $\mathbb{S}$ đồng dư $x_{i}$ modulo $p$.

Ta sẽ thực hiện các thuật toán sau:

a) Giả sử trong tay ta đã có $p_{x_{1}}, p_{x_{2}}, \cdots p_{x_{i}}$. Khi đó tích của $m_{j}$ số nguyên tố dạng $x_{j}\pmod{p}$ là $x_{1}^{m_{1}}x_{2}^{m_{2}}\cdots x_{i}^{m_{i}}$. Đặt $A = \{x_{1}^{m_{1}}x_{2}^{m_{2}}\cdots x_{i}^{m_{i}}: \quad 0\le m_{j} \le p - 1\}$. Khi đó:

b) Nếu $i > \frac{p - 1}{2}$ thì có $x_{u}$ nào đó không là thặng dư chính phương modulo $p$. Gọi ra $\frac{p - 1}{2}$ số $p_{x_{u}}$ thì tích của chúng đồng dư $x_{u}^{\frac{p - 1}{2}} \equiv \frac{x_{u}}{p} \equiv -1\pmod{p}$. Từ đây cũng suy ra vô lý.
Nếu không, ta chuyển xuống bước c)

c) Nếu tồn tại phần tử nào đó của $A$ đồng dư $-1\pmod{p}$ thì bài toán kết thúc nhờ việc ta lấy $m_{j}$ số $p_{x_{j}}$. Nếu không, ta chuyển xuống bước d).

d) Nếu $|A_{p}| > \frac{p - 1}{2}$ thì theo bổ đề 2 tồn tại bộ $g_{1}, g_{2}, \cdots , g_{i}$ thỏa mãn $\prod_{j = 1}^{i}x_{i}^{g_{i}} \equiv a\pmod{p}$ với $a$ không thặng dư chính phương modulo $p$. Lúc này do tính vô hạn nên ta cứ việc lấy $\frac{p - 1}{2}g_{i}$ lần số nguyên tố dạng $p_{x_{i}}$ thì tích của chúng đồng dư $a^{\frac{p - 1}{2}} \equiv \left(\frac{a}{p}\right) \equiv -1\pmod{p}$. Từ đó có vô lý.
Nếu không, ta  chuyển xuống bước e)
e) Nếu $|A_{p}|\le \frac{p - 1}{2}$, theo bổ đề thì tồn tại $n_{1}, n_{2}, \cdots n_{i}$ thỏa mãn $x_{1}^{n_{1}}x_{2}^{n_{2}}\cdots x_{i}^{n_{i}} + 1\not\equiv x_{1}^{m_{1}}.x_{2}^{m_{2}}\cdots x_{i}^{m_{i}}\pmod{p}$ với mọi $m_{j}$ bất kỳ. Tức là trong phân tích $x_{1}^{n_{1}}\cdots x_{i}^{n_{i}} + 1$ không thể mãi chứa $x_{1}, x_{2}, \cdots x_{i}$ được. Nhờ việc có vô hạn số $p_{x_{i}}$ nên ta cũng suy ra tồn tại vô hạn ta cũng suy ra có phần tử nào $x_{i + 1}$ nào đó cũng thỏa $p_{x_{i + 1}}$. Bây giờ quay lại bước b).
Lưu ý là bước b) vừa là bước tối ưu (tức là không có cũng OK), vừa là bước chặn, do số lượng $p_{x_{i}}$ ngày càng tăng, mà $i$ chỉ có thể không quá $\frac{p - 1}{2}$ thì ta mới có thể thực hiện tiếp thuật toán. Vì vậy nên bài toán sẽ đến lúc nào đó sẽ dừng.
 

Bài viết đã được chỉnh sửa nội dung bởi Ego: 10-06-2016 - 10:54

[H S G S]

Lời giải bài 49.

Bổ đề 1. Cho $i \in \{0, 1, 2, \cdots , p - 1\}$ với $p \in \mathbb{P}$. Ký hiệu $A_{p} \subset \{0, 1, 2, \cdots , p - 1\}$ là tập hợp chứa các phần tử đôi một không đồng dư nhau modulo $p$. Khi đó nếu $|A_{p}| \le \frac{p - 1}{2}$ thì tồn tại $a \in \mathbb{A_{p}}$ sao cho $a + 1\not\in A_{p}$

Bổ đề 2. Có đúng $\frac{p - 1}{2}$ thặng dư chính phương modulo $p$ với $p$ nguyên tố.
i) Dễ thấy rằng $2 \in \mathbb{S}$

ii) Ta sẽ chứng minh $\mathbb{S}$ chứa vô hạn phần tử. Thật vậy, nếu chúng chỉ có hữu hạn thì ta suy ra tồn tại một số nguyên tố $p \mid P + 1$ với $P$ là tích tất cả các phần tử của $\mathbb{S}$, mặt khác, $p \in \mathbb{S}$ nên $p\mid 1$, vô lý.

iii) Giả sử phản chứng, tồn tại $k$ để $p$ là số nguyên tố đầu tiên (thứ $k$) không là phần tử của $\mathbb{S}$. Ta đã biết rằng theo định lý Dirichlete rằng tồn tại vô hạn số nguyên tố có dạng $mp + n$ với $n = 1, 2, \cdots p - 1$.
Từ ii) ta suy ra rằng tồn tại $i \in \{1, 2, \cdots , p - 1\}$ sao cho các số nguyên tố dạng $mp + i$ mà là phần tử của $\mathbb{S}$ là vô hạn. Để thuận tiện, ta sẽ ghi $p_{i}$ tương ứng với $p_{i} \in \mathbb{S}$ và $p_{i} \equiv i\pmod{p}$ (mình có sử dụng $p_{i}^{k}$, ở đây không có nghĩa là chúng bằng nhau, chỉ có nghĩa là $k$ số nguyên tố đồng dư nhau ($\equiv k$) theo modulo $p$ thôi)
Nếu $i = 1$ thì cứ mỗi $p_{i}$ như vậy ta sẽ suy ra ước nguyên tố của $p_{i} + 1 \equiv 2\pmod{p}$ là thuộc $\mathbb{S}$, mà $p_{i} + 1$ đều không thể chứa tất cả các số dạng $1\pmod{p}$. Tức là lúc này có một $j$ nào đó sao cho $p_{j}$ ($j \neq 1$) là vô hạn. Ở đây ta xét các trường hợp xấu nhất (mình gọi là xấu nhất thì các bạn đọc ở dưới sẽ hiểu tại sao), tức là $j$ thỏa $\left(\frac{j}{p}\right) = 1$. Lúc này ta gọi các số dạng $p_{j}$ ra và nhân chúng lại, nôm na mình sẽ đặt $P_{j} = \prod{p_{j}} = j^{x}$, ở đây ta cũng xét trường hợp tệ nhất tức là với $x$ chạy từ $0$ đến $p$ thì $j^{x}$ chỉ nhận không quá $\frac{p - 1}{2}$ giá trị modulo $p$. Áp dụng bổ đề 1 ta có sẽ tồn tại một số $x$ nào đó $P_{j} \not\equiv j^{x} + 1\pmod{p}$. Tức là ta cứ đem xét các ước của $p_{j}^{(p - 1)k + x} + 1$ thì hẳn các ước của chúng sẽ không thể mãi dạng $p_{j}$ được, điều này chứng minh còn $k \neq j, i$ thỏa $p_{k}$ tồn tại vô hạn. Xét TH xấu luôn là $\left(\frac{k}{p}\right) = 1$
Tương tự, ta xét $P_{jk} = \prod{p_{j}.p_{k}} \equiv j^{x}k^{y}$ và cũng tính đến trường hợp tệ nhất, tức là $x, y$ chạy từ $0$ đến $p$ mà tập các lớp đồng dư của $j^{x}.k^{y}$ cũng không quá $\frac{p - 1}{2}$ thì theo bổ đề 1 ta cũng thu được tồn tại $x, y$ thỏa $P_{jk} \neq j^{x}k^{y} + 1\pmod{p}$. Từ giờ ta cũng đem đi xét các ước của $p_{j}^{(p - 1)u + x}.p_{k}^{(p - 1)v + y} + 1$ thì cũng chẳng thể toàn ước là $p_{j}, p_{k}$ mãi được,....
Lặp lại quá trình trên đến một trong hai TH sau sẽ dừng:
a) Có nhiều hơn $\frac{p - 1}{2}$ số $i$ trong tập $\{1, 2, \cdots , p - 1\}$ thỏa $p_{i}$ là vô tận. Lúc này để ý theo bổ đề 2 sẽ có $i$ sao cho $\left(\frac{i}{p}\right) = -1$ và $p_{i}$ là vô tận. Xét $\frac{p - 1}{2}$ số $p_{i}$ như vậy, đặt là $q_{1}, q_{2}, \cdots q_{\frac{p - 1}{2}}$. Khi đó $\prod_{i = 1}^{\frac{p - 1}{2}}q_{i} \equiv i^{\frac{p - 1}{2}} \equiv -1\pmod{p}$ theo tiêu chuẩn Euler. Hay $\prod_{i = 1}^{\frac{p - 1}{2}}q_{i} + 1 \vdots p$. Chứng tỏ $p \in \mathbb{S}$. Vô lý.

b) Sẽ đến lúc nào đó mà với tập $j_{1}, j_{2}, \cdots j_{u}$ thỏa $p_{j_{m}}$ là vô tận sao cho tích chúng tạo thành nhiều hơn $\frac{p - 1}{2}$ lớp đồng dư modulo $p$. Cũng áp dụng bổ đề 2 sẽ tồn tại $a$ sao cho $\left(\frac{a}{p}\right) = -1$ và $P(j_{1}j_{2}\cdots j_{u}) \equiv a\pmod{p} \implies (P(j_{1}j_{2}\cdots j_{u}))^{\frac{p - 1}{2}} \equiv a^{\frac{p - 1}{2}} \equiv \left(\frac{a}{p}\right) = -1$. Điều này cũng chứng tỏ $p \in \mathbb{S}$. Vô lý.
Nếu $i \neq 1$ cũng không quan trọng gì, lẫn $p_{1}$ cũng chẳng quan trọng vì $1$ nhân số nào chả là nó . Vì mình chỉ đang giải quyết các trường hợp xấu nhất có thể xảy ra
Các bạn check hộ mình . Bài hay quá, mình sẽ cố gắng đơn giản hóa lời giải của mình lại (nếu không có chỗ sai)

 

Hì hì, ở đây có thể dùng Cyclotomic Polynomial để chứng minh sơ cấp Dirichlet, nhưng mình nghĩ dùng 1 định lý thậm chí còn mạnh hơn cả bài này để giải nó thì hơi quá.

Nhân tiện bạn có thể nói sơ qua ý tưởng được không

[canhhoang30011999]

Hì hì, ở đây có thể dùng Cyclotomic Polynomial để chứng minh sơ cấp Dirichlet, nhưng mình nghĩ dùng 1 định lý thậm chí còn mạnh hơn cả bài này để giải nó thì hơi quá.

Nhân tiện bạn có thể nói sơ qua ý tưởng được không

Thực ra nguyên lí Đi-rich-lê chứng minh rất phức tạp nhưng theo mình biết thì khi thi cử không cần cm nên thấy cũng nhiều bài toán phải sử dụng luôn chứ cũng khồng có gì quá cả

p/s bài 50 Ego ơi

Bài viết đã được chỉnh sửa nội dung bởi canhhoang30011999: 08-06-2016 - 07:56

[Ego]

Mình thì nghĩ nguyên lý Dirichlete ở Olympiad có thể được thừa nhận. Đương nhiên đa thức Cyclotomic là một công cụ mạnh rồi .
Ý tưởng của mình cho bài toán trên bắt đầu từ ý tưởng phản chứng, vì mình chẳng thể quy nạp, hay làm bất cứ gì như bình thường. Mình phản chứng dựa trên $p$. Mình còn phát hiện ra là nếu như trong tay có một số nguyên tố $\equiv p - 1\pmod{p}$ thì bài toán sẽ vô lý hẳn. Vì vậy mình cố gắng tìm ra các lực lượng khác để truy ra số nguyên tố đó. Bài này cũng gợi gợi chút gì đó trong chứng minh vô hạn số nguyên tố của Euler nên cũng chứng minh được tập $S$ vô hạn. Phần còn lại là cố gắng tìm ra số nguyên tố dạng $kp + a$ với $a$ không thặng dư chính phương modulo $p$ (tự nhiên xuất thần nghĩ ra cái này). Chỉ cần $\frac{p - 1}{2}$ số nguyên tố như vậy ta đã truy ra số nguyên tố mình cần.
Bài 50. (AMM) Chứng minh rằng nếu ta chọn $n$ số tự nhiên từ $2n$ số nguyên dương đầu tiên thì ta luôn tìm được số square - free.
Nói thêm về số square-free, ta gọi $n$ là số square-free nếu và chỉ nếu với $p\in\mathbb{P}$ sao cho $p\mid n$ thì $v_{p}(n) = 1$.

Remark

Tìm thấy bài này trong mục Junior nhưng thấy cũng hay

[IMOer]

Thực ra nguyên lí Đi-rich-lê chứng minh rất phức tạp nhưng theo mình biết thì khi thi cử không cần cm nên thấy cũng nhiều bài toán phải sử dụng luôn chứ cũng khồng có gì quá cả

p/s bài 50 Ego ơi

 

Định lý Dirichlet sẽ chỉ được sử dụng không chứng minh khi dự thi IMO. Còn các kỳ thi khác thì đều không được sử dụng khi không chứng minh lại.

[JUV]

Định lý Dirichlet sẽ chỉ được sử dụng không chứng minh khi dự thi IMO. Còn các kỳ thi khác thì đều không được sử dụng khi không chứng minh lại.

Hình như mấy kì thi khác mình đọc thì định lí Dirichlet được thay tên bằng định lí Pigeonhole nội dung tương tự được sử dụng không chứng minh 

[IMOer]

Hình như mấy kì thi khác mình đọc thì định lí Dirichlet được thay tên bằng định lí Pigeonhole nội dung tương tự được sử dụng không chứng minh 

"Định lý Pigeonhole" mà bạn nói được gọi là "Nguyên lý Dirichlet" chứ không phải "Định lý Dirichlet về sự tồn tại số nguyên tố" bạn nhé!

"Nguyên lý Dirichlet" thì luôn được dùng rồi.

[IMOer]

Bài 50. (AMM) Chứng minh rằng nếu ta chọn $n$ số tự nhiên từ $2n$ số nguyên dương đầu tiên thì ta luôn tìm được số square - free.
Nói thêm về số square-free, ta gọi $n$ là số square-free nếu và chỉ nếu với $p\in\mathbb{P}$ sao cho $p\mid n$ thì $v_{p}(n) = 1$.

Remark

Tìm thấy bài này trong mục Junior nhưng thấy cũng hay

Một hướng đi hơi giải tích cho bài này:

Kết quả quen thuộc: $\displaystyle \sum_{n=1}^{\infty} \dfrac{1}{n^2}=\dfrac{\pi^2}{6}$

Với mỗi số nguyên tố $p$ thì có $\left\lfloor\dfrac{2n}{p^2}\right\rfloor$ số không là số square-free và $\le 2n$.

Vậy số các số không phải square-free và $\le 2n$ sẽ không vượt quá:

$\displaystyle S=\sum_{p\textrm{ prime}} \left\lfloor \dfrac{2n}{p^2}\right\rfloor\le 2n\sum_{p \textrm{ prime}}\dfrac{1}{p^2}$

Lại có: $\displaystyle \sum_{p \textrm{ prime}}\dfrac{1}{p^2}<\sum_{k=1}^{\infty}\dfrac{1}{k^2}-1-\dfrac{1}{4^2}-\dfrac{1}{6^2}-\dfrac{1}{8^2}-\dfrac{1}{9^2}-\dfrac{1}{10^2}-\dfrac{1}{12^2}-\dfrac{1}{14^2}-\dfrac{1}{15^2}-\dfrac{1}{16^2}=\dfrac{\pi^2}{6}-\dfrac{29177437}{25401600}<\dfrac{1}{2}$

Nên có ít hơn $n$ số không phải số square-free trong $2n$ số nguyên dương đầu tiên.

Từ đó suy ra, nếu lấy $n$ số bất kỳ từ $2n$ số nguyên dương đầu tiên thì luôn tồn tại ít nhất 1 số square-free.

[canhhoang30011999]

Đây là ý kiến của mình từ lâu rồi không phải nói bài này đâu nhé. Do topic có mục đích giao lưu học hỏi là chính nên ở 1 số bài toán nếu người đề xuất có khác với các cách được đưa ra thì cũng nên post lời giải của mình lên.

p/s bài 36 anh imoer có thể post đáp án được không ạ

[IMOer]

Đây là ý kiến của mình từ lâu rồi không phải nói bài này đâu nhé. Do topic có mục đích giao lưu học hỏi là chính nên ở 1 số bài toán nếu người đề xuất có khác với các cách được đưa ra thì cũng nên post lời giải của mình lên.

p/s bài 36 anh imoer có thể post đáp án được không ạ

Cảm ơn Hoàng đã nhắc.

Đây là lời giải của mình cho bài 36:

 

Gọi số cần tìm là ${{n}^{2}}$.

Theo bài ra ta có: ${{n}^{2}}=\underbrace{{{111...1}_{\left( 3 \right)}}}_{m}=\frac{{{3}^{m}}-1}{2}$ hay ${{3}^{m}}-1=2{{n}^{2}}$.

Trường hợp 1: $m=2k;\ k\ge 1$, khi đó ta có: ${{\left( {{3}^{k}} \right)}^{2}}-2{{n}^{2}}=1$.

Xét phương trình Pell: ${{x}^{2}}-2{{y}^{2}}=1$.

Phương trình này có tất cả các nghiệm không âm là: $\left\{ \begin{array}{l} {{x}_{0}}=1;\ {{x}_{1}}=3 \\ {{y}_{0}}=0;\ {{y}_{1}}=2 \\ {{x}_{n+1}}=6{{x}_{n}}-{{x}_{n-1}} \\ {{y}_{n+1}}=6{{y}_{n}}-{{y}_{n-1}} \\ \end{array} \right.$

Nhận thấy: ${{x}_{n}}>3$ với mọi $n>2$ và $\left\{ \begin{array}{l} {{x}_{n}}\equiv 0\ \left( \bmod \ 9 \right)\Leftrightarrow n\equiv 3\ \left( \bmod \ 6 \right) \\ {{x}_{n}}\equiv 0\ \left( \bmod \ 11 \right)\Leftrightarrow n\equiv 3\ \left( \bmod \ 6 \right) \\ \end{array} \right.$

Nên với $n>2$ thì ${{x}_{n}}$ không thể có dạng ${{3}^{k}}$.

Từ đó suy ra phương trình ${{\left( {{3}^{k}} \right)}^{2}}-2{{n}^{2}}=1$ có nghiệm $n$ nguyên dương duy nhất là $\left( k,\ n \right)=\left( 1,\ 2 \right)$.

Trường hợp 2: $m=2k+1;\ k\ge 0$ khi đó ta có: $3{{\left( {{3}^{k}} \right)}^{2}}-2{{n}^{2}}=1$.

Xét phương trình Pell: $3{{x}^{2}}-2{{y}^{2}}=1$.

Phương trình này có tất cả các nghiệm không âm là: $\left\{ \begin{array}{l} {{x}_{0}}=1;\ {{x}_{1}}=9 \\ {{y}_{0}}=1;\ {{y}_{1}}=11 \\ {{x}_{n+1}}=10{{x}_{n}}-{{x}_{n-1}} \\ {{y}_{n+1}}=10{{y}_{n}}-{{y}_{n-1}} \\ \end{array} \right.$

Nhận thấy: ${{x}_{n}}>9$ với mọi $n>2$ và $\left\{ \begin{array}{l} {{x}_{n}}\equiv 0\ \left( \bmod \ 27 \right)\Leftrightarrow n\equiv 4\ \left( \bmod \ 9 \right) \\ {{x}_{n}}\equiv 0\ \left( \bmod \ 17 \right)\Leftrightarrow n\equiv 4\ \left( \bmod \ 9 \right) \\ \end{array} \right.$

Nên với $n>2$ thì ${{x}_{n}}$ không thể có dạng ${{3}^{k}}$.

Từ đó suy ra phương trình $3{{\left( {{3}^{k}} \right)}^{2}}-2{{n}^{2}}=1$ có các nghiệm nguyên không âm là $\left( k,\ n \right)=\left( 0,\ 1 \right)$ và $\left( k,\ n \right)=\left( 2,\ 11 \right)$.

Vậy các số chính phương cần tìm là: $1, 4, 121$.

[bangbang1412]

À anh IMOer có thể post bài tiếp theo không ạ . Còn ego chỉnh lại giải bây giờ mới đc đọc mà hơi rối . Tớ sẽ xóa post này tối nay .

[IMOer]

Mình xin đề xuất bài tiếp theo.

Bài 51: (Nguồn: AMM)

Tìm tất cả các số nguyên dương $n$ sao cho $\binom{n}{k}$ là ước của$\binom{2n}{2k}$ với mọi số nguyên dương $k$ không vượt quá $n$.

[Zaraki]

Bài 51: (Nguồn: AMM)

Tìm tất cả các số nguyên dương $n$ sao cho $\binom{n}{k}$ là ước của$\binom{2n}{2k}$ với mọi số nguyên dương $k$ không vượt quá $n$.

Lời giải. Ta xét một bài toán phụ sau:

 

Bài toán phụ. Tìm tất cả số nguyên dương $n$ sao cho không tồn tại số nguyên tố $2<p<n$ thoả mãn $n=ph+r$ với $h \ge 2, 1 \le  r \le \frac{p-1}{2}$.

Lời giải. Xét số $n-1$, để thoả mãn điều kiện thì hoặc $n-1$ là số nguyên tố hoặc $n-1=2^x$.

 

TH1. Nếu $n-1$ là số nguyên tố, tức $n$ chẵn. Xét $n-2$ thì ta suy ra để thoả mãn điều kiện thì $n-2=2^y \cdot 3^z$ với $y,z \ge 0$ là các số nguyên dương. Ta xét tiếp $n-3$ thì ta thấy hoặc $n-3$ là số nguyên tố hoặc $n-3=3^u \cdot 5^v$ với $u,v \ge 0$.

 

Với $n-3=3^u \cdot 5^v$ thì ta suy ra $2^y3^z-1=3^u5^v$. Như vậy hoặc $z=0$ hoặc $u=0$ hoặc cả hai bằng $0$.

 

+) Nếu $u=0$ thì $2^y3^z-1=5^v$ mà $5^v+1 \equiv 2 \pmod{4}$ nên $y=1$ dẫn đến $2 \cdot 3^z-1=5^v$ suy ra $v \equiv 1 \pmod{2}$ nếu $z \ge 1$, (còn nếu $z=0$ thì $v=0$, khi đó $n=4$). Do đó $\nu_3(5^v+1)=1+\nu_3(v)=z$ suy ra $v=3^{z-1} \cdot l$. Với $z \ge 2$ thì ta có $5^z+1=5^{3^{z-1} \cdot l}+1>2 \cdot 3^z$, mâu thuẫn. Vậy $z=1$ suy ra $v=1$. Khi đó $n=8$. 

 

+) Nếu $z=0, u \ne 0$ thì $2^y-1=3^u5^v$. Nếu $v=0$ thì $2^y-1=3^u$, ta dễ tìm được $y=2,u=1$. Khi đó $n=6$. Nếu $v \ge 1$ thì $4 \mid y$ và $\nu_3(2^y-1)=1+\nu_3(y)=u, \; \nu_5(2^y-1)=\nu_5(y)+1=v$. Suy ra $y=3^{u-1} 5^{v-1} l$. Ta thấy rằng $2^y-1>3^u5^v$ với mọi $u,v \ge 1$ nên suy ra không tồn tại $n$.

 

Với $n-3$ là số nguyên tố. Xét $n-4$ thì để thoả mãn điều kiện bài toán, ta phải có $2^y3^z-2=n-4=2^m3^h5^p7^q$. Nếu $n-3,n-1 \ne 3$ là hai số nguyên tố thì $3 \mid n-5$. Do đó để thoả mãn điều kiện bài toán, ta phải có $2^y3^z-3=3^u5^v7^t$ với $z \ge 1$. Khi đó buộc $h=0$.

 

+) Nếu $y=1$ tức $3^z-1=2^{m-1}5^p7^q$ thì nhận thấy nếu $q \ge 1$ thì $6 \mid z$ suy ra $13 \mid 3^6-1 \mid 3^z-1$, mâu thuẫn. Vậy $q=0$ suy ra $3^z-1=2^{m-1}5^p$. Nhận thấy với $8 \mid z$ thì $41 \mid 3^8-1 \mid 3^z-1$, mâu thuẫn. Vậy $\nu_2(z) \le 2$. Dễ tìm được với $p=0$ thì $z=2,m=4$. Khi đó $n=20$. Với $p \ge 1$ thì ta suy ra $4 \| z$ hay $m=5$ và $\nu_5(3^z-1)=\nu_5(z)+1=p$ dẫn đến $z=5^{p-1} \cdot 4i$ suy ra $3^z-1>16\cdot 5^p$ với $p>1$. Với $p=1$ thì $3^z=81$ suy ra $z=4$. Ta tìm được $n=164$. Tuy nhiên $7 \mid n-3=164-3$ nên ta suy ra mâu thuẫn. 

 

+) Nếu $y \ge 2$ thì $m=1$ ta có $2^{y-1}3^z-1=5^p7^q$ và ta cũng có $2^y3^{z-1}-1=3^{u-1}5^v7^t$. Ta suy ra $pv=0$ và $qt=0$. Với $q=0$ ta quay lại phương trình cũ $2^{y-1}3^z-1=5^p$ đã giải ở trên. Ta có $y=2,z=1$ hoặc $y=2,z=0$. Ta tìm được $n=14$ hoặc $n=5$. Với $q \ge 1$ thì nếu $p \ge 1$ thì $v=t=0$ suy ra $2^y3^{z-1}-1=3^{u-1}$ suy ra $z=1,y=2$ hay $n=14$.

 

TH2. Nếu $n-1=2^x$ thì ta suy ra $2^x-2=n-3=2^y3^z5^t$.

 

Nếu $x=1$ thì $n=3$. Nếu $x \ge 2$ thì $y=1$ suy ra $2^{x-1}-1=3^z5^y$. Nếu $z=0$ thì $2^{x-1}=5^y+1 \equiv 2 \pmod{4}$ suy ra $x=2$ dẫn đến $n=5$. Nếu $y=0$ thì $2^{x-1}-1=3^y$ suy ra $x=3$ dẫn đến $n=9$. Nếu $z,y \ge 1$ thì $4 \mid x-1$ và $\nu_3(x-1)=z-1, \nu_5(x-1)=y-1$ nên $x-1=3^{z-1}5^{y-1} \cdot 4i$. Nếu $z \ge 2$ thì $3 \mid x-1$ suy ra $7 \mid 2^{x-1}-1$, mâu thuẫn. Vậy $z=1$. Nếu $y \ge 2$ thì $5 \mid x-1$ suy ra $31=2^5-1 \mid 2^{x-1}-1$, mâu thuẫn. Vậy $y=z=1$ suy ra $x=5$. Ta tìm được $n=33$.

 

Các số $n$ tìm được là $n \in \{ 3,4,5,6,8,9,14,20,33 \}$.    $\square$

_________________________________________________________________________

 

Quay lại bài toán, ta có 

$$\begin{aligned} \binom{2n}{2k} & = \frac{2^{n}n!(3 \cdot 5 \cdots (2n-1))}{ \left [ 2^k k! (3 \cdot 5 \cdots (2k-1)) \right ] \cdot \left [ 2^{n-k}(n-k)! (3 \cdot 5 \cdots (2n-2k-1)) \right ] }, \\ & = \binom nk \cdot \frac{3 \cdot 5 \cdots (2n-1)}{(3 \cdot 5 \cdot (2k-1)) \cdot (3 \cdot 5 \cdots (2n-2k-1)) } = \binom nk \cdot \frac{A}{B}. \end{aligned}$$

Ta xét các số $n \not\in \{ 3,4,5,8,9,14,20,33 \}$. Khi đó luôn tồn tại số nguyên tố $p<n$ sao cho $n=hp+r$ với $1 \le r \le \frac{p-1}{2}$ và $h \ge 2$. Ta suy ra $2hp+2 \le 2n=2hp+2r<2hp+p+1$. Ta chọn $2k-1=(2h-1)p$ thì khi đó $2n-2k-1=2n-2-(2h-1)p \ge p$. Do đó $$\nu_p(B)= \nu_p(3 \cdot 5 \cdots (2h-1)p)+\nu_p(3 \cdot 5 \cdots (2n-2-(2h-1)p)) \ge \nu_p(3 \cdot 5 \cdots (2h-1)p)+1.$$

Mặt khác, do $1 \le r \le \frac{p-1}{2}$ nên các số lẻ từ $(2h-1)p+2$ đến $2n-1<(2h-1)p+2p$ sẽ không có số nào chia hết cho $p$. Ta suy ra $\nu_p(A)= \nu_p(3 \cdot 5 \cdots (2h-1)p)< \nu_p(B)$. Vậy lúc đó $\binom nk \nmid \binom{2n}{2k}$.

 

Xét các số $n \in \{ 3,4,5,8,9,14,20,33 \}$. Với $n=3,5$ thì thoả mãn điều kiện đề bài. 

Với $n=4$ thì chọn $2k-1=3$ ta thấy $\nu_3(B)>\nu_3(A)$, mâu thuẫn.

Với $n=6$ thì chọn $2k-1=5$ ta thấy $\nu_5(B)>\nu_5(A)$, mâu thuẫn.

Với $n=8,9$ thì chọn $2k-1=7$ ta thấy $\nu_7(B)>\nu_7(A)$, mâu thuẫn.

Với $n=14$ chọn $2k-1=13$ ta thấy $\nu_{13}(B)>\nu_{13}(A)$, mâu thuẫn.

Với $n=20$ chọn $2k-1=17$ ta thấy $\nu_{17}(B)>\nu_{17}(A)$, mâu thuẫn.

Với $n=33$ chọn $2k-1=23$ ta thấy $\nu_{23}(B)>\nu_{23}(A)$, mâu thuẫn.

 

Hiển nhiên $n=1,2$ cũng thoả mãn.

Vậy $n \in \{ 1,2,3,5 \}$ là đáp án bài toán.    $\blacksquare$

 

Bài 52. [AoPS] Cho số $n \in \mathbb{N}, n \ge 4$. $M$ là một tập con của $\{ 1,2 \cdots , 2n-1 \}$ có $n$ phần tử. Chứng minh rằng, tồn tại một tập con khác rỗng của $M$ sao cho tổng các phần tử trong tập đó chia hết cho $2n$.

Bài viết đã được chỉnh sửa nội dung bởi Zaraki: 10-06-2016 - 11:00

[H S G S]

Lời giải bài 52:

 

Lemma $(1)$: Với $p>2$ nguyên tố và $A={a_{1},a_{2}, \cdots, a_{s}}$ $1<s<p$ là tập số nguyên dương không chia hết cho p và thoả mãn $a_{1} \not\equiv a_{2} (mod p)$ thì tập $\sum_{i=1}^{s} x_{i}a_{i}$ với $x_{i}=0$ hoặc $x_{i}=1$ chứa ít nhất $s+1$ lớp đồng dư phân biệt $mod p$.

 

Chứng minh:

Với $s=2$, đúng.

Giả sử $(1)$ đúng với $s-1$, gọi dãy $b_{i}$ là tất các lớp đồng dư $mod p$ của $\sum_{i=1}^{s-1}x_{i}a_{i}$. Nếu $k>s$ thì hiển nhiên $(1)$ đúng với $s$, nên chỉ xét $k=s$. Do $a_{s} \not\equiv 0 (modp)$ suy ra tồn tại $k$ để $b_{k}+a_{s} \not\equiv b_{i}$ với mọi $i$. Nên phải có $s+1$ lớp đồng dư. 

 

Quay lại bài toán, với $n=p$, gọi dãy đã cho là $a_{i}$ và $-1<a_{1} \leq a_{2} \leq \cdots \leq a_{2p-1} <p$ 

Nếu $a_{i} \equiv a_{i+p-1}$ thì hiển nhiên nên xét $a_{i} \not\equiv a_{i+p-1}$. Đặt $b_{i} = a_{p+i} - a_{i+1}, 1 \leq i \leq p-1$ thì phương trình $\sum_{i=1}^{p}a_{i} \equiv - \sum_{i=1}^{p-1}x_{i}b_{i} (mod p)$ với $x_{i}=0$ hoặc $x_{i}=1$ có nghiệm theo $(1)$ suy ra $\sum_{i=1}^{p}a_{i} + \sum_{i=1}^{p-1}x_{i}b_{i} \equiv 0 (mod p)$ hay đúng với $n=p$.

 

Giờ cần chứng minh nếu đúng với $n=n_{1}$ và $n=n_{2}$ thì đúng với $n=n_{1}n_{2}$

Vì giả thiết đúng với $n_{1}$ nên chọn được $2n_{2}-1$ bộ gồm $n_{1}$ số có tổng chia hết cho $n_{1}$, giả thiết đúng với $n_{2}$ nên từ $2n_{2}-1$ bộ chọn được $n_{2}$ bộ có tổng chia hết cho $n_{2}$ hay $n_{1}n_{2}$ số có tổng chia hết cho $n_{1}n_{2}$

 

Bài 53: Giải phương trình nghiệm nguyên $x^{p}+1=y^{2}$ $(p>5)$

P/S: IMOer có thể đăng lời giải bài 49 được không

Bài viết đã được chỉnh sửa nội dung bởi H S G S: 10-06-2016 - 10:01

[IMOer]

Lời giải khác bài 52:

Trường hợp 1: Nếu $n\notin M$, ta chia $2n-2$ số còn lại thành $n-1$ cặp: $(1,2n-1), (2,2n-2),...,(n-1,n+1)$.

Theo nguyên lý Dirichlet thì tồn tại ít nhất 1 cặp mà cả 2 số đều là phần tử của $M$, và tổng 2 phần tử này chia hết cho $2n$.

Trường hợp 2: Nếu $n\in M$, gọi $n-1$ phần tử còn lại của $M$ là $x_1, x_2,...,x_{n-1}$. Ta sẽ chứng minh tồn tại tập con khác rỗng $S$ của $M\backslash \{n\}$ có tổng các phần tử chia hết cho $n$          $(*)$.

Nếu tổng các phần tử của $S$ chia hết cho $2n$ thì $S$ là tập cần tìm.

Nếu tổng các phần tử của $S$ không chia hết cho $2n$ thì $S\cup\{n\}$ là tập cần tìm.

Thật vậy, vì $n\ge4$ nên sẽ tồn tại 2 số không cùng số dư khi chia cho $n$, không mất tính tổng quát, giả sử đó là $x_1,x_2$.

Xét $n$ số sau: $x_1, x_2, x_1+x_2, x_1+x_2+x_3,...,x_1+x_2+...+x_{n-1}$. 

Nếu có ít nhất 1 số trong $n$ số trên chia hết cho $n$ thì xong.

Nếu không có số nào trong $n$ số trên chia hết cho $n$ thì sẽ tồn tại 2 số có cùng số dư khi chia cho $n$. Khi đó hiệu 2 số này sẽ chia hết cho $n$, suy ra $(*)$.

[bangbang1412]

Bạn HSGS trình bày lại được không , mình không hiểu bạn định làm gì viết cũng khó hiểu nữa . Nếu chơi " đao to mổ gà " thì dùng định lý mahailescu =)) còn không thì mình nhớ anh IMOer đã giải với $p=5$ và chắc là tương tự thôi .

Bài viết đã được chỉnh sửa nội dung bởi bangbang1412: 10-06-2016 - 11:05

[IMOer]

Thực ra bài 53 không khác bài 48 là mấy, chỉ là trường hợp tổng quát thôi. Với trường hợp $x+1$ là số chính phương, ta có thể dùng phương trình Pell để giải quyết như cách dưới đây.

 

Lời giải bài 53:

Bổ đề: Với ${{a}^{p}}+{{b}^{p}}={{c}^{2}}$ và $\gcd \left( a,b \right)=1$ thì $p|c$ hoặc $a+b$ là một số chính phương.

Chứng minh bổ đề: Ta có: ${{c}^{2}}=\left( a+b \right)\left( {{a}^{p-1}}-{{a}^{p-2}}b+...-a{{b}^{p-2}}+{{b}^{p-1}} \right)$

Gọi $d=\gcd \left( a+b,{{a}^{p-1}}-{{a}^{p-2}}b+...-a{{b}^{p-2}}+{{b}^{p-1}} \right)$ thì suy ra: $d|p{{a}^{p-1}}$ và $d|p{{b}^{p-1}}$.

Mà $\gcd \left( a,b \right)=1$ suy ra: $d|p$.

Nếu $d=1$ thì suy ra: $a+b$ là một số chính phương.

Nếu $d=p$ thì suy ra: $p|c$.

 

Quay lại bài toán, ta có:

Nhận thấy nếu $(x,y)$ là nghiệm thì $(x,-y)$ cũng là nghiệm nên ta sẽ chỉ xét $y\ge0$.

Với $y=0$ thì ta suy ra: $x=-1$

Với $y=1$ thì ta suy ra: $x=0$

Với $y\ge 2$ thì ta cũng suy ra: $x\ge 2$.

Lại có: ${{x}^{p}}=\left( y-1 \right)\left( y+1 \right)$.

Nếu $2|y$ thì suy ra: $\left\{ \begin{array}{l}y-1={{a}^{p}} \\y+1={{b}^{p}}\end{array} \right.$ với $a,b\in \mathbb{N},\ \gcd \left( a,b \right)=1$.

Khi đó suy ra: ${{b}^{p}}-{{a}^{p}}=2$, dễ thấy vô nghiệm.

Nếu $2\nmid y$ thì ta có:

Xét phương trình: ${{y}^{2}}={{x}^{p}}+1$

Nếu $x+1$ là số chính phương, giả sử $x+1=t^2; t\ge 2$ thì ta xét phương trình Pell $X^2-xY^2=1$.

Khi đó phương trình Pell có các nghiệm $(X,Y)=(t,1)$ và $(X,Y)=(y, x^{\frac{p-1}{2}})$.

Nên sẽ tồn tại số nguyên dương $n$ sao cho $y+x^{\frac{p-1}{2}}\sqrt x=(t+\sqrt x)^n$.

Hệ số của $\sqrt x$ ở vế phải sẽ phải chia hết cho $x$ nên $x|nt^{n-1}$.

Vì $2\nmid y$ nên $2|x$, suy ra $2\nmid t$, dẫn tới $2|n$.

Khi đó hệ số của $\sqrt x$ ở vế phải chia hết cho $t$, nên $t|x^{\frac{p-1}{2}}$.

Gọi $q$ là ước nguyên tố của $t$, khi đó $q|x$, mà $x+1=t^2$, suy ra $q|1$, vô lý.

Nếu $x+1$ không là số chính phương thì theo bổ đề ta có: $p|y$.

Ta xét 2 trường hợp sau:

Trường hợp 1: $y+1=2{{a}^{p}};\ y-1=2^{p-2}{{b}^{p}}$ với $a,b\in \mathbb{N},\ \gcd \left( a,b \right)=1,\ a$ lẻ. Khi đó dễ dàng suy ra được: $a>b\Rightarrow a-1\ge b$.

Ta có: ${{a}^{2p}}-{{\left( 2b \right)}^{p}}={{\left( \frac{y+1}{2} \right)}^{2}}-2\left( y-1 \right)={{\left( \frac{y-3}{2} \right)}^{2}}$

Vì $\frac{y-3}{2}\in \mathbb{N}$ và không chia hết cho $p$ nên theo bổ đề ta có: ${{a}^{2}}-2b$ là số chính phương, vô lý vì: ${{a}^{2}}>{{a}^{2}}-2b\ge {{a}^{2}}-2\left( a-1 \right)>{{\left( a-1 \right)}^{2}}$.

Trường hợp 2: $y+1=2^{p-2}{{a}^{p}};\ y-1=2{{b}^{p}}$ với $a,b\in \mathbb{N},\ \gcd \left( a,b \right)=1,\ b$ lẻ. Giải quyết tương tự suy ra trường hợp này vô nghiệm.

 

Bài 54: (Nguồn: Sưu tầm)

Cho dãy các số nguyên dương $a_1, a_2, ...$ thoả mãn với mọi $n\ge 1$ thì tồn tại số tự nhiên $k_n$ nhỏ hơn $9$ sao cho $a_{n+1}=10a_n+k_n$.

Chứng minh rằng dãy số trên chứa vô số hợp số.

[bangbang1412]

Em nghĩ dãy $k_{n}$ phải nhỏ hơn $10$ và cách chúng ta thêm vào phải lặp lại em không chắc về ý kiến của mình . Mong anh có ý kiến thêm .

Bài viết đã được chỉnh sửa nội dung bởi bangbang1412: 11-06-2016 - 02:00