Đế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

#81
I Love MC

I Love MC

    Đại úy

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

Nếu đã phân tích được thế kia thì chọn modulo có khó khăn gì đâu em. Cho anh hỏi em biến đổi biểu thức kia ntn thế?   quá khủng

Biểu thức quen thuộc thôi anh 
$a^4+a^2+1=(a^2+a+1)(a^2-a+1)$ 



#82
I Love MC

I Love MC

    Đại úy

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

Cách chứng minh bổ đề của anh IMOer


Bài viết đã được chỉnh sửa nội dung bởi viet nam in my heart: 31-05-2016 - 12:59
Sửa latex.


#83
Zaraki

Zaraki

    PQT

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

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

Tìm tất cả các số nguyên dương $m\equiv 2\ (\bmod{4})$ sao cho tồn tại các số tự nhiên $n, k$ và số nguyên tố $p$ sao cho $\dfrac{m^{2^n-1}-1}{m-1}=m^n+p^k$.

Lời giải. Từ phương trình ta suy ra $n \ge 2$ do đó từ $m \equiv 2 \pmod{4}$ ta dẫn đến $p^k \equiv 3 \pmod{4}$ suy ra $p \equiv 3 \pmod{4}$. Phương trình tương đương với $$m^{2^n}-1+(1-m) \left( m^{n+1}+1 \right) = m(m-1)p^k.$$

Nếu ta đặt $n+1=2^l(2h+1)$ thì $l<n$ suy ra $m^{2^l}+1 \mid m^{2^n}-1$ và ta cũng có $m^{2^l}+1 \mid m^{n+1}+1$ suy ra $m^{2^l}+1 \mid m(m-1)p^k$. Do $\gcd \left( m(m-1), m^{2^l}+1 \right)=1$ nên $m^{2^l}+1 \mid p^k$. 

Nếu $l \ge 1$ thì ta dẫn đến luôn tồn tại số nguyên tố $q \equiv 1 \pmod{4}$ là ước của $m^{2^l}+1$, mâu thuẫn. Vậy $l=0$ hay $m+1 \mid p^k$. Vậy $m=p^l-1$ với $2 \nmid l$.

 

Ta chứng minh với mỗi $m=p^l-1$ tồn tại $n,k,p$ thoả mãn. Thật vậy, ta chỉ việc chọn $n=2,k=l$ là xong.

 

Bài 33. Cho trước số nguyên dương $k$. Chứng minh rằng với mọi số nguyên tố $p$ thoả $\gcd (k,p)=1$ thì với mỗi số nguyên dương $n$, luôn tồn tại hai số nguyên dương $x,y$  sao cho $p^n \mid x^2-ky^2+1$.

Nguồn. Đề đề nghị cho VMEO IV.


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”). 


#84
Ego

Ego

    Thượng sĩ

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

Hình như bài toán có vấn đề với $k = 3$, khi này với $p = 2$ thì $p^{n}\mid x^{2} - 3y^{2} + 1$ chỉ đúng với $n = 1$. Nếu với $p$ lẻ thì đây là lời giải của mình.
Lời giải bài 33. Ta sẽ chứng minh bằng quy nạp

i) Ta sẽ chứng minh tồn tại $x_{1}, y_{1}$ để $p\mid x_{1}^{2} - ky_{1}^{2} + 1$. Cái này có thể dùng định lý Cauchy - Davenport để chứng minh. Tuy nhiên ta có thể làm dễ hơn bằng cách:

a) Cho $a, b$ là hai số tự nhiên không vượt quá $\frac{p - 1}{2}$, khi đó $a^{2} \equiv b^{2} \pmod{p} \iff a = b$
b) Như (a) thì ta chỉ việc cho $(x_{1}, y_{1}) \in \left\{0, 1, \cdots \frac{p - 1}{2}\right\}^{2}$ thì $x_{1}^{2} + 1$ có thể nhận $\frac{p + 1}{2}$ đồng dư khác nhau; và $ky^{2}$ cũng nhận đúng $\frac{p + 1}{2}$ đồng dư khác nhau do $\gcd(k, p) = 1$. Để ý là chúng chỉ có thể có tối đa $p$ đồng dư modulo $p$ nên ắt hẳn sẽ có hai phần tử bằng nhau, tức là $x_{1}^{2} + 1 \equiv ky_{1}^{2}$

ii) Giả sử $p^{n}\mid x_{n}^{2} - ky_{n}^{2} + 1$ và $p^{n + 1}\nmid x_{n}^{2} - ky_{n}^{2} + 1$ (để ý là $n \ge 1$ nên $2n \ge n + 1$), ta có thể giả sử đoạn sau vì nếu không có nó thì mệnh đề cũng đúng với $n + 1$ rồi, không cần xét. Đặt $x_{n + 1} = x_{n} + p^{n}u$ và $y_{n + 1} = y_{n} + p^{n}v$ và $P_{n} = x_{n}^{2} - ky_{n}^{2} + 1$ cho thuận tiện
Lúc này ta muốn tìm $u, v$ thỏa mãn $p^{n + 1}\mid x_{n + 1}^{2} - ky_{n + 1}^{2} + 1$.
Ta có $P_{n + 1} = x_{n + 1}^{2} - ky_{n + 1}^{2} + 1 = P_{n} + p^{2n}(u^{2} - kv^{2}) + 2x_{n}p^{n}u - 2ky_{n}p^{n}v$
Để thỏa mãn điều ta cần thì $p^{n + 1}\mid P_{n} + 2p^{n}(x_{n}u - ky_{n}v) \iff p\mid \frac{P_{n}}{p^{n}} + 2x_{n}u - 2ky_{n}v$
Để ý là trong hai số $x_{n}, y_{n}$ ắt hẳn có một số không chia hết cho $p$, nếu số đó là $x_{n}$ thì ta chọn tùy ý $v$ và chọn $u$ thỏa mãn $u \equiv \left(2ky_{n}v - \frac{P_{n}}{p^{n}}\right)(2x_{n})^{-1}$, tương tự nếu số đó là $y_{n}$ thì ta chọn tùy ý $u$ và chọn $v$ thỏa mãn $v \equiv \left(2x_{n}u + \frac{P_{n}}{p^{n}}\right)(2ky_{n})^{-1}$, do $\gcd(k, p) = 1$.
Bài toán 34. (Gabriel Dospinescu) Ký hiệu $\sigma(n)$ là tổng các ước nguyên dương của $n$. Chứng minh rằng với mọi $n > 1$ thì đẳng thức sau đúng: $$\sum_{k = 0}^{n - 1}(-1)^{k}(2k + 1)\sigma\left(\frac{n^{2} + n}{2} - \frac{k^{2} + k}{2}\right) = (-1)^{n - 1}\frac{n(n + 1)(2n + 1)}{6}$$


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


#85
IMOer

IMOer

    Hạ sĩ

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

Bài toán 34. (Gabriel Dospinescu) Ký hiệu $\sigma(n)$ là tổng các ước nguyên dương của $n$. Chứng minh rằng với mọi $n > 1$ thì đẳng thức sau đúng: $$\sum_{k = 0}^{n - 1}(-1)^{k}(2k + 1)\sigma\left(\frac{n^{2} + n}{2} - \frac{k^{2} + k}{2}\right) = (-1)^{n - 1}\frac{n(n + 1)(2n + 1)}{6}$$

Bài này xếp vào mục giải tích thì hợp hơn.



#86
bangbang1412

bangbang1412

    Độc cô cầu bại

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

Bài 34 : 

Đúng như anh IMOer nói bài này mình nghĩ Ego nên ném vào mục giải tích , đây là lời giải theo giải tích mà mình biết

Trước tiên với $|x|<1$ ta có đẳng thức sau 

                                                $$\prod_{n=1}^{\infty}(1-x^{n})^{3}=\sum_{n=0}^{\infty}(-1)^{n}(2n+1).x^{\frac{1}{2}n(n+1)}$$

Xét chuỗi :

$$\sum_{n=1}^{\infty} \sigma(n)x^{n} = \sum_{n=1}^{\infty} \sum_{m|n}mx^{n} = \sum_{n=1}^{\infty} \sum_{m=1}^{\infty} mx^{mn} = \sum_{m=1}^{\infty}\frac{mx^{m}}{1-x^{m}} = -x \frac{d}{dx}\sum_{m=1}^{\infty}log(1-x^{m})=-x\frac{d}{dx} log \prod_{m=1}^{\infty}(1-x^{m})=-x\frac{\frac{d}{dx} \prod_{m=1}^{\infty}(1-x^{m})}{\prod_{m=1}^{\infty}(1-x^{m})}$$

Lấy tích

$$\sum_{n=1}^{\infty} \sigma(n)x^{n}.\sum_{n=0}^{\infty}(-1)^{n}(2n+1)x^{\frac{1}{2}n(n+1)}=-x \prod_{m=1}^{\infty}(1-x^{m})^{2} \frac{d}{dx}\prod_{m=1}^{\infty}(1-x^{m})=\frac{-x}{3}\frac{d}{dx}\prod_{m=1}^{\infty}(1-x^{m})^{3}=\frac{-1}{6}\sum_{n=0}^{\infty}(-1)^{n}n(n+1)(2n+1)x^{\frac{1}{2}n(n+1)}$$

Đồng nhất hệ số của $x^{\frac{1}{2}n(n+1)}$ ta có dpcm 

Không giỏi tổng hàm như đề xuất một bài 

Bài 35 : Gọi $n>1$ nguyên dương , $f(n)$ là số các số nguyên nhỏ hơn $n$ và nguyên tố cùng nhau với $n$ , gọi $a_{1},a_{2},...a_{f(n)}$ là các số thuộc $[n]$ và nguyên tồ cùng nhau với $n$ . Giả sử tất cả các ước nguyên tố của $n$ là $p_{1},p_{2},...p_{k}$ Chứng minh đẳng thức sau :

                                                   $$\sum_{i=1}^{f(n)}a_{i}^{2} = \frac{f(n)}{6}(2n^{2}+(-1)^{k}\prod_{i=1}^{k}p_{i})$$


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

$$[\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})).$$


#87
IMOer

IMOer

    Hạ sĩ

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

Bài 35 : Gọi $n>1$ nguyên dương , $f(n)$ là số các số nguyên nhỏ hơn $n$ và nguyên tố cùng nhau với $n$ , gọi $a_{1},a_{2},...a_{f(n)}$ là các số thuộc $[n]$ và nguyên tồ cùng nhau với $n$ . Giả sử tất cả các ước nguyên tố của $n$ là $p_{1},p_{2},...p_{k}$ Chứng minh đẳng thức sau :

                                        $\sum_{i=1}^{f(n)}a_{i}^{2} = \frac{f(n)}{6}(2n^{2}+(-1)^{k}\prod_{i=1}^{k}p_{i})$

Đây cũng là một bài thuộc Giải tích số học thì hợp lý hơn.

Lời giải sử dụng một số kết quả sau:

1. Công thức nghịch đảo Möbius:

\[f(n)=\sum_{d|n}g(d) \Leftrightarrow g(n)=\sum_{d|n} f(d)\mu\left(\dfrac{n}{d}\right)\]

với $\mu(n)$ là hàm Möbius.

2. $\displaystyle \sum_{d|n}\mu(d)=\sum_{d|n}\mu\left(\dfrac{n}{d}\right)=0$ khi $n>1$

3. $\displaystyle \sum_{d|n} d\mu\left(\dfrac{n}{d}\right)=\varphi(n)$

4. $\displaystyle \sum_{d|n} d\mu(d)=\prod_{\begin{array}{c}p\in\wp\\p|n\end{array}}(1-p)$

5. $\displaystyle \sum_{d|n} \dfrac{\varphi_k(d)}{d^k}=\dfrac{1^k+2^k+...+n^k}{n^k}$ với $\displaystyle \varphi_k(n)=\sum_{\begin{array}{c}d=1\\(n,d)=1\end{array}}^n d^k$

 

Sử dụng các kết quả trên ta có:

\[\begin{array}{l}\dfrac{\varphi_2(n)}{n^2}&=\displaystyle\sum_{d|n}\dfrac{1^2+2^2+...+d^2}{d^2}\mu\left(\dfrac{n}{d}\right)\\&=\displaystyle\sum_{d|n}\dfrac{d(d+1)(2d+1)}{d^2}\mu\left(\dfrac{n}{d}\right)\\&=\dfrac{1}{6}\left(\displaystyle \sum_{d|n}2d\mu\left(\dfrac{n}{d}\right)+\sum_{d|n}\dfrac{1}{d}\mu\left(\dfrac{n}{d}\right)\right)\\&\displaystyle=\dfrac{1}{3}\varphi(n)+\dfrac{1}{6}\sum_{d|n}\dfrac{d}{n}\mu(d)\\&\displaystyle=\dfrac{1}{3}\varphi(n)+\dfrac{1}{6n}\prod_{\begin{array}{c}p\in\wp\\p|n\end{array}}(1-p)\end{array}\]
Từ đây dễ dàng nhận được điều cần chứng minh.
 
Mình xin phép đề xuất 1 bài Số học "nguyên chất" để tiếp tục topic và cũng mong các bạn cũng có thể học được nhiều hơn từ các bài toán thuộc topic này. Cứ "cao cấp" mãi như bài 34 hay 35 cũng nản.
Bài 36: (Nguồn: Sưu tầm)
Tìm tất cả các số chính phương sao cho biểu diễn của nó trong cơ số 3 chỉ chứa chữ số 1.

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


#88
bangbang1412

bangbang1412

    Độc cô cầu bại

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

 

Đây cũng là một bài thuộc Giải tích số học thì hợp lý hơn.

 

 

Lời giải của anh thì em không có ý kiến gì nhưng nó có thể sơ cấp hơn chỉ dùng công thức tập hợp . Còn rõ ràng lời giải này ngắn gọn và hay . Nhưng dù sao vẫn khuyến khích mọi người học cách này . 

P/s : Theo em nghĩ có giải tích số học cũng hay vì nó khá đẹp và cũng dễ hiểu , nếu học lên cao cái này cũng tốt . Đây là ý kiến cá nhân mong m.n tập trung vào topic và không delete post này .


Bài viết đã được chỉnh sửa nội dung bởi bangbang1412: 31-05-2016 - 22: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})).$$


#89
Ego

Ego

    Thượng sĩ

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

Cá nhân em nghĩ thì em thích phần này, hình như nó là analytic number theory. Nhưng tính ra cũng hơi cao cấp :P. Thỉnh thoảng ta cũng nên chêm vào cho vui :3 =))
Bài 36 em có hiểu sai không nhỉ, biểu diễn $n = \sum_{i = 0}^{k}3^{i} = \frac{3^{k + 1} - 1}{2}$.


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


#90
IMOer

IMOer

    Hạ sĩ

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

Cá nhân em nghĩ thì em thích phần này, hình như nó là analytic number theory. Nhưng tính ra cũng hơi cao cấp :P. Thỉnh thoảng ta cũng nên chêm vào cho vui :3 =))
Bài 36 em có hiểu sai không nhỉ, biểu diễn $n = \sum_{i = 0}^{k}3^{i} = \frac{3^{k + 1} - 1}{2}$.

 

Hình như bài $36$ của anh có vấn đề và nếu đúng nó không hợp với tiêu chí topic lắm . 

P/s : Điểm after hôm nay  :D

Về phần số học giải tích mình chia sẻ một tài liệu và mọi người search gg theo hai cụm từ sau : " AIANT.pdf " hoặc " Introduction to analytic number theory hardy  "

 

Xin lỗi các bạn, mình đã sửa lại đề đúng.



#91
canhhoang30011999

canhhoang30011999

    Thiếu úy

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

Lời giải của anh thì em không có ý kiến gì nhưng nó có thể sơ cấp hơn chỉ dùng công thức tập hợp . Còn rõ ràng lời giải này ngắn gọn và hay . Nhưng dù sao vẫn khuyến khích mọi người học cách này . 

P/s : Theo em nghĩ có giải tích số học cũng hay vì nó khá đẹp và cũng dễ hiểu , nếu học lên cao cái này cũng tốt . Đây là ý kiến cá nhân mong m.n tập trung vào topic và không delete post này .

Bằng có thể đăng cách kia không để mọi người tham khảo?



#92
bangbang1412

bangbang1412

    Độc cô cầu bại

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

From a book but i forgot it , very lucky because i having retained this soluntion  :D  gg dịch oai tý thôi giờ vào vấn đề chính , lời giải hay nhất , đơn giản và đúng nhất IMOer đã trình bày 

Trong bài này sẽ thay $f(n)$ ở đề thành $\phi(n)$

Trước hết ta có công thức sau $\left | \bigcup_{i=1}^{n}A_{i} \right |=\sum _{I \in [n],I\not\equiv 0}(-1)^{\left | I \right |+1}\left | \bigcap_{i \in I}A_{i} \right |$

Với $I$ là tập chỉ số nào đó

Nếu một tập $A= \bigcup_{i=1}^{n} A_{i}$ và một hàm số $f : A \to R$ và $f( O )\neq 0 , f(B)= \sum_{x \in B}f(x) (B \in A)$

Thì $f(A) = \sum_{I \neq O} (-1)^{\left | |I|+1 \right|} f( \bigcap_{i\in I}A_{i})$

Đặt $f(x)=x^{2},f(A)=\sum_{x \in A} f(x) = \sum_{x \in A} x^{2}$

Dĩ nhiên $f(O) \neq 0$ với $1 \leq i \leq k$ gọi $A_{i}$ là tập mà mỗi phần tử thuộc $A_{i}$ đều chia hết cho $p_{i}$ và $A_{i}$ là con của $A$

Thế thì $f(A) = \sum_{i=1}^{n} i^{2} = \frac{n^{3}}{2} + \frac{n^{2}}{2} + \frac{n}{6}$

Ta có : 

$f(A_{i}) = p_{i}^{2}+(2p_{i})^{2}+...+ (\frac{n}{p_{i}}p_{i})^{2}= p_{i}^{2} (\frac{1}{3}(\frac{n}{p_{i}})^{3}+\frac{1}{2}(\frac{n}{p_{i}})^{2}+\frac{1}{6}\frac{n}{p_{i}})$

Và $f(A_{i}\cap A_{j})=(p_{i}p_{j})^{2}(\frac{1}{3}(\frac{n}{p_{i}p_{j}})^{3}+\frac{1}{2}(\frac{n}{p_{i}p_{j}})^{2}+\frac{1}{6}\frac{n}{p_{i}p_{j}})$

Thế thì ta có 

$\sum_{i=1}^{\phi(n)}a_{i}^{2} = f(A) - f(\bigcup_{i=1}^{k}A_{i}) = \frac{n^{3}}{3}+\frac{n^{2}}{2}+\frac{n}{6}- \sum_{I \neq O}(-1)^{|I|+1}f(\bigcap_{i \in I}A_{i})$

Ta tính nốt cái tổng kia 

$\sum_{I \neq O} (-1)^{|I|} f(\bigcap_{i \in I}A_{i}) = \sum_{I \in [n] , I \neq O} (-1)^{|I|} \prod_{i \in I}p_{i}S_{I}$

Trong đó $S_{I} = \frac{1}{3}(n\prod_{i \in I}\frac{1}{p_{i}})^{3}+\frac{1}{2}(n\prod_{i \in I}\frac{1}{p_{i}})^{2}+\frac{n}{6}\prod_{i \in I}\frac{1}{p_{i}}$

Nên ta có 

$\sum_{i=1}^{\phi(n)}a_{i}^{2}=\frac{n^{3}}{3}(1+\sum_{I\in [n],I \neq O} \prod_{i\in I} (\frac{-1}{p_{i}}))+n^{2}(1+\sum_{I \in [n],I \neq O} (-1)^{|I|})+\frac{n}{6}(1+ \sum_{I \in [n],I\neq O} \prod_{i \in I} (-p_{i}))=\frac{n^{3}}{3} \prod_{i=1}^{k}(1-\frac{1}{p_{i}})+\frac{n^{2}}{2}\prod_{i=1}^{k} (1-1)+\frac{n}{6}\prod_{i=1}^{k}(1-p_{i})=\frac{n^{2}}{3} \phi(n) + \phi(n) \prod_{i=1}^{k} \frac{-p_{i}}{6} = \phi(n)\frac{1}{6}(2n^{2}+(-1)^{k}\prod_{i=1}^{k}p_{i})$

Từ đó có đpcm , ở đây $O$ nghĩa là rỗng nhé . Mình bị vấn đề với latex đang tìm hiểu . 


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

$$[\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})).$$


#93
Zaraki

Zaraki

    PQT

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

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

Tìm tất cả các số chính phương sao cho biểu diễn của nó trong cơ số 3 chỉ chứa chữ số 1.

 

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$.

 

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

 

Bài 37. [AoPS] Với mỗi số nguyên $r$, chứng minh rằng tồn tại số tự nhiên $n_r$ sao cho với mọi số nguyên $n>n_r$ tồn tại ít nhất một số nguyên dương $k$ thoả mãn $1 \le k \le n-1$ và $p^r$ là ước của $\binom{n}{k}$ với $p$ là số nguyên tố nào đó.


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

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”). 


#94
canhhoang30011999

canhhoang30011999

    Thiếu úy

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

bài 37 mình xin sửa lại như sau

ta sẽ cm $n_{r}=6^{2r}$ thỏa mãn

thật vậy xét$ n>6^{2r}$

ta có $C^{k}_{n}=\frac{k+1}{n+1}C^{k+1}_{n+1}$ 

nếu $n+1$ không chia hết cho $6^{r}$ thì chọn $k=6^{2r}-1$ ta có $C^{k}_{n}$ chia hết cho $2^{r}$
nếu $n+1$ chia hết cho $6^{r}$ thì xét $n+1= p_{1}^{a_1}p_{2}^{a_2}...p_{k}^{a_k}$ với $p_i$ là các số nguyên tố liên tiếp 
ta có $p_{n+1}<p_{1}p_{2}...p_{n}$ (phản chứng rồi xét $p_{1}p_{2}...p_{n}-1$)
 xét $a_{i}$ là số bé nhất sao cho $a_{i}<r$ lúc đó xét $k+1= p_{i}^{r+a_{i}}<p_{1}^{r}p_{2}^{r}..p_{i-1}^{r}p_{i}^{a_{i}}<n+1$ ta có $C^{k}_{n}$ chia hết cho $p_{i}^{r}$
Vậy ta có đpcm
p/s xho mình hỏi làm sao đánh nhị thức dạng quốc tế bằng Latex vậy
Bài 38 cho p là 1 số nguyên tố. Chứng minh rằng tồn tại 1 số nguyên tố q sao cho với mọi số nguyên dương n không chia hết cho q thì $n^{p}-p$ không chia hết cho $q$ (bài này kinh điển)

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


#95
Zaraki

Zaraki

    PQT

  • Phó Quản lý Toán Cao cấp
  • 4273 Bài viết
nếu $n+1$ chia hết cho $p^{r}$ chọn k=2 ta có $C^{2}_{n}=\frac{n(n+1)}{2}$ chia hết cho $p^{r}$
vậy ta có đpcm
p/s xho mình hỏi làm sao đánh nhị thức dạng quốc tế bằng Latex vậy

Hình như $\binom{n}{2}= \frac{n(n-1)}{2}$ mà nhỉ?

 

Mình làm rõ điều kiện cho đề bài nữa là $p$ có thể chọn được (chứ không phải $p$ cho trước).

 

$\binom{n}{k}$ viết trong $\LaTeX$ là

$\binom{n}{k}$

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”). 


#96
bangbang1412

bangbang1412

    Độc cô cầu bại

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

Bài 38 : Ta chứng minh rằng mọi ước nguyên tố $q$ của $\frac{p^{p}-1}{p-1}=p^{p-1}+....+p+1=A$ mà $q \not\equiv 1(modp^{2})$ thỏa mãn 

Trước tiên ta cần chứng minh có một ước như thế đã . Thật vậy giả sử mọi ước của nó đều dạng như vậy thế thì $A \equiv 1 \equiv p +1 (mod p^{2})$ cái này vô lý

Giả sử tồn tại $n$ mà $n^{p} \equiv p (mod q)$ thế thì ta có $n^{p^{2}} \equiv p^{p} \equiv 1 (mod q)$

Hơn nữa theo Fermat nhỏ ta có $n^{q-1} \equiv 1(modq)$

Gọi $x$ là cấp của $n$ theo $modq$ thế thì $x | (q-1,p^{2})$ 

Nếu $x = p^{2}$ thì ta suy ra vô lý vì khi đó $q \equiv 1 (mod p^{2})$ 

Nếu $x = p$ ta có $n^{p} \equiv 1(mod p)$ nhưng lại có $n^{p} \equiv p (modq) => p \equiv 1 (mod q)$ , nhưng $p$ là cấp của $n$ theo $modq$ nên $q \equiv 1(mod p)$

Nhưng khi đó $p-1 \geq q \geq p +1$ vô lý 

Nếu $x = 1$ thì ta có $n \equiv 1 (mod q)$ khi đó $p \equiv 1 (mod q)$ , khi đó $A \equiv p-1 +1 \equiv 0 \equiv p (mod q)$ vô lý

Vậy ta có đpcm

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 viết đã được chỉnh sửa nội dung bởi bangbang1412: 02-06-2016 - 11:11

$$[\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})).$$


#97
Visitor

Visitor

    Hạ sĩ

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

 

 

Bài 37. [AoPS] Với mỗi số nguyên $r$, chứng minh rằng tồn tại số tự nhiên $n_r$ sao cho với mọi số nguyên $n>n_r$ tồn tại ít nhất một số nguyên dương $k$ thoả mãn $1 \le k \le n-1$ và $p^r$ là ước của $\binom{n}{k}$ với $p$ là số nguyên tố nào đó.

Lời giải của mình.

Lấy $p,q$ là hai số nguyên tố bất kì.

Với mỗi $r$ chọn $n_r=max(p^r,q^r)+100$

Xét số nguyên $n$ bất kì lớn hơn $n_r$. Ta thấy luôn luôn có $p^a-1\neq q^b-1$ do $p\neq q$ nên $n$ ko thể có cả hai dạng $p^a-1$ hoặc là $q^a-1$

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$.

Ta sẽ sử dụng định lí $Kummer$

Giả sử $n=(b_tb_{t-1}...b_1b_0)_p$ với $b_0\neq p-1$ và do cách chọn $n_r$ nên $t>>r$.

CHọn $k=[b_rb_{r-1}...b_1(b_0+1)]_p$ 

Dễ thấy rằng khi trừ $n-k$ trong hệ $p$-phân sẽ được kết quả là một số có $r+1$ chữ số tận cùng bằng $p-1$ ( $p-1$ là chữ số lớn nhất trong hệ cơ số này)

Khi đó thì phép cộng $n-k$ với $k$ sẽ nhớ ít nhất là $r$ lần, theo định lí $Kummer$ ta có $v_p\binom{n}{k}\geq r$.

Ta có đpcm.

 

Bài 40.   Tìm tất cả các số tự nhiên $m$ sao cho với mọi sô thuộc tập $\{0,1,2,..,m-1\}$ đều đồng  dư với một số dạng $x^2+y^2$ mod $m$.


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

__________

Bruno Mars


#98
IMOer

IMOer

    Hạ sĩ

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

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$.

Dòng này sai, ví dụ: $b_3=99, b_5=3363$ đều là các số chia hết cho 3.

 

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$.

 

Đoạn này cũng sai, ví dụ $v_2=198; v_5=192060$ đều chia hết cho 3.



#99
Ego

Ego

    Thượng sĩ

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

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$.

Chỗ này có lỗi, $b_{3} = 99$. Và mình chứng minh được kết quả mạnh hơn. Đây là đoạn mình còn khúc mắc (chắc là chỗ khó nhất). Mình còn chứng minh được luôn tồn tại $i$ để $3^{k}\mid b_{i}$

Bài 37. [AoPS] Với mỗi số nguyên $r$, chứng minh rằng tồn tại số tự nhiên $n_r$ sao cho với mọi số nguyên $n>n_r$ tồn tại ít nhất một số nguyên dương $k$ thoả mãn $1 \le k \le n-1$ và $p^r$ là ước của $\binom{n}{k}$ với $p$ là số nguyên tố.

Lời giải bài 37.

Ta sẽ dùng định lý Kummer như sau:
Định lý Kummer. Số mũ của $p$ trong biểu diễn $\dbinom{n}{k}$ bằng với số lần của phép nhớ trong phép cộng $n - k$ và $k$ trong biểu diễn cơ số $p$.
Bổ đề. Luôn tồn tại $L$ để tích $k \ge L$ số nguyên tố đầu tiên lớn hơn $p_{k + 1}^{r}$
Bây giờ ta chọn $n_{r} = \prod_{i = 1}^{k}p_{i}$ như trên. Ta sẽ chứng minh bài toán đúng với mọi $n > n_{r}$
Bây giờ nếu như trong biểu diễn cơ số $p_{i}$ nào đó ($1\le i \le k$) thì chữ số tận cùng khác $p_{i} - 1$ thì áp dụng định lý Kummer, ta luôn chọn được $k$ thỏa mãn $v_{p_{i}}(n) > r$ lí do là $n > p_{k + 1}^{r} > p_{i}^{r}$. Do đó ta chỉ còn TH sau:
Gọi $p_{u}$ là số nguyên tố đầu tiên sao cho $n + 1$ không chia hết cho $p_{u}$, lúc này $u \ge k + 1$. Nếu như lúc này chữ số tận cùng của $n$ là $p_{u} - 1$ thì $n + 1 \vdots p_{u}$ là vô lý. Mặt khác, $n + 1 \vdots p_{1}p_{2}\cdots p_{u - 1}$ nên $n + 1 \ge \prod_{i = 1}^{u - 1}p_{i} > p_{u}^{r}$ theo bổ đề, từ đây ta có $n$ trong biểu diễn cũng có ít nhất $r$ chữ số.
Xong.

Hi


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


#100
Zaraki

Zaraki

    PQT

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

:(  ... Để mình nghĩ lại câu 36 vậy. 

 

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})$

Bằng có thể cho biết nguồn của bài này được không, tại nhìn bài này thấy quen quen. :)


  • Ego yêu thích

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”). 





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

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