Đến nội dung

Hình ảnh

Marathon số học Olympic

- - - - -

  • Please log in to reply
Chủ đề này có 191 trả lời

#41
bangbang1412

bangbang1412

    Độc cô cầu bại

  • Phó Quản lý Toán Cao cấp
  • 1667 Bài viết

Lời giải bài 14 : 

Đặt $\frac{p-1}{2}=h$ thế thì $(q^{h}-1)(q^{h}+1)=pK^{2}$

Đặt $d=gcd(q^{h}-1,q^{h}+1)$ thế thì $d|2$ mà cả hai số chẵn nên $d=2$

Hơn nữa để ý rằng $-p$ là số chính phương $modq$ nên $q^{h}+1$ là bội của $p$ ( cái này các bạn thuận nghịch bình phương sẽ thấy)

Nên ta có thể đặt $q^{h}-1=2a$ và $q^{h}+1=2pb$ với $(a,pb)=1$, Lại có thể đặt $(a,b)=(m^{2},n^{2})$

Hai phương trình trên tương đương $q^{h}=m^{2}+pn^{2}$ và $1=pn^{2}-m^{2}$

Nếu $n$ chẵn thì $m^{2}\equiv -1(mod4)$ nên $a+1\equiv 0(mod4)$ nên $2a\equiv -2(mod8)$ nên $q^{h}\equiv -1(mod8)$ hay $3^{h}\equiv -1(mod8)$

Nhưng nếu $h$ chẵn hay lẻ đều này đều không xảy ra vậy phải có $n$ lẻ và $m$ chẵn từ $1=pn^{2}-m^{2}$ thì $p\equiv 1(mod4)$

Đặt $h=2t$ thì ta có phân tích $q^{h}-1=(q^{t}-1)(q^{t}+1)=2m^{2}$

Lý luận tương tự $q^{t}-1=2c^{2},q^{t}+1=4d^{2}$ nên $q^{t}=(2d-1)(2d+1)$ , nhưng $q$ nguyên tố và $(2d-1,2d+1)=1,2d-1<2d+1$ nên $d=1$

Vậy $(p,q)=(5,3)$

Đề xuất bài 15  ( Nguồn : Aops) : Giả sử dãy $(a_{n})$ thỏa mãn $\sum_{d|n} a_{d}=2^{n}$ với mọi $n$ thì $a_{n}$ là bội của $n$ với mọi $n$ 


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

$$[\Psi_f(\mathbb{1}_{X_{\eta}}) ] = \sum_{\varnothing \neq J} (-1)^{\left|J \right|-1} [\mathrm{M}_{X_{\sigma},c}^{\vee}(\widetilde{D}_J^{\circ} \times_k \mathbf{G}_{m,k}^{\left|J \right|-1})] \in K_0(\mathbf{SH}_{\mathfrak{M},ct}(X_{\sigma})).$$


#42
Zaraki

Zaraki

    PQT

  • Phó Quản lý Toán Cao cấp
  • 4273 Bài viết

Đề xuất bài 15  ( Nguồn : Aops) : Giả sử dãy $(a_{n})$ thỏa mãn $\sum_{d|n} a_{d}=2^{n}$ với mọi $n$ thì $a_{n}$ là bội của $n$ với mọi $n$ 

Lời giải. Ta chứng minh theo quy nạp. Với $n=1$ thì $a_1=2$ thoả mãn.

Giả sử bài toán đúng đến $n=k-1$, tức với mọi $n \le k-1$ thì $n \mid a_n$. Ta sẽ chứng minh rằng $k \mid a_k$. Thật vậy, xét bất kì ước nguyên tố $p$ của $k$ thì đặt $k=p^lh$ với $p^l||n$. Khi đó, ta thấy rằng $$2^k=2^{p^lh}= \sum_{d|k}a_d= 2^{p^{l-1}h}+ \sum_{d \mid k, p^{l} \mid d}a_d = 2^{p^{l-1}h}+\sum_{d \mid k, p^l \mid d, d \ne k}a_d+a_k.$$

Theo giả thiết quy nạp, ta thấy rằng với mọi $d \ne k, d=p^lm \mid k$ thì $p^l \mid a_d$ suy ra $p^l \mid \sum_{d \mid k, p^l \mid d, d \ne k}a_d$. Ta cũng có theo bổ đề LTE với $2 \nmid p$ thì $$v_p \left( 2^{p^lh}-2^{p^{l-1}h} \right) = v_p \left( 2^p-2 \right)+v_p \left( p^{l-1}h \right) \ge l,$$ và $v_2 \left( 2^{p^lh}-2^{p^{l-1}h} \right) \ge p^{l-1}h \ge l$. Do đó từ đây ta suy ra $p^l \mid a_k$. Do cái này đúng với mọi ước nguyên tố $p$ của $k$ nên $k \mid a_k$.

Vậy với mọi $n$ thì $n \mid a_n$.    $\blacksquare$

 

Bài 16. [Peru TST 2008] Ta nói một số nguyên dương là số vui vẻ nếu nó có thể biểu diễn được dưới dạng $\frac{a^2b}{a-b}$ với $a>b>0$ là các số nguyên. Ta cũng nói rằng số nguyên dương $m$ là số ác quỷ nếu không tồn tại số vui vẻ $n$ thoả $\tau (n)=m$. Tìm tất cả các số vừa vui vẻ vừa ác quỷ.

Ở đây, $\tau (n)$ là số các ước nguyên dương của $n$.


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

Discovery is a child’s privilege. I mean the small child, the child who is not afraid to be wrong, to look silly, to not be serious, and to act differently from everyone else. He is also not afraid that the things he is interested in are in bad taste or turn out to be different from his expectations, from what they should be, or rather he is not afraid of what they actually are. He ignores the silent and flawless consensus that is part of the air we breathe – the consensus of all the people who are, or are reputed to be, reasonable.

 

Grothendieck, Récoltes et Semailles (“Crops and Seeds”). 


#43
IMOer

IMOer

    Hạ sĩ

  • Thành viên
  • 50 Bài viết

Lời giải bài 16:

Giả sử số nguyên dương $n$ vừa là số vui vẻ vừa là số ác quỷ và $n={{2}^{s}}\left( 2k+1 \right)$, với $k,s\in \mathbb{N}$.

Xét trường hợp $k\ge 1$:

Chọn $m={{2}^{{{2}^{s}}-1}}\cdot {{3}^{2k}}$, ta có: $\tau \left( m \right)={{2}^{s}}\left( 2k+1 \right)=n$.

Lại có: $m=\frac{{{\left( {{2}^{{{2}^{s-1}}-1}}\cdot {{3}^{k}} \right)}^{2}}\cdot \left( {{2}^{{{2}^{s-1}}}}\cdot {{3}^{k-1}} \right)}{\left( {{2}^{{{2}^{s-1}}-1}}\cdot {{3}^{k}} \right)-\left( {{2}^{{{2}^{s-1}}}}\cdot {{3}^{k-1}} \right)}$  nên $m$ là số vui vẻ, hay $n$ không phải là số ác quỷ.

Suy ra: $k=0$, hay $n={{2}^{k}}$.

Giả sử $n=\frac{{{a}^{2}}b}{a-b}$ với $a>b>0$.

Gọi $d=\gcd \left( a,\ b \right)$ và $a=d{{a}_{1}},\ b=d{{b}_{1}},\ \gcd \left( {{a}_{1}},\ {{b}_{1}} \right)=1$.

Khi đó ta có: $n\left( {{a}_{1}}-{{b}_{1}} \right)={{d}^{2}}a_{1}^{2}b_{1}^{2}\Leftrightarrow {{2}^{k}}\left( {{a}_{1}}-{{b}_{1}} \right)={{d}^{2}}a_{1}^{2}b_{1}^{2}$.

Vì ${{a}_{1}}>1,\ \gcd \left( {{a}_{1}},\ {{a}_{1}}-{{b}_{1}} \right)=1$ nên $2\ |\ {{a}_{1}}$, dẫn tới ${{a}_{1}}-{{b}_{1}}$ lẻ.

Xét số mũ của 2 ở 2 vế, ta sẽ nhận được $k$ phải là số chẵn.

Hay nếu $n$ là số vừa vui vẻ vừa ác quỷ thì $n$ phải có dạng ${{4}^{k}}$.

Ta sẽ chứng minh mọi số có dạng ${{4}^{k}}$ đều là số vui vẻ và số ác quỷ.

Thật vậy, ${{4}^{k}}=\frac{{{\left( {{2}^{k}} \right)}^{2}}\cdot {{2}^{k-1}}}{{{2}^{k}}-{{2}^{k-1}}}$ nên ${{4}^{k}}$ là số vui vẻ.

Lại có: $\tau \left( {{4}^{k}} \right)=2k+1$ là một số lẻ nên ${{4}^{k}}$ là số ác quỷ.

 

Bài 17: (Vietnam IMO training 2011)

Giả sử $P(x)$ là đa thức hệ số nguyên không có nghiệm bội. Chứng minh rằng với mọi $r$ nguyên dương, tồn tại $n$ nguyên dương sao cho trong phân tích $P(n)$ thành thừa số nguyên tố có ít nhất $r+1$ số nguyên tố tham gia với số mũ bằng 1.


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


#44
canhhoang30011999

canhhoang30011999

    Thiếu úy

  • Thành viên
  • 634 Bài viết

Lời giải bài 17.

ta có xét đa thức $P(x)$ hệ số nguyên bất kì thì tồn tại vô số nguyên tố $p_{k}$ sao cho tồn tại $n_{k}$ sao cho $P(n_{k})$ chia hết cho $p_{k}$

ta có $P(x)$ và $P'(x)$ nguyên tố cùng nhau nên tồn tại $g(x),f(x)$ hệ số nguyên và n nguyên sao cho

$P(x)g(x)+P'(x)f(x)=n$ với mọi $x$ nguyên

ta xét k số nguyên tố $p_{1}$,...,$p_{k}$ sao cho $p_{i}>n$ và tồn tại $n_{i}$ sao cho $P(n_{i})$ chia hết cho $p_{i}$ 

TH1 nếu $P(n_{i})$ không chia hết cho $p_{i}^{2}$ với mọi $1\leq i \leq k$ thì ta xét n sao cho $n\equiv n_{i} (mod p_{i}^{2})$ với mọi $1\leq i \leq k$ có n thỏa đề ra

TH2 nếu tồn tại $i$ sao cho $P(n_{i})$ chia hết cho $p_{i}^{2}$ thì ta xét

$P(n_{i}+p_{i})=\sum a_t(n_{i}+p_{i})^{k}\equiv P(n_{i})+p_{i}P'(n_{i})(mod p_{i}^{2})$

 nên $P(n_{i}+p_{i})$ chia hết cho $p_{i}$ nhưng không chia hết cho $p_{i}^{2}$ rồi làm như TH1

Bài 18.  giải pt nghiệm nguyên $x^{2}+5=y^{3}$

nguồn Các phương pháp giải toán qua các kì thi olympic 2014


Bài viết đã được chỉnh sửa nội dung bởi Zaraki: 29-05-2016 - 16:49
In đậm + tô đỏ


#45
I Love MC

I Love MC

    Đại úy

  • Thành viên nổi bật 2016
  • 1861 Bài viết

Lời giải bài 18 Giả sử phương trình $x^2=y^3-5$ có nghiệm nguyên $(x,y)$ 
Xét $y$ chẵn thì $x^2=y^3-5 \equiv 3 \pmod{8}$ (vô lí vì $x^2 \equiv 0,1,4 \pmod{8}$) 
Suy ra $y$  lẻ . 
Xét $y \equiv 3 \pmod{4}$ suy ra $x^2 \equiv 3^3-5 \equiv 2 \pmod{4}$ (vô lí) 
Xét $y \equiv 1 \pmod{4}$  nên ta đặt $y=4z+2$ với $z \in \mathbb{Z}$ 
 Khi đó ta có $x^2+4=(4z+1)^3-1=4z(16z^2+12z+3)$  
Suy ra $x^2 \equiv -4 \pmod{(16z^2+12z+3)}$ 
Sử dụng kí hiệu Jacobi : $1=(\frac{-4}{16z^2+12z+3})=(\frac{-1}{16z^2+12z+3})=-1$ (vì $16z^2+12z+3 \equiv 3 \pmod{4}$) vô lí 
Vậy phương trình đã cho vô nghiệm nguyên.

Bài 19  (Nguồn : Sưu tầm)  Cho $a,b,c$ là các số nguyên và $p$ là một số nguyên lẻ lớn hơn $3$. Chứng minh rằng nếu : 
$f(x)=ax^2+bx+c$ là số chính phương tại $\frac{p+5}{2}$ giá trị nguyên liên tiếp của $x$ thì $b^2 \equiv 4ac \pmod{p}$  
P/s : @Canhhoang...: Lần sâu anh nhớ đăng in đậm những bài đề xuất và bài giải . Chứ vậy thì khó nhìn lắm :( 
Em nghĩ anh chị khác cũng vậy 



#46
Zaraki

Zaraki

    PQT

  • Phó Quản lý Toán Cao cấp
  • 4273 Bài viết

Bài 19  (Nguồn : Sưu tầm)  Cho $a,b,c$ là các số nguyên và $p$ là một số nguyên lẻ lớn hơn $3$. Chứng minh rằng nếu : 
$f(x)=ax^2+bx+c$ là số chính phương tại $\frac{p+5}{2}$ giá trị nguyên liên tiếp của $x$ thì $b^2 \equiv 4ac \pmod{p}$  
P/s : @Canhhoang...: Lần sâu anh nhớ đăng in đậm những bài đề xuất và bài giải . Chứ vậy thì khó nhìn lắm :( 
Em nghĩ anh chị khác cũng vậy 

Lời giải. Ta sử dụng bổ đề sau.

Bổ đề. Với mọi số nguyên $a,b,c$ và số nguyên tố $p \nmid a$ thì tổng 

$$\sum_{x=0}^{p-1} \left( \frac{ax^2+bx+c}{p} \right)$$ bằng $- \left( \tfrac ap \right)$ nếu $p \nmid b^2-4ac$ và bằng $(p-1)\left( \tfrac ap \right)$ nếu $p \mid b^2-4ac$.

 

Ta gọi $m$ là số các số $0 \le x \le p$ sao cho $ax^2+bx+c$ là số chính phương modulo $p$, $n$ là số các số $x$ sao cho $ax^2+bx+c$ là số không chính phương modulo $p$. Ta để ý rằng có tối đa hai $0 \le x_1,x_2 \le p-1, x_1 \ne x_2$ sao cho $f(x_1) \equiv f(x_2) \equiv 0 \pmod{p}$. Kết hợp với giả thiết, ta suy ra có ít nhất $\frac{p+5}{2}-2=\frac{p+1}{2}$ số chính phương modulo $p$ hay $m \ge \frac{p+1}{2}$ (dấu bằng khi có đúng $2$ số $x$ sao cho $p \mid f(x)$).

Giả sử phản chứng rằng $p \nmid b^2-4ac$. Theo bổ đề, ta lại có $m-n= - \left( \tfrac ap \right) \le 1$. Mặt khác,  $m+n+a= p$ với $a \le 2$ là số các số $x$ sao cho $p \mid f(x)$. Từ đây ta dẫn đến $m \le \frac{p+1-a}{2}$. Kết hợp với điều trên ta dẫn đến $a=0$, mâu thuẫn với điều kiện xảy ra dấu bằng.

Vậy $p \mid b^2-4ac$.

 

Bài 20. [AoPS] Cho $a,b,c,d$ là các số nguyên dương sao cho $\gcd(abcd(a-b)(a-c)(a-d)(b-c)(b-d)(c-d),a+b+c+d)=1$. Chứng minh rằng nếu $a+b+c+d |a^n+b^n+c^n+d^n$ với mọi $4 \nmid n$ thì $a+b+c+d$ có thể biểu diễn thành tổng bình phương hai số nguyên dương (với hai số nguyên dương đó nguyên tố cùng nhau).


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

Discovery is a child’s privilege. I mean the small child, the child who is not afraid to be wrong, to look silly, to not be serious, and to act differently from everyone else. He is also not afraid that the things he is interested in are in bad taste or turn out to be different from his expectations, from what they should be, or rather he is not afraid of what they actually are. He ignores the silent and flawless consensus that is part of the air we breathe – the consensus of all the people who are, or are reputed to be, reasonable.

 

Grothendieck, Récoltes et Semailles (“Crops and Seeds”). 


#47
bangbang1412

bangbang1412

    Độc cô cầu bại

  • Phó Quản lý Toán Cao cấp
  • 1667 Bài viết

:mellow:  :mellow:  Không liên quan Toàn cho hỏi bài này ở AoPs ai làm chưa để còn biết mà làm , tớ sẽ xóa post này ngay . ( =)) ông định cho ngưng topic à )


$$[\Psi_f(\mathbb{1}_{X_{\eta}}) ] = \sum_{\varnothing \neq J} (-1)^{\left|J \right|-1} [\mathrm{M}_{X_{\sigma},c}^{\vee}(\widetilde{D}_J^{\circ} \times_k \mathbf{G}_{m,k}^{\left|J \right|-1})] \in K_0(\mathbf{SH}_{\mathfrak{M},ct}(X_{\sigma})).$$


#48
Ego

Ego

    Thượng sĩ

  • Điều hành viên OLYMPIC
  • 296 Bài viết

@bangbang1412: Đâu nhất thiết phải có người ở AoPS làm rồi, mình nghĩ cứ post, ít ra đây là một động lực để các bạn làm. Nếu topic bí 7 ngày mình sẽ đề xuất bài khác.

#bangbang1412 : Nói thế chứ bài này thấy toàn post lâu rồi nhìn khủng quá . Cậu để 4 ngày thôi 7 hơi lâu .


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


#49
Zaraki

Zaraki

    PQT

  • Phó Quản lý Toán Cao cấp
  • 4273 Bài viết

À, bài này có lời giải của mình rồi, cũng đã lâu rồi nên chưa kiểm lại lời giải. Nếu quá 4 ngày không có lời giải thì mình sẽ post lời giải của mình lên.


Discovery is a child’s privilege. I mean the small child, the child who is not afraid to be wrong, to look silly, to not be serious, and to act differently from everyone else. He is also not afraid that the things he is interested in are in bad taste or turn out to be different from his expectations, from what they should be, or rather he is not afraid of what they actually are. He ignores the silent and flawless consensus that is part of the air we breathe – the consensus of all the people who are, or are reputed to be, reasonable.

 

Grothendieck, Récoltes et Semailles (“Crops and Seeds”). 


#50
Ego

Ego

    Thượng sĩ

  • Điều hành viên OLYMPIC
  • 296 Bài viết

Lời giải bài 20. Từ điều kiện đầu cho ta các số trên phân biệt (lưu ý là $\gcd(0, a) = a$). Ta sẽ sử dụng các bổ đề sau:
Bổ đề. Một số tự nhiên $n$ lẻ có thể viết dưới dạng tổng hai số chính phương nguyên tố cùng nhau khi và chỉ khi mọi ước nguyên tố của $n$ đều có dạng $4k + 1$
i) Ta sẽ chứng minh $a + b + c + d$ lẻ. Giả sử ngược lại là nó chẵn, khi đó nếu có một số chẵn thì dễ thấy vô lí, xét 4 số đều lẻ, khi đó $\gcd(a - b, a + b + c + d) > 1$, vô lí nốt.

ii) Giả sử $p$ là một ước nguyên tố của $a + b + c + d$ ($p \neq 2$).

  1. Nếu $p > 3$ và $p \equiv 3\pmod{4}$ thì theo giả thiết $p\mid a + b + c + d\mid a^{p - 1} + b^{p - 1} + c^{p - 1} + d^{p - 1}$
    (lưu ý là $x^{p - 1} \equiv 0\quad\text{hoặc}\quad 1\pmod{p}$). Từ đây ta suy ra $p\mid 0\quad\text{hoặc}\quad 1 \quad\text{hoặc}\quad 2\quad\text{hoặc}\quad 3\quad \text{hoặc}\quad 4$. Dĩ nhiên chỉ có TH $p\mid 0$ là khả thi, tuy nhiên điều này chỉ xảy ra khi và chỉ khi $p\mid a, b, c, d$. Vô lí.
  2. Nếu $p = 3$ thì ta cũng xét tương tự, và lần này thì ta chỉ quan tâm $p\mid 3$ và $p\mid 0$ (cái này tương tự trên).
    Do đó ta chỉ cần quan tâm có đúng một số chia hết cho $3$, giả sử là $a$, khi đó $\gcd(a, a + b + c + d) \ge 3$, vô lí.

Từ đó mọi ước của $a + b + c + d$ là số dạng $4k + 1$, theo bổ đề ta có đpcm.


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


#51
Stoker

Stoker

    Binh nhì

  • Thành viên mới
  • 11 Bài viết

Lời giải bài 20. Từ điều kiện đầu cho ta các số trên phân biệt (lưu ý là $\gcd(0, a) = a$). Ta sẽ sử dụng các bổ đề sau:
Bổ đề. Một số tự nhiên $n$ lẻ có thể viết dưới dạng tổng hai số chính phương nguyên tố cùng nhau khi và chỉ khi mọi ước của $n$ đều có dạng $4k + 1$

Cho mình hỏi tại sao lại nguyên tố cùng nhau vậy?



#52
I Love MC

I Love MC

    Đại úy

  • Thành viên nổi bật 2016
  • 1861 Bài viết

Bổ đề. Một số tự nhiên $n$ lẻ có thể viết dưới dạng tổng hai số chính phương nguyên tố cùng nhau khi và chỉ khi mọi ước của $n$ đều có dạng $4k + 1$
 

Anh chứng minh bổ đề đó dùm em . Em biết đây là mở rộng định lí Fermat-Euler về tổng hai bình phương nhưng chưa tìm ra tài liệu chứng minh cái này 
Em nghĩ mọi người khi ghi bổ đề nào mới nên ghi cách chứng minh để mọi người cùng tham khảo để mở rộng tầm mắt .


Bài viết đã được chỉnh sửa nội dung bởi I Love MC: 29-05-2016 - 22:28


#53
Long Phi

Long Phi

    Binh nhất

  • Thành viên
  • 26 Bài viết

Trong bài chỉ dùng tới các ước nguyên tố có dạng $4k+1$ thôi, không phải mọi ước, cái này do $p=4k+1=a^{2}+b{2}$ và $(a^{2}+b^{2})(c^{2}+d^{2})=(ac+bd)^{2}+(ad-bc)^{2}$ 


Bài viết đã được chỉnh sửa nội dung bởi Long Phi: 29-05-2016 - 22:37


#54
bangbang1412

bangbang1412

    Độc cô cầu bại

  • Phó Quản lý Toán Cao cấp
  • 1667 Bài viết

Trong bài chỉ dùng tới các ước nguyên tố có dạng $4k+1$ thôi, không phải mọi ước, cái này do $p=4k+1=a^{2}+b{2}$ và $(a^{2}+b^{2})(c^{2}+d^{2})=(ac+bd)^{2}+(ad-bc)^{2}$ 

Chứng minh $ac+bd,ad-bc$ nguyên tố cùng nhau đi bạn .


$$[\Psi_f(\mathbb{1}_{X_{\eta}}) ] = \sum_{\varnothing \neq J} (-1)^{\left|J \right|-1} [\mathrm{M}_{X_{\sigma},c}^{\vee}(\widetilde{D}_J^{\circ} \times_k \mathbf{G}_{m,k}^{\left|J \right|-1})] \in K_0(\mathbf{SH}_{\mathfrak{M},ct}(X_{\sigma})).$$


#55
Long Phi

Long Phi

    Binh nhất

  • Thành viên
  • 26 Bài viết

Ta hoàn toàn có thể chọn $a,b,c,d$ sao cho $(a^{2}+b^{2},c^{2}+d^{2})=1$

khi đó giả sử  $(ac+bd),(ad-bc)$cùng chí hết cho $p$

Giả sử $a^{2}+b^{2}$ chia hết cho p

$=>(ad)^{2}-(bc)^{2}$ chia hết cho $p$

$=>a^{2}(c^{2}+d^{2})-c^{2}(a^{2}+b^{2})$ chia hết cho $p$

Mà $(a,b)=1$ (có thể coi là GTQN)

$=>c^{2}+d^{2}$ chia hết cho p

$=> p=1$



#56
canhhoang30011999

canhhoang30011999

    Thiếu úy

  • Thành viên
  • 634 Bài viết

Chứng minh $ac+bd,ad-bc$ nguyên tố cùng nhau đi bạn .

đầu tiên ta sẽ chứng minh $p^{t}=x^{2}+y^{2}$ với $(x,y)=1$ với $p=4k+1$

ta cm bằng quy nạp dễ thấy đúng với t=1

giả sử đúng đến t ta sẽ cm đúng với t+1

ta có $p^{t+1}=p^{t}.p=(x^{2}+y^{2})(a^{2}+b^{2})=(ax+by)^{2}+(ay-bx)^{2}=(ax-by)^{2}+(ay+bx)^{2}$

nên nếu $p^{t+1}$ không viết đc dưới dạng tổng của 2 số chính phương nguyên tố cùng nhau thì $p/ax+by,ay-bx,ax-by,ay+bx$

mà $a,b<p$ nên $p/x$,$p/y$ (vô lý)

vậy $p^{t}=x^{2}+y^{2}$ với $(x,y)=1$

ta có với n chỉ gồm các ước nguyên tố dạng $4k+1$ thì $n=(a_{1}^{2}+b_{1}^{2})....(a_{k}^{2}+b_{k}^{2})$ với $(a_{i},b_{i})=1,(a_{i}^{2}+b_{i}^{2})=1$

ta chỉ cần cm $(a^{2}+b^{2})(x^{2}+y^{2})$ phân tích đc thành 2 SCP nguyên tố cùng nhau rồi sau đó quy nạp là xong

hay là cm $(ax+by,ay-bx)=1$

gọi $(ax+by,ay-bx)=d$ thì $b(x^{2}+y^{2})$ chia hết cho p là ước nguyên tố của d

nếu b $b$ chia hết cho $p$ thì $ax$,$ay$ chia hết cho p nên vô lý

vậy $x^{2}+y^{2}$ chia hết cho p

tương tự $a^{2}+b^{2}$ chia hết cho p (vô lý) ta có đpcm 

p/s đang đánh dở mới nhận thông báo có bài mới nên nếu có giống bài trên mong mọi người thông cảm


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


#57
Long Phi

Long Phi

    Binh nhất

  • Thành viên
  • 26 Bài viết

Bài 21(IMO Shortlist 1984):Tìm $n$ thỏa $n=d_{6}^{2}+d_{7}^{2}-1$ với $d_{i}$ là ước dương thứ $i$ của $n$

Trong khi chờ bài của Ego các bạn thử sức với bài này xem



#58
bangbang1412

bangbang1412

    Độc cô cầu bại

  • Phó Quản lý Toán Cao cấp
  • 1667 Bài viết

Lời giải bài 21 : ( à bài này học trên tuyển rồi nên nhìn phát nhớ ngay  :D )

Hiển nhiên ta có $(d_{6},d_{7})=1$ và $d_{6}^{2}-1,d_{7}^{2}-1$ lần lượt là bội của $d_{7},d_{6}$

+ Nếu $d_{6}=ab,d_{7}=cd$ với $a>b>1,c>d>1$

Thế thì $1,a,b,c,d,bd$ là $6$ ước của $n$ mà $<d_{6}$

Từ đó $d_{6}$ hoặc $d_{7}$ có dạng $p^{r}$ với $r=1$ hoặc $r=2$

+ Nếu $d_{7}=p^{r}$ ta có $(d_{6}-1)(d_{6}+1)$ là bội $p^{r}$

   Ta có $d_{6}-1<d_{6}<d_{7},=> d_{7}|d_{6}+1$ ( để ý $p>2,d_{6}<d_{7},(d_{6}-1,d_{6}+1)=2$)

    Nhưng lại có $d_{6}+1\leq d_{7}$ nên $d_{6}+1=d_{7}$

+ Nếu $d_{6}=p^{r}$ thì $(d_{7}-1)(d_{7}+1)$ là bội $p^{r}$ nên có $s \in (1,-1)$ để mà $d_{7}+s=kd_{6}=kp^{r}$

   Lại có $k^{2}-1=k^{2}d_{6}^{2}-s^{2}-k^{2}(d_{6}^{2}-1)=(kd_{6}+s)(kd_{6}-s)-k^{2}(d_{6}^{2}-1)$ là bội $d_{7}=kd_{6}-s$

Nếu $k>1$ thế thì $k^{2} -1\geq kd_{6}-s \geq kd_{6}-1$ hay $k \geq d_{6}$

Từ đó $d_{7} \geq d_{6}^{2}-1$ , mà $d_{7}|d_{6}^{2}-1$ nên $d_{7}=d_{6}^{2}-1$

Nên $n = p^{2r}(p^{2r}-1)$

Nếu $p \geq 3 , r = 2$ ta có $1,p,p-1,p+1,p(p-1),\frac{p(p+1)}{2}$ là $6$ ước $<d_{6}=p^{2}$ vô lý

Do đó nếu $p=3,r=2$ thử trực tiếp không thỏa mãn

Vậy phải có $r=1$ thì $n=p^{2}(p^{2}-1)$ nên $d_{6}=p,d_{7}=p+1$ thế thì $p^{2}+p^{2}+2p+1=2p(p+1)$ khác $p^{2}(p^{2}-1)$

THế thì $k$ không thể lớn hơn $1$ nên $k=1=> d_{7}=d_{6}-s=d_{6}+1$ vậy ta luôn có $d_{7}=d_{6}+1$

Ta có các trường hợp $2p^{2}(p^{2}-1),2p^{2}(p^{2}+1),2p(p-1),2p(p+1)$ ( trường hợp đầu và cuối có nghiệm $144,1984$ đúng là số năm ra đề )

Đề xuất bài 22 : Tìm tất cả nghiệm nguyên của $x^{3}+2y^{3}+4z^{3}-6xyz=1$ ( nguồn : sưu tầm )


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

$$[\Psi_f(\mathbb{1}_{X_{\eta}}) ] = \sum_{\varnothing \neq J} (-1)^{\left|J \right|-1} [\mathrm{M}_{X_{\sigma},c}^{\vee}(\widetilde{D}_J^{\circ} \times_k \mathbf{G}_{m,k}^{\left|J \right|-1})] \in K_0(\mathbf{SH}_{\mathfrak{M},ct}(X_{\sigma})).$$


#59
IMOer

IMOer

    Hạ sĩ

  • Thành viên
  • 50 Bài viết

Lời giải bài 22:

Đặt $\alpha =\sqrt[3]{2}$ và $\omega ={{e}^{\frac{2\pi i}{3}}}$.

Phương trình đã cho tương đương với:

$\left( x+y\alpha +z{{\alpha }^{2}} \right)\left( x+y\alpha \omega +z{{\alpha }^{2}}{{\omega }^{2}} \right)\left( x+y\alpha {{\omega }^{2}}+z{{\alpha }^{2}}\omega  \right)=1\ \ \ \ \ (*)$

Dễ thấy $\;$ là nghiệm của $\left( * \right)$ và các bộ số $\left( {{x}_{n}},{{y}_{n}},{{z}_{n}} \right)$ thoả mãn ${{x}_{n}}+{{y}_{n}}\alpha +{{z}_{n}}{{\alpha }^{2}}={{\left( {{x}_{1}}+{{y}_{1}}\alpha +{{z}_{1}}{{\alpha }^{2}} \right)}^{n}}={{\left( 1+\alpha +{{\alpha }^{2}} \right)}^{n}}$  đều là nghiệm của $\left( * \right)$ với mọi $n\in \mathbb{Z}$.

Ta sẽ chứng minh mọi nghiệm của (*) có dạng $\left( {{x}_{n}},\ {{y}_{n}},\ {{z}_{n}} \right)$.

Với $\left( x,y,z \right)$ là nghiệm của (*) ta sẽ có: $x+y\alpha +z{{\alpha }^{2}}>0$ nên tồn tại duy nhất số nguyên $n$ sao cho ${{\left( 1+\alpha +{{\alpha }^{2}} \right)}^{n}}\le x+y\alpha +z{{\alpha }^{2}}<{{\left( 1+\alpha +{{\alpha }^{2}} \right)}^{n+1}}$.

Khi đó $\left( a,b,c \right)\in {{\mathbb{Z}}^{3}}$ thoả mãn $a+b\alpha +c{{\alpha }^{2}}=\left( x+y\alpha +z{{\alpha }^{2}} \right){{\left( 1+\alpha +{{\alpha }^{2}} \right)}^{-n}}$ cũng là nghiệm của (*) và khi đó: $1\le a+b\alpha +c{{\alpha }^{2}}<1+\alpha +{{\alpha }^{2}}$.

Ta có:
$ 1\ge {{\left( a+b\alpha +c{{\alpha }^{2}} \right)}^{-1}}=\left( {{a}^{2}}-bc \right)+\left( 2{{c}^{2}}-ab \right)\alpha +\left( {{b}^{2}}-ac \right){{\alpha }^{2}} =\frac{1}{2}\left[ {{\left( a-b\alpha  \right)}^{2}}+{{\left( b\alpha -c{{\alpha }^{2}} \right)}^{2}}+{{\left( c{{\alpha }^{2}}-a \right)}^{2}} \right]$

Nên suy ra: $\left| a-b\alpha  \right|\le \sqrt{2};\ \left| b\alpha -c{{\alpha }^{2}} \right|\le \sqrt{2};\ \left| c{{\alpha }^{2}}-a \right|\le \sqrt{2}$.

Nếu $c\ge 1$ thì ta có: $a\ge c{{\alpha }^{2}}-\sqrt{2}>0$ và $b>c\alpha -\frac{\sqrt{2}}{\alpha }>0$ nên $a+b\alpha +c{{\alpha }^{2}}\ge 1+\alpha +{{\alpha }^{2}}$, vô lý.

Nếu $c\le -1$, tương tự ta có: $a+b\alpha +c{{\alpha }^{2}}\le -\left( 1+\alpha +{{\alpha }^{2}} \right)$, vô lý.

Vậy $c=0$, suy ra: $\left| a-b\alpha  \right|\le \sqrt{2};\ \left| b\alpha  \right|\le \sqrt{2};\ \left| a \right|\le \sqrt{2}$. Kết hợp với ${{a}^{3}}+2{{b}^{3}}+4{{c}^{3}}-6abc=1$ thì ta chỉ nhận được 1 bộ số thoả mãn là $\left( a,\ b,\ c \right)=\left( 1,\ 0,\ 0 \right)$.

Từ đó suy ra: $x+y\alpha +z{{\alpha }^{2}}={{\left( 1+\alpha +{{\alpha }^{2}} \right)}^{n}}$, điều phải chứng minh.

 

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

Cho $n$ là một số nguyên dương. Gọi $a_n$ là số các số tự nhiên $k$ sao cho $\binom{n}{k}\equiv 1 \pmod{3}$ và $b_n$ là số các số tự nhiên $k$ sao cho $\binom{n}{k}\equiv 2 \pmod{3}$.

Chứng minh rằng: $a_n-b_n$ là một luỹ thừa của 2.



#60
Ego

Ego

    Thượng sĩ

  • Điều hành viên OLYMPIC
  • 296 Bài viết

Lời giải bài 23. Biểu diễn $n$ dưới dạng cơ số $3$ là $(x_{1}x_{2}\cdots x_{k})_{3}$ với $x_{i} \in \{0, 1, 2\}$ và $x_{1} > 0$. Quy ước $\dbinom{m}{n} = 0$ nếu $n > m$
Xét một số $k$ biểu diễn dưới dạng cơ số $3$ là $(y_{1}y_{2}\cdots y_{k})_{3}$
Áp dụng định lý Lucas, $\dbinom{n}{k} \equiv \prod_{i = 1}^{k}\dbinom{x_{i}}{y_{i}}\pmod{3}$
Lúc này để ý là $\dbinom{0}{0} = \dbinom{1}{0} = \dbinom{1}{1} = \dbinom{2}{0} = \dbinom{2}{2} = 1$ và $\dbinom{2}{1} = 2$
Gọi $u, v, w$ lần lượt là số số $0, 1, 2$ trong biểu diễn cơ số $3$ của $n$.

  1. Để $\dbinom{n}{k}\equiv 1\pmod{3}$ thì tương ứng các vị trí $0$ của $n$ trong cơ số $3$ thì ta cũng chọn tương ứng $0$ ở vị trí $k$ (do đó ta không quan tâm điều này). Ở các vị trí $1$ ta cũng phải chọn $0$ hoặc $1$. Ở các vị trí $2$ ta có hai lựa chọn:
    i) Tương ứng ở $k$ ta sẽ thay số $2$ hoặc số $0$
    ii) Tương ứng ở $k$ ta thay số $1$, tuy nhiên số số lần thay số $1$ này là số chẵn vì $2^{2k}\equiv 1\pmod{3}$.
    Tóm lại ta sẽ có số cách chọn là $a_{n} = 2^{v}\times\sum_{i = 0}^{\left\lfloor \frac{w}{2}\right\rfloor}\dbinom{w}{2i}2^{w - 2i} = 2^{v}\times\sum_{i = 0}^{\left\lfloor \frac{w}{2}\right\rfloor}\dbinom{w}{2i}2^{w - 2i}(-1)^{2i}$
  2. Để $\dbinom{n}{k} \equiv 2\pmod{3}$ thì cũng tương tự, tuy nhiên số lần thay số $1$ trong $k$ ở các vị trí tương ứng $2$ trong $n$ phải là số lẻ.
    Số cách chọn sẽ là $b_{n} = 2^{v}\times \sum_{i = 0}^{\left\lfloor \frac{w}{2}\right\rfloor}\dbinom{w}{2i + 1}2^{w - 2i - 1} \implies -b_{n} = 2^{v}\times \sum_{i = 0}^{\left\lfloor \frac{w}{2}\right\rfloor}\dbinom{w}{2i + 1}2^{w - 2i - 1}(-1)^{2i + 1}$

Cộng lại ta thu được $a_{n} - b_{n} = 2^{v}\sum_{i = 0}^{w}\dbinom{w}{i}2^{w - i}(-1)^{i} = 2^{v}(2 - 1)^{w} = 2^{v}$. Bài toán kết thúc.

Bài toán 24. (thầy Trần Nam Dũng) Cho $n$ là số tự nhiên. Chứng minh rằng nếu phương trình $x^{2} + xy - y^{2} = n$ có nghiệm nguyên thì nó có vô số nghiệm nguyên.

Hi

Lời nhắn tới bạn canhhoang30111999


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





0 người đang xem chủ đề

0 thành viên, 0 khách, 0 thành viên ẩn danh