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

[canhhoang30011999]

Bài 40

Cái tính cẩu thả mãi không sửa được . Mình xin giải lại như sau

Ta có nếu m có ước nguyên tố $p$ dạng 4k +3 mà $m$ chia hết cho $p^{2}$

Khi đó do tồn tại $x,y$ sao cho $x^{2}+y^2\equiv p^{2}+p(mod m)$ (vô lý)

Xét Th m chia hết cho p nhưng không chia hết cho p^{2}

xét m=$2^{t}.p_{1}^{a_1}..p_{k}^{a_k}.q_{1}q_{2}..q_{k}=2^{t}m_{1}.q_{1}.q_{2}..q{k}$ với $p_{i}$ là số nguyên tố dạng $4k+1$ $q_{i}$ là số nguyên tố dạng $4k+3$

nếu $t>1$ thì ta suy ra tồn tại $x^{2}+y^{2} \equiv 3 (mod m)$ nên vô lý

ta sẽ chứng minh $t=0$ hoặc $t=1$ thỏa mãn

Nếu $t=1$ thì $m_{1}=a^{2}+b^{2}$ với $(a,b)=1$ (đã chứng minh ở bài toán trên) nên tồn tại $n$ sao cho $n^{2}+1$ chia hết cho $m$ (cái này có thể dùng kí hiệu Jacobi để chứng minh )

xét $l$ là một thặng dư bất kì mod $m_{1}$ thì nếu l lẻ thì $l=(\frac{t+1}{2})^{2}-(\frac{t-1}{2})^{2} \equiv a^{2}+b^{2}(mod m_{1})$ (do -1 là số chính phương mod $m_{1}$)

nếu l chẵn thì xét $l+m_{1}$

 tồn tại x,y,a,b sao cho

$x^{2}+y^{2}\equiv t (mod m)$

$a^{2}+b^{2} \equiv t (mod 2)$

xét $q$ nguyên tố bất kỳ thì ta có tồn tại $\frac{q+1}{2}$ thặng dư bình phương  của q

ta có xét t bất kỳ thì $t=1+t-1=2+t-2=....=p-1+t-(p-1)$

ta có 2 tổng $i+p-i$ và $j+p-j$ trùng nhau khi i+j=t nên ta chia t thành $\frac{p-1}{2}$ tổng của 2 số khác 0 hay là t viết được thành $\frac{p+1}{2}$ tổng của 2 số 

nếu $\frac{t}{2}$ là thặng dư bình phương ta có đpcm

nếu $\frac{t}{2}$không là thặng dư bình phương thì sẽ tồn tại 2 thặng dư bình phương ở cùng 1 tổng

vậy luôn tồn tại $a_{i},b_{i}$ sao cho $a_{i}^{2}+b_{i}^{2}=t (mod q_{i})$

Dùng định lý thặng dư Trung Hoa ta có đpcm

trường hợp t=0 thì tương tự

p/s: có bạn nào nói rõ cho mình về ký hiệu Jacobi được không?

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

[bangbang1412]

Thứ nhất mình không hiểu câu đầu tiên của Hoàng lắm còn thứ hai nếu kí hiệu jacob là $1$ thì chưa chắc nó là thặng dư bậc hai cậu nhé

Cái dòng mà cậu bảo dùng kí hiệu Jacob để chứng minh $n^{2}+1$ là bội $m$ ấy làm rõ ra được không cậu hơn nữa tổng $i+p-i$ trùng $j+p-j$ rồi xét $l+m_{1}$ , mỗi đoạn tồn tại cậu đánh cẩn thận dài một chút cũng không sao, cậu latex các thứ và trình bày rõ từng phần ra được không .
À mà thặng dư TH ntn =)) rõ luôn nhé

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

[bangbang1412]

Lời giải bài 40 : 

Bổ đề $1$ : Bài toán đúng với mọi số nguyên tố $p$

Bổ đề $2$ : $m$ nếu thỏa mãn và nếu gọi $p$ là một ước nguyên tố và $p=2$ hoặc $p\equiv 3(mod4)$ thì $v_{p}(m)<2$

Chứng minh : 

$1)$ Với một lớp thặng dư $k$ xét $k - x^{2} \equiv y^{2} (mod p)$ , rõ ràng $x^{2}$ có $\frac{p+1}{2}$ lớp nên $k - x^{2}$ và $y^{2}$ đều có $\frac{p+1}{2}$ lớp , nhưng chỉ có $p$ lớp thặng dư nên có hai lớp bằng nhau nên bổ đề $1$ được cm

$2)$ Thật vậy xét $2^{2}$ thì $3 \not\equiv x^{2}+y^{2}(mod4)$ , còn nếu $p \equiv 3(mod4)$

Trong các số đó chọn ra một số dạng $pu$ với $(u,p)=1$ thế thì $x^{2}+y^{2}\equiv pu \equiv 0 (modp)$ và $x^{2}+y^{2}\equiv pu (modp^{2})$ nên vô lý do $p|x,y$ 

Ngược ta ta sẽ chứng minh tất cả các số dạng này đều thỏa mãn .

Nếu $v_{2}(m)=0$ thì $m$ có dạng $p_{1}...p_{l}q_{1}^{a_{1}}....q_{t}^{a_{t}}= \prod_{i=1}^{l}p_{i}.M$ trong đó $p_{i} \equiv 3(mod4) , q_{i}\equiv 1(mod4)$

Ta chứng minh $-1$ là thặng dư bậc $2$ của $M$ , mỗi số $q_{i}$ đều có một bội dạng $r^{2}+1$

Bổ đề $3$: Nếu hai số $(a,b)=1$ có $u,v$ thỏa $u^{2}\equiv -1(moda)$ và $v^{2}\equiv -1(modb)$ thế thì có $j^{2}\equiv -1(modab)$

Chứng minh : Theo định lý trung hoa về thặng dư có $j$ mà $j\equiv u(moda),j\equiv v(modb)$ thế thì $j^{2}\equiv -1(modab)$ 

Bổ đề $4$: Cho $q\equiv 1(mod4)$ thế thì có $j^{2}+1\equiv 0(mod q^{n})$ với $n$ chọn trước .

Chứng minh : Sử dụng bổ đề Hansel cho đa thức ( hệ quả luôn , các bạn search mạng )

Bổ đề $5$: Nếu $a^{2}+b^{2}\equiv v(modx),c^{2}+d^{2}\equiv v(mod y)$ thì tồn tại $i^{2}+j^{2} \equiv v(mod xy)$ với $(x,y)=1$

Chứng minh : Định lý thặng dư Trung hoa có $i \equiv a(modx), c(mody)$ và $j \equiv b(modx),d(mody)$ nên có đpcm

Theo hai bổ đề $3,4$ trên $M$ có bội dạng $u^{2}+1$

Xét lớp thặng dư $l$ 

Nếu $l$ lẻ thì $l$ có dạng $(\frac{l+1}{2})^{2}-(\frac{l-1}{2})^{2}\equiv (\frac{l+1}{2})^{2}+(u\frac{l-1}{2})^{2}(mod M)$

Nếu $l$ chẵn thì $l+M$ lẻ xét như trên đúng

Còn vụ $p_{1}...p_{l}$ , với mỗi $l$ luôn $a,b$ đồng dư $a^{2}+b^{2}\equiv l(modp_{i})$ theo bổ đề $1$

Theo định lý thặng dư Trung Hoa với một lớp $l$ thì từ các bổ đề trên cho ta đpcm

Các TH khác xet tương tự

Kết luận : Tất cả các số $m$ thỏa mãn thì $v_{p}(m)<2$ với $p$ nguyên tố , $p=2$ hoặc $p\equiv 3(mod4)$

Anybody check for me , à điểm Ego ơi 

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

[Ego]

Bài 39 : Chứng minh với mọi $n>1$ tồn tại $2m$ số nguyên tố phân biệt đôi một $(p_{1},...p_{m})$ và $(q_{1},...q_{m})$ 

Trong đó :

$a) p_{i} > q_{i}$

$b) n = \sum_{i=1}^{m}(p_{i}-q_{i})$

Nguồn : VMF 

Bài này mình nhớ có anh Tantlsh có từng đăng trên diễn đàn và chưa nhận được lời giải, mình cũng chưa kiếm lại bài đó. Hiện giờ đề nghị các bạn khoan hãy đề xuất bài toán mới, mình nghĩ bài 39 khá hay.

Giả sử $n\neq p^a-1$, khi đó biểu diển $p$-phân của $n$ sẽ có chữ số tận cùng khác $p-1$.

Mình không hiểu chỗ này của Vistor lắm, ví dụ cho $p = 7$ đi, thì mình cứ lấy $n = (26)_{7} = 2\times 7 + 6$ khác $7^{a} - 1$ chứ nhỉ?


Hiện đã cập nhật điểm đến post #111 (đối với các mod) vì còn một số post cần phải kiểm tra lại

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

[canhhoang30011999]

Thứ nhất mình không hiểu câu đầu tiên của Hoàng lắm còn thứ hai nếu kí hiệu jacob là $1$ thì chưa chắc nó là thặng dư bậc hai cậu nhé

Cái dòng mà cậu bảo dùng kí hiệu Jacob để chứng minh $n^{2}+1$ là bội $m$ ấy làm rõ ra được không cậu hơn nữa tổng $i+p-i$ trùng $j+p-j$ rồi xét $l+m_{1}$ , mỗi đoạn tồn tại cậu đánh cẩn thận dài một chút cũng không sao, cậu latex các thứ và trình bày rõ từng phần ra được không .
À mà thặng dư TH ntn =)) rõ luôn nhé

Cảm ơn Bằng đã góp ý. Nhìn chung ý tưởng của mình cũng giống của Bằng thôi

Còn về phần Jacobi thì mình không thạo phần này lắm nhưng chắc là thế này

$(\frac{-1}{m_{1}})= \prod (\frac{-1}{p_{i}})^{a_{i}}= 1$

do các $(\frac{-1}{p_{i}})$ đều bằng $1$ nên -1 là thặng dư bậc 2 của $m_{1}$

trong bài mình có cm bằng cách khác mà mình chỉ góp ý thêm thôi

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

[bangbang1412]

Cảm ơn Bằng đã góp ý. Nhìn chung ý tưởng của mình cũng giống của Bằng thôi

Còn về phần Jacobi thì mình không thạo phần này lắm nhưng chắc là thế này

$(\frac{-1}{m_{1}})= \prod (\frac{-1}{p_{i}})^{a_{i}}= 1$

do các $(\frac{-1}{p_{i}})$ đều bằng $1$ nên -1 là thặng dư bậc 2 của $m_{1}$

trong bài mình có cm bằng cách khác mà mình chỉ góp ý thêm thôi

https://vi.wikipedia.../Kí_hiệu_Jacobi

Cậu đọc kĩ nhé , kí hiệu Jacobi $\left ( \frac{a}{m} \right )=1$ thì chưa chắc đã có $x^{2}\equiv a(modm)$ nhưng nếu $\left ( \frac{a}{m} \right)=-1$ thì chắc chắn không tồn tại $x^{2}\equiv a(modm)$

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

[Zaraki]

Lời giải. Bài toán tương đương với việc tìm nghiệm tự nhiên của $2a^2+1=3^k$.

 

TH1. Nếu $2 \mid k$ thì phương trình trở thành $b^2-2a^2=1$ với $b=3^{k/2}$. Ta thấy $(a_1,b_1)=(2,3)$. Phương trình Pell này có nghiệm tổng quát $$\begin{cases} b_{n+1}=3b_n+4a_n, \\ a_{n+1}=2b_n+3a_n. \end{cases}$$

Dễ thấy rằng với $3 \nmid b_i$ với $i \ge 2$. Do đó chỉ có $(a,b)=(2,3)$ hay số chính phương đó là $4$.

 

TH2. Nếu $2 \nmid k$ thì $3b^2-2a^2=1$ với $b=3^{k/2}$. Ta thấy $(a_0,b_0)=(1,1)$. Xét phương trình $u^2-6v^2=1$ có nghiệm cơ sở $(u_1,v_1)=(5,2)$. Khi đó nếu $(u_n,v_n)$ là nghiệm tổng quát của phương trình này thì ta có $$\begin{cases} b_n=u_n+2v_n, \\ a_n=u_n+3v_n. \end{cases} \qquad  \qquad \begin{cases} u_{n+1}=5u_n+12v_n, \\ v_{n+1}=2u_n+5v_n \end{cases}.$$

Khi đó $b_n=u_n+2v_n=9u_{n-1}+22v_{n-1}$. Với $i \ge 2$ thì $3 \nmid v_i$. Thật vậy, nếu $3 \mid v_n$ mà $3 \mid b_n$ dẫn đến $3 \mid u_n$, điều này mâu thuẫn vì $u_n^2-6v_n^2=1$. Vậy ta chỉ cần xét $(a_1,b_1)$. Ta thấy $b_1=9, a_1=11$. Hay số chính phương ta tìm được ở trường hợp này là $11^2$ và $1$.

Lời giải chỉnh sửa cho bài 36.

 

Lời giải. Ta xét bổ đề sau:

 

Bổ đề. $\nu_3 \left( \binom{n}{2l} \right) \ge \nu_3(n)-\nu_3(l)$ với $3 \mid n,3 \mid l$.

Chứng minh. Ta có $\binom{n}{2l}= \frac{(n-2l+1) \cdots n}{(2l)!}$.

Nếu $3 \mid l$ thì $$\begin{aligned} \nu_3 \left( (n-2l+1) \cdots n \right) & = \nu_3(n-2l+3)+\nu_3(n-2l+6)+ \cdots + \nu_3(n-3)+\nu_3(n), \\ & \ge \sum_{i=0}^{2l/3-2}\nu(3+3i)+\nu_3(n) = \nu_3((2l)!)-\nu_3(2l)+\nu_3(n). \end{aligned}$$

Như vậy, bổ đề được chứng minh.   $\square$

______________________________________________________________________

 

Quay lại bài toán, ta xét tương tự xét như lời giải sai trên.

 

Trường hợp 1. Nếu $2 \nmid k$ và ta tìm được công thức nhiệm như trên, từ đó có nghiệm tổng quát $$\begin{aligned} b_n & =\frac 12 \left[ \left( 3+2\sqrt 2 \right)^n+ \left( 3-2\sqrt 2 \right)^n \right], \\ & = 3^n+\binom{n}{2} 3^{n-2}(2\sqrt2)^2+\binom{n}{4} 3^{n-4}(2\sqrt 2)^4+ \cdots + \binom{n}{2 \left \lfloor n/2 \right \rfloor} 3^{n-2 \left \lfloor n/2 \right \rfloor}(2\sqrt 2)^{2\left \lfloor n/2 \right \rfloor}. \end{aligned}$$

Từ đây ta suy ra để có $3 \mid b_n$ thì $2 \nmid n$. Khi đó $\nu_3 \left( \binom{n}{2 \left \lfloor n/2 \right \rfloor} 3^{n-2 \left \lfloor n/2 \right \rfloor}(2\sqrt 2)^{2\left \lfloor n/2 \right \rfloor} \right) = \nu_3 \left( 3n \cdot (2\sqrt 2)^{n-1} \right)= \nu_3(n)+1$. Ta sẽ chứng minh rằng thì $$\nu_3 \left( \binom{n}{2i}3^{n-2i}8^i \right) > \nu_3(n)+1$$ với mọi $0 \le i \le (n-3)/2$ hay

\begin{equation} \label{pqt1} \nu_3 \left( \binom{n}{2i} \right)+n-2i >\nu_3(n)+1.\end{equation}

Hiển nhiên với $3 \nmid n$ thì \eqref{pqt1} đúng. Ta đi xét với $3 \mid n$. Ta thấy với $2i <n-\nu_3(n)-1$ thì bài toán hiển nhiên đúng, ta đi xét với những $i$ thoả $n-2i \le \nu_3(n)+1$. 

 

Nếu $\nu_3(i)\ge \nu_3(n)$ thì $3^{\nu_3(n)}  \mid n-2i \le \nu_3(n)+1$, mâu thuẫn với mọi $3 \mid n$. Vậy $\nu_3(i) <\nu_3(n)$ suy ra $3^{\nu_3(i)} \mid n-2i$ suy ra $n-2i \ge 3^{\nu_3(i)}.$ Do đó kết hợp với bổ đề thì $$\nu_3 \left( \binom{n}{2i} \right) +n-2i \ge \nu_3(n)+n-2i-\nu_3(2i) \ge \nu_3(n)+ 3^{\nu_3(i)}-\nu_3(i) >\nu_3(n)+1.$$

BĐT trên chỉ đúng nếu $3 \mid i$. Trường hợp $3 \nmid i$, ta thấy rằng $$\binom{n}{2i}= \binom{n}{2i-2} \cdot \frac{(n-2i+2)(n-2i+1)}{(2i-1)2i}.$$

Nếu $i \equiv 1 \pmod{3}$ thì $\nu_3 \left( \binom{n}{2i} \right) = \nu_3 \left( \binom{n}{2i-2} \right)+\nu_3(n-2i+2)>\nu_3(n)+1$ với mọi $i \equiv 1 \pmod{3}$.

Nếu $i \equiv 2 \pmod{3}$ thì lập luận tương tự để có $\nu_3(2i-1) < \nu_3(n)$ suy ra $\nu_3(2i-1) = \nu_3(n-2i+1)$ nên kết hợp với đẳng thức trên thì $\nu_3 \left( \binom{n}{2i} \right) \ge \nu_3 \left( \binom{n}{2i-2} \right)>\nu_3(n)+1$.

Như vậy \eqref{pqt1} được chứng minh. Ta dẫn đến $\boxed{\nu_3(b_n)=\nu_3(n)+1}$ với $2 \nmid n$ suy ra $b_n=3^{\nu_3(n)+1} \ge 3^n$ dẫn đến $n=1$. Ta tìm được $b_1=3$ và $a_1=2$ hay số chính phương tìm được là $4$.

 

Trường hợp 2. Nếu $2 \mid k$ thì ta có nghiệm tổng quát $$b_n= 3^n+ \binom{2n+1}{2}3^{n-1} \cdot 2+\binom{2n+1}{4}3^{n-2} \cdot 2^2+ \cdots+ \binom{2n+1}{2n} \cdot 2^n.$$

Với $n=0$ thì $b_0=1$ thì $a_0=1$. Ta tìm được số chính phương $1$. Nếu $n \ge 1$ thì $3 \mid 2n+1$. Tương tự, ta sẽ đi chứng minh BĐT sau với mọi $1 \le i \le n-2$.

\begin{equation} \label{pqt2} \nu_3 \left( \binom{2n+1}{2i}3^{n-i}\cdot 2^{i} \right)= \nu_3 \left( \binom{2n+1}{2i} \right)+n-i>\nu_3(2n+1)+1. \end{equation}

Hiển nhiên bài toán đúng với những $i$ thoả $n-i \ge \nu_3(2n+1)+2$. Ta đi chứng minh bài toán đúng cho những $i$ thoả $n-i \le \nu_3(2n+1)+1$. 

 

Nếu tồn tại $i$ thoả $\nu_3(i) \ge \nu_3(2n+1)$ thì $3^{\nu_3(2n+1)} \mid 2n+1-2i \le 2\nu_3(2n+1)+3$. Điều này xảy ra khi $2n+1-2i=3$ và $\nu_3(2n+1)=1$ suy ra $n=1$. Ta tìm được $b_1=9$ nên $a_1=11$ suy ra số chính phương tìm được là $11$.

 

Nếu với mọi $i$ mà $n-i \le \nu_3(2n+1)$ thì $\nu_3(i) <\nu_3(2n+1)$ thì $3^{\nu_3(i)} \cdot k = 2n+1-2i$. Khi đó kết hợp với bổ đề thì $$\nu_3 \left( \binom{2n+1}{2i} \right)+n-i \ge \nu_3(2n+1)-\nu(i)+n-i \ge \nu_3(2n+1)+ \frac{3^{\nu_3(i)}k-1}{2}-\nu_3(i)>\nu_3(2n+1)+1.$$

BĐT trên chỉ đúng khi ít nhất một trong hai điều kiện $k \ge 2$ hoặc $\nu_3(n) \ge 2$ đúng.

 

Nếu $\nu_3(i)=1,k=1$ thì $3=2n+1-2i$ suy ra $i=n-1$, mâu thuẫn vì $i \le n-2$.

Nếu $\nu_3(i)=0$ thì ta có $$\binom{2n+1}{2i}= \binom{2n+1}{2i-2} \cdot \frac{(2n+1-2i+2)(2n+1-2i+1)}{(2i-1)2i}.$$

Xét từng trường hợp $i \equiv 1,2 \pmod{3}$ như TH1 để suy ra đpcm.

 

Như vậy \eqref{pqt2} đúng. Do đó $$b_n=3^{\nu_3(2n+1)+2} \cdot K+2^{n-1} \left( 3\binom{2n+1}{2n-2}+2\binom{2n+1}{2n} \right)$$

Ta có $$\nu_3(2n+1) \le \nu_3 \left( 3\binom{2n+1}{2n-2}+2\binom{2n+1}{2n} \right)= \nu_3( (2n+1)(2n^2-n+2) ) <\nu_3(2n+1)+2,$$ suy ra $\boxed{\nu_3(2n+1) \le \nu_3(b_n)  < \nu_3(2n+1)+2}$. Kết hợp với $b_n \ge 3^n$ ta suy ra chỉ có thể $\nu_3(2n+1) \in \{ 1,2 \}$. Ta tìm được $b_1=9$.

 

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

[Zaraki]

Bài 39 : Chứng minh với mọi $n>1$ tồn tại $2m$ số nguyên tố phân biệt đôi một $(p_{1},...p_{m})$ và $(q_{1},...q_{m})$ 

Trong đó :

$a) p_{i} > q_{i}$

$b) n = \sum_{i=1}^{m}(p_{i}-q_{i})$

Nguồn : VMF 

Một bài toán chứng minh tồn tại hay. Sau đây là lời giải của mình.

 

Lời giải. Xin nhắc lại bổ đề Bertrand. 

Bổ đề Bertrand. Với mọi số nguyên dương $n>1$ luôn tồn tại số nguyên tố $p$ sao cho $n<p<2n$.

 

Quay lại bài toán, xét một số nguyên dương $n>1$ bất kì. Theo bổ đề thì tồn tại số nguyên tố $p_0$ thoả $n<p_0<2n$. Khi đó $n=p_0-r_0$ thì $1 \le r_0$ và $p_0>2r_0$. Tiếp tục áp dụng bổ đề Bertrand thì tồn tại số nguyên tố $p_1$ sao cho $r_0<p_1<2r_0$ khi đó $n=p_0-r_0=p_0-(p_1-r_1)=(p_0-p_1)+r_1$ với $p_1>2r_1$. Tương tự, tồn tại số nguyên tố $p_2$ sao cho $2r_1>p_2>r_1$ suy ra $n=(p_0-p_1)+p_2-r_2$ với $p_2>2r_2 \ge 2$. Bất cứ khi nào $r_i>1$, ta cứ tiếp tục áp dụng Bổ đề Bertrand. Theo cách xây như trên thì ta luôn có các số $p_i$ phân biệt, hay cụ thể hơn $p_0>p_1>p_2> \cdots $

 

Như vậy, đến một lúc nào đó sẽ tồn tại $i$ sao cho $r_i=1$. Có hai khả năng sau có thể xảy ra:

 

TH1. Nếu $n= (p_0-p_1)+(p_1-p_2)+ \cdots + (p_{i-1}-p_i)+r_i$ với $p_i>2r_i=2$ theo cách xây dựng các số $p_l$.

Nếu $p_i=3$ thì $n=(p_0-p_1)+(p_1-p_2)+ \cdots + (p_{i-1}-2)$, ta có đpcm.

Nếu $p_i >3$ thì $n=(p_0-p_1)+(p_1-p_2)+ \cdots + (p_{i-1}-p_i)+(3-2)$, ta có đpcm.

 

TH2. Nếu $n=(p_0-p_1)+(p_1-p_2)+ \cdots + (p_{i-2}-p_{i-1})+p_{i}-r_i$ với $p_i>2r_i=2$ theo cách xây dựng các số $p_l$.

 

Nếu $p_i=3$ thì với $p_{i-1}=5$ ta có $n=(p_0-p_1)+ \cdots + (p_{i-2}-3)$. Còn với $p_{i-1}>5$ thì $n=(p_0-p_1)+ \cdots + (p_{i-2}-p_{i-1})+(5-3)$.

 

Nếu $p_i=5$ thì với $p_{i-1}=7$ thì $n=(p_0-p_1)+ \cdots + (p_{i-2}-3)$. Còn với $p_{i-1}>7$ thì $n=(p_0-p_1)+ \cdots +(p_{i-2}-p_{i-1})+(7-3)$.

 

Nếu $p_i=7$ thì với $p_{i-1}=11$ thì $n=(p_0-p_1)+ \cdots + (p_{i-2}-5)$. Còn với $p_{i-1}>11$ thì $n=(p_0-p_1)+ \cdots +(p_{i-2}-p_{i-1})+(11-5)$.

 

Nếu $p_i>7$ thì $n=(p_0-p_1)+\cdots + (p_{i-2}-p_{i-1})+(p_i-5)+(7-3)$.

 

Bài toán được chứng minh.    $\blacksquare$

 

Bài 41. [ITAMO 2016] Tìm tất cả các số nguyên dương $(a,n)$ thoả $a \ge n \ge 2$ và $(a+1)^n+a-1$ là luỹ thừa của $2$.

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

[bangbang1412]

Bài 41 : Dễ dàng nhận thấy rằng $a|(a+1)^{n}+a-1$ nên $a$ cũng sẽ là một lũy thừa của $2$ , bây giờ đặt $(a+1)^{n}+a-1=2^{b}>a=2^{c}$ ( vì nếu bằng nhau thi $a=0$ vô lý ), bây giờ xét khai triển sau của $(a+1)^{n}+a-1$ với $a=2^{c}$ có:

                                                                                                              $$(2^{c}+1)^{n}+2^{c}-1=2^{cn}+\binom{n}{1}2^{c(n-1)}+....\binom{n}{n-2}2^{2c}+(n+1)2^{c}=2^{b}$$

Nếu $a=n=2^{c}$ thế thì từ đẳng thức trên phải có $c=b$ nhưng điều này rõ ràng không xảy ra .

 

Ta lại thấy thằng $2^{c}> n \geq 2$ nên $v_{2}(n+1)\leq v_{2}(2^{c})=c$ , dấu bằng nếu $n+1=2^{c}$ , cũng dễ viết lại $v_{2}((n+1)2^{c}) \leq 2c$ , nếu dấu bằng không xảy ra :

 

                                          $v_{2}(n+1)=2^{t}$ với $t<c$ ta có $v_{2}(2^{b})=b=v_{2}(2^{cn}+\binom{n}{1}2^{c(n-1)}+....+(n+1)2^{c}) \leq 2c$ cái này suy ra vì ngoài số hạng cuối lũy thừa bậc hai tất cả các số còn lại đều lớn hơn $2c$

Hay :

                                                                                                                $$2^{cn}\leq 2^{cn}+\binom{n}{1}2^{c(n-1)}+.....+\binom{n}{n-2}2^{2c}+(n+1)2^{c}\leq 2^{2c}$$ 

Nên $2\leq n \leq 2$ , thế thì $n=2$ nhưng khi đó $(a+1)^2+a-1=a^{2}+3a=a(a+3)=2^{c}(2^{c}+3)=2^{b}$ điều này rõ ràng vô lý , vậy dấu bằng phải xảy ra tức là $n=2^{c}-1$ , khi đó viết lại đẳng thức $v_{2}(VT) \leq 2c+1$ nếu $c\geq 3$ thế thì lại có $cn \leq 2c+1$ , suy ra $n=3,c=1$ vô lý do $c\geq 3$

Vậy bắt buộc phải có $c=1,2$ , nếu $c=1$ thì $a=2^{c}\geq n\geq 2$ ta đã biết $n=2$ không có nghiệm nên phải có $c=2$ tức là $a=4$ , và $n=a-1=3$ thử lại thấy đúng . Suy ra bài toán có nghiệm duy nhất $(a,n)=(4,3)$ 

Bài 42 : Với mọi số $n$ nguyên dương , tính giá trị biểu thức sau :

                                                                                                                                                    $$\frac{\prod_{k=1}^{2n-1}k^{min(k,2n-k)}}{\prod_{k=1}^{n-1}(2k+1)^{2n-2k-1}}$$

Nguồn : Aops

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

[Zaraki]

Bài 42 : Với mọi số $n$ nguyên dương , tính giá trị biểu thức sau :

                                                                                                                                                    $\frac{\prod_{k=1}^{2n-1}k^{min(k,2n-k)}}{\prod_{k=1}^{n-1}(2k+1)^{2n-2k-1}}$

Nguồn : Aops

Lời giải. Ta chứng minh theo quy nạp rằng $$\displaystyle A(n)= \frac{ \prod_{k=1}^{2n-1}k^{\min \{ k,2n-k \} }}{\prod_{k=1}^{n-1}(2k+1)^{2n-2k+1}}=2^{(n-1)n}.$$

Với $n=1$ bài toán đúng. Giả sử bài toán đúng với $n$, tức $A(n)=2^{(n-1)n}$. Ta sẽ chứng minh $A(n+1)=2^{n(n+1)}$. Thật vậy, ta thấy rằng $$A(n+1)= A(n) \cdot \frac{ (n+1)^2(n+2)^2 \cdots (2n)^2(2n+1)}{3^2 \cdot 5^2 \cdots (2n-1)^2 \cdot (2n+1)}=2^{n(n-1)} \cdot \left [ \frac{(n+1)(n+2) \cdots (2n)}{3 \cdot 5 \cdot 7 \cdots (2n-1)} \right]^2.$$

Mặt khác, ta thấy rằng $$n! \cdot (n+1)(n+2) \cdots (2n)=(2n)!=(2 \cdot 4 \cdots 2n) \cdot (3 \cdot 5 \cdots (2n-1))= 2^nn! \cdot (3 \cdot 5 \cdots (2n-1)).$$

Do đó $\frac{(n+1)(n+2) \cdots (2n)}{3 \cdot 5 \cdot 7 \cdots (2n-1)}=2^n$ suy ra $A(n+1)=2^{n(n+1)}$.

Ta có điều phải chứng minh.   $\blacksquare$

 

Bài 43. Giải phương trình nghiệm tự nhiên $2^x=3+5^y$.

[bangbang1412]

Bài 43 :  bài này nghiệm sida quá , phải test code C xong mới dám làm , tưởng dễ ăn mà khó quá  . Viết lại phương trình $128(2^{x-7}-1)=125(5^{y-3}-1)$  ,xét $x>7$ kéo theo $y>3$ theo $LTE$  do $4|5-1$ nên $v_{2}(5^{y-3}-1)=v_{2}(5-1)+v_{2}(y-3)$ .

Do $x>7$ nên $(2,2^{x-7}-1)=1$ do đó $v_{2}(y-3)=5$ , đặt $y-3=2^{5}m$ với $(m,2)=1$ , khi đó $5^{16.2m}-1 \equiv 5^{16}-1 \equiv 0(mod17)$ theo Fermat nhỏ , lại theo Fermat nhỏ $2^{x-7}-1\equiv 0(mod17)$ và $2^{16}\equiv 1(mod17)$ 

Gọi $h$ là cấp của $2$ theo $mod17$ , check qua lại thấy $2$ không phải căn nguyên thủy của $17$ mà có $2^{16}-1=(2^{8}-1)(2^{8}+1)=257(2^{8}-1)\equiv 257.15.17 \equiv 0(mod17)$ , kiểm tra vài TH nhỏ hơn ra có $h=8$ do đó $8|x-7$ . Do đó phương trình tương đương :

                                                                                                                                                                $2^{7}(2^{8n}-1)=5^{3}(5^{32m}-1)$

Xét $m$ theo $mod2$ ta có $5^{32m}-1=5^{2^{5}(2k+1)}-1 \equiv 5^{2^{7}k+2^{5}}-1(mod 257)$ , ta có $2^{7}(2^{8n}-1)\equiv 2^{7}((-1)^{n}-1)\equiv 0,1(mod257)$ , còn trong khi đó do $257$ là số nguyên tố nên theo Fermat nhỏ $5^{256}-1=(5^{128}+1)(5^{128}-1)\equiv 0(mod257)$ , Xét cả hai trường hợp $5^{128}\equiv 1,-1(mod257)$ ta có $VP \equiv 125((-1)^{k}.5^{32}-1) , 125(5^{32}-1)(mod257)$ , kiểm tra trực tiếp thấy không thỏa do đó phải có $y<4$ , khi đó các nghiệm là $(x,y)=(7,3),(3,1),(2,0)$

Bài 44 : ( India ) Giải phương trình nghiệm tự nhiên : $7^{x}=3^{y}+4$ ( gợi ý là xét $mod37$ vì nếu không lần mò mất thời gian )

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

[Minhnguyenthe333]

Lời giải. Ta chứng minh theo quy nạp rằng $$\displaystyle A(n)= \frac{ \prod_{k=1}^{2n-1}k^{\min \{ k,2n-k \} }}{\prod_{k=1}^{n-1}(2k+1)^{2n-2k+1}}=2^{(n-1)n}.$$
Với $n=1$ bài toán đúng. Giả sử bài toán đúng với $n$, tức $A(n)=2^{(n-1)n}$. Ta sẽ chứng minh $A(n+1)=2^{n(n+1)}$. Thật vậy, ta thấy rằng $$A(n+1)= A(n) \cdot \frac{ (n+1)^2(n+2)^2 \cdots (2n)^2(2n+1)}{3^2 \cdot 5^2 \cdots (2n-1)^2 \cdot (2n+1)}=2^{n(n-1)} \cdot \left [ \frac{(n+1)(n+2) \cdots (2n)}{3 \cdot 5 \cdot 7 \cdots (2n-1)} \right]^2.$$
Mặt khác, ta thấy rằng $$n! \cdot (n+1)(n+2) \cdots (2n)=(2n)!=(2 \cdot 4 \cdots 2n) \cdot (3 \cdot 5 \cdots (2n-1))= 2^nn! \cdot (3 \cdot 5 \cdots (2n-1)).$$
Do đó $\frac{(n+1)(n+2) \cdots (2n)}{3 \cdot 5 \cdot 7 \cdots (2n-1)}=2^n$ suy ra $A(n+1)=2^{n(n+1)}$.
Ta có điều phải chứng minh.   $\blacksquare$
 
Bài 43. Giải phương trình nghiệm tự nhiên $2^x=3+5^y$.

Dễ dàng suy ra $y=2k+1$ và $x=2t+1$
$PT<=>\frac{1+(5^k)^2}{(2^t)^2-(5^k)^2}=\frac{2}{3}$ $(1)$
Đặt $d=(1+(5^k)^2,(2^t)^2-(5^k)^2)$
Suy ra $d=(1+(5^k)^2,1+(2^t)^2)$
Áp dụng bổ đề $a^2+1$ không có ước nguyên tố dạng $4n+3$
Suy ra $d=4n+1$
Thay vào $(1)=>25^k+1=2(4n+1)$ và $4^t-25^k=3(4n+1)<=>4^{t-1}=5n+1$ và $25^k=8n+1$
$n=0=>k=0$ và $t=1<=>x=3$ và $y=1$
Xét $n>0$ suy ra $n=3<=>t=3$ và $k=1<=>x=7$ và $y=3$

[Zaraki]

Xét $n>0$ suy ra $n=3<=>t=3$ và $k=1<=>x=7$ và $y=3$

Tại sao xét $n>0$ lại suy ra $n=3$ được nhỉ ?

[IMOer]

Bài 44 : ( India ) Giải phương trình nghiệm tự nhiên : $7^{x}=3^{y}+4$ ( gợi ý là xét $mod37$ vì nếu không lần mò mất thời gian )

Lời giải bài 44: (Không xét modulo 37)

Với $y=0$ thì $7^x=4$, không thoả mãn.

Với $y=1$ thì $7^x=7\Leftrightarrow x=1$.

Với $y\ge 2$ thì $3^y+4\equiv 4\ (\bmod{9})$ nên $7^x\equiv 4\ (\bmod{9})$. Từ đó suy ra: $x\equiv 2\ (\bmod{3})$.

Từ đó suy ra: $7^x$ khi chia cho $13$ có thể dư $10,11,2$ hoặc $3$.

Lại có: $3^y\equiv 3\ (\bmod{7})$ nên $y\equiv 1\ (\bmod{6})$.

Từ đó suy ra: $3^y+4\equiv 7\ (\bmod{13})$.

Vậy phương trình vô nghiệm khi $y\ge 2$.

Vậy phương trình có nghiệm tự nhiên duy nhất $(x,y)=(1,1)$

 

Bài 45: (Sưu tầm)

Cho $n$ là một số nguyên dương. Chứng minh rằng mọi bội số của $10^n-1$ đều có ít nhất $n$ chữ số khác 0.

Bonus: Tổng quát hoá bài toán trên.

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

[Ego]

Lời giải bài 45. Tổng quát: Cho $a, n$ là số nguyên dương với $a \ge 2$. Khi đó mọi bội số của $a^{n} - 1$ đều có ít nhất $n$ chữ số khác $0$ theo cơ số $a$.

Giả sử phản chứng là tồn tại $k$ để $k(a^{n} - 1) = \sum_{i = 1}^{n - 1}b_{i}a^{u_{i}}$ với $u_{i} < u_{i + 1}$ và $1 \le b_{i} \le a - 1$.
Bây giờ nếu $k$ là bội của $a$ thì cũng khá dễ dàng, ta chỉ cần thực hiện trên $\frac{k}{a}.(a^{n} - 1)$ vì nó tương đương nhau. Vậy nên giả sử luôn $k$ không là bội của $a$
Đến đây ta nghĩ đến đưa về đồng dư, đặt $T = a^{n} - 1$. Khi này $\sum_{i = 1}^{n - 1}b_{i}a^{u_{i}} \equiv 0 \pmod{T}$.
Bây giờ ta có thể đẩy về đồng dư bằng cách nếu có $u_{i} = pn + q$ với $0 \le q < n$ và $a^{u_{i}} \equiv a^{q} \pmod{T}$, làm tương tự như vậy với từng $u_{i}$ sau đó ghép cặp chúng lại; và cũng nhờ vậy ta có thể giả sử $v_{i} < n$. Vậy thì $\sum_{i = 1}^{n - 1}b_{i}a^{u_{i}} \equiv \sum_{i = 1}^{n - 1}c_{i}a^{v_{i}}\pmod{T}$ với $v_{i} < v_{i + 1}$ và $0 \le c_{i} \le a - 1$. Mặt khác, để ý là $c_{i}$ có thể bằng $0$ (trong giai đoạn ghép cặp), nhưng không thể tất cả cùng đồng thời bằng $0$ vì nếu có thì do các nhân tử chứa $u_{i}$ ghép lại vì $1 \le b_{i} < a$ (chúng không đủ lớn để chia hết cho $T$). Mà nếu ghép lại, ta cũng chỉ có tối đa $n - 1 < b_{1} + \cdots + b_{n - 1} \le (a - 1).(n - 1) < a^{n} - 1$). Điều này kết luận $0 < \sum_{i = 1}^{n - 1}c_{i}a^{v_{i}}$ và $0 < \sum_{i = 1}^{n - 1}c_{i}a^{v_{i}} \le (a - 1)\sum_{i = 1}^{n - 1}a^{i} = a^{n} - a < a^{n} - 1 = T$. Điều này là vô lý.
Bài 46. (Erdos) Cho $a, b$ là các số nguyên dương sao cho với mọi số nguyên tố $p$ thì $a \pmod{p} \le b \pmod{p}$. Chứng minh rằng $a = b$.

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

[I Love MC]

Lời giải bài 44 : Dễ thấy $x,y \ge 1$ . Ta giả sử $x,y>1$ 
Phương trình được viết trở lại thành : $7(7^{x-1}-1)=3.(3^{y-1}-1)$ 
Suy ra $7|3^{y-1}-1$ 
 Thấy $o_7(3)=6$
Định lí :  Nếu $a$ và $n \ge 1$ là các số nguyên tố cùng nhau thì số nguyên $x$ là nghiệm của phương trình $a^x \equiv 1 \pmod{n} \Leftrightarrow o_n(a)|x$ 
Áp dụng đinh lí vì $(3,7)=1$ vậy nên $6|y-1$ 
Suy ra $3^6-1|3^{y-1}-1$ vậy nên $13|3^{y-1}-1$ 
Suy ra $13|7^{x-1}-1$ . Có $o_13(7)=12$ do vậy $12|x-1$ 
Khi đó $9|7^{12}-1|7^{x-1}-1$ nên vậy $3^{y-1}-1 \vdots 9$ . Điều này vô lí vì $x>1$ 
Do đó $x=1$ kéo theo $y=1$ 
Vậy $(x,y)=(1,1)$
 

[I Love MC]

Lời giải bài 43 : Ta chứng minh phương trình sẽ không có nghiệm nguyên nào để mà $y > 3$
Ta thấy $5^y \vdots 125$ do đó $2^x \equiv 3 \pmod{125}$ . 
Ta có $o_{5^n}(2)=4.5^{n-1}$ (được tính bằng LTE ) 
Do đó $2^{100} \equiv 1 \pmod{125}$ suy ra $x \equiv 7 \pmod{100}$ 
Theo Fermat nhỏ : $2^{100} \equiv 1 \pmod{101}$ do vậy $2^x \equiv 27 \pmod{101}$ 
Khi đó $5^y \equiv 23 \pmod{101}$  
Ta có $o_{101}(5)=100$  
Vì $x \equiv 7 \pmod{100}$ nên $x \equiv 1 \pmod{2}$ suy ra $2^x \equiv 2 \pmod{3}$ suy ra $5^y \equiv 2 \pmod{3}$ suy ra $3|y$ 
Bằng LTE ta chứng minh được $o_{2^n}(5)=2^{n-2}$. Xét nếu $y$ chẵn cộng với $y \ge 3$ thì $5^y \equiv 1 \pmod{2^3}$ 
Suy ra $5^y+3 \equiv 4 \pmod{2^3}$ do đó $x=2$ (mâu thuẫn) . Do đó $y$ lẻ . 
Kiểm tra thấy không có $y$ nào thỏa 
Từ đó suy ra $(x,y)=(7,3),(3,1),(2,0)$

[canhhoang30011999]

.

Với $y\ge 2$ thì $3^y+4\equiv 4\ (\bmod{9})$ nên $7^x\equiv 4\ (\bmod{9})$. Từ đó suy ra: $x\equiv 2\ (\bmod{4})$, hay $x=2k$, với 

Theo em thì đoạn này phải là $x\equiv 2(mod3)$ chứ (vì mà là $ord_{9}(7)$)

đây là lời giải của mình

xét $y=1$ thì suy ra $x=1$.

xét $x=1$ thì suy ra $y=1$.

xét $x,y>1$ thì $7/ 3^{y-1}-1$ nên $6/y-1$ ($ord_{7}(3)=6$)

nên $(3^{6}-1/ 3(3^{y-1}-1)=7(7^{x-1}-1)$ nên $13/7^{x-1}-1$

nên $12/ x-1$ (do $12=ord_{13}(7)$) (vô lý do $x \equiv 2 (mod 3)$

[bangbang1412]

Bài 46 : 

Bổ đề  : Định lý Sylvester - Schur : Giả sử $n \geq 2k$ thế thì tồn tại một ước nguyên tố $>k$ của $\binom{n}{k}$ ( chứng minh đề cập cuối bài viết ) . 

Quay lại bài toán : Chứng minh nếu $a (mod p ) \leq b (mod p)$ với mọi số nguyên tố $p$ thì $a = b$ , với mọi số $x$ đặt $x(p)$ là số dư trong phép chia $x$ cho số nguyên tố $p$ , thế thì $0 \leq x(p) < p$ . Bây giờ chọn một số nguyên tố $p > max (a,b)$ thế thì $a=a(p) \leq b=b(p)(mod p)$ , như vậy ta có $a \leq b$ , giả sử tiếp rằng $a < b$ . Lại thấy rằng $0 < b - a \leq  b$ và $(b-a)(p)=b(p)-a(p) \leq b(p)$ , vậy cặp $(a,b)$ thỏa mãn khi và chỉ khi $(b-a,b)$ thỏa mãn . Lùi liên tục như vậy đến khi thu được một bộ $(a,b)$ thỏa mãn $1 \leq a \leq \frac{b}{2}$ . Theo định lý Sylvester - Schur tồn tại một ước nguyên tố của $\binom{b}{a}$ là $u$ mà $u > a$ . Ta lại có $\binom{b}{a}=\frac{(b-a+1)...(b-1)b}{1.2...(a-1)a}$ là bội của $u$ , như thế sẽ có một số $k$ mà $u|b-k , 0 \leq k < a$ thế thì $b(u)=k < a = a(u)$ trái với giả thiết . 

Tham khảo thêm tại đây về định lý Sylvester - Schur . Bản thân tớ nghĩ có một cách chứng minh đơn giản hơn cho định lý này (SS) Tớ sẽ sưu tầm thêm chứng minh từ một số kết quả ở các tài liệu khác và đưa lên ngay khi có thể .

Bài 47 : Chứng minh rằng nếu các số $(a,b,n)$ thỏa mãn $\frac{a^{n}+b^{n}}{(ab)^{n-1}+1}$ là số nguyên thì nó là lũy thừa bậc $n$ của một số nguyên dương . ( Nguồn : Aops + Math.stackexchange )

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

[H S G S]

Lời giải bài 47:

Cho ai chưa biết lời giả cho trường hợp $n=2$ :

Nếu $a=b$ thì dễ dàng suy ra $a=b=1$. Giả sử $a<b$, xét dãy $\cdots, x_{-1}, x_{0}, x_{1}, x_{2}, \cdots$ thoả mãn:

$x_{0}=a, x_{1}=b, x_{i+1}=nx_{i} - x_{i-1}$ với $i=1,2, \cdots, n$

Suy ra $x_{i}^2+x_{i-1}^2=n(x_{i}x_{i-1}+1)$ $(1)$ và $x_{n}$ là dãy tăng chặt (Quy nạp)

 

Chọn $x_{k}$ là số hạng bé nhất dương trong dãy, vì dãy tăng nên phải có $x_{k-1}<=0$

Giả sử $x_{k-1}<0$ thay $i=k$ vào $(1)$ vô lý, vậy $x_{k-1}=0$ hay $x_{k}^2=\frac{a^2+b^2}{ab+1}$

 

Trong trường hợp $n>=3$ :

Nếu $a,b$ trái dấu thì sai đề nên ở đây chắc là $a,b$ nguyên dương.

 

Giả sử $a<b$, đặt $x=\frac{a^n+b^n}{(ab)^{n-1}+1}$ suy ra $a^n-x=(xa^{n-1}-b)b^{n-1}$ $(2)$

Nếu $x<a^n$ suy ra $xa^n-b=\frac{a^n-x}{b^{n-1}}<a$ (Do $a<b$) suy ra $xa^n<a+b$ hay $xa^{n-1}<\frac{b}{ax}+\frac{1}{x}<b$. Từ $(2)$ suy ra $a^n-x=(xa^{n-1}-b)b^{n-1}>=b^{n-1}>a^{2n-2}>a^{n}$ (Vô lý)

Nếu $x>a^n$ thì $x>x-a^{n}=(b-xa^{n-1})b^{n-1}<=b^{n-1}$ hay $b>ka^{n-1}>=k>b^{n-1}$ Vô lý

Vậy $x=a^n$ từ đó ta có đpcm.

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

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