|
|
|
Ngoài một số quy định đã được nêu trong phần Quy định của Ghi Danh , mọi người tranh thủ bỏ ra 5 phút để đọc thêm một số Quy định sau để khỏi bị treo nick ở MathScope nhé ! * Quy định về việc viết bài trong diễn đàn MathScope * Nếu bạn muốn gia nhập đội ngũ BQT thì vui lòng tham gia tại đây |
| Ðiều Chỉnh | Xếp Bài |
03-11-2017, 06:55 AM | #1 |
Administrator | Bài số học trong đề KHTN - Ý tưởng cũ hay mới? Các bài toán dãy số nguyên cùng các tính chất số học là chủ đề phổ biến trong thi HSG. Đôi khi, việc chứng minh tính khẳng định lại dễ hơn là chứng minh phủ định. Trước hết, mọi người có thể xem bài toán tại post 27 của: http://mathscope.org/showthread.php?t=51387&page=2 Cho dãy số $\left(a_n\right)$ xác định bởi công thức sau: $$a_0=1;\,a_1=4;\,a_{n+2}=2a_{n+1}+3a_n\quad \forall \,n \in\mathbb N.$$ Chứng minh rằng trong dãy số trên không có số nào là bội của $2017.$ Ta biết một kết quả quen thuộc rằng dãy số dư của dãy trên khi chia cho $2017$ thì luôn tuần hoàn, và vì $(3,2017)=1$ nên sẽ tuần hoàn từ số hạng đầu tiên. Do đó, nếu đi hết chu kỳ của dãy này mà không có số nào bằng 0 thì bài toán dĩ nhiên được giải quyết. Tuy nhiên, đi đến bao giờ mới xong? Dĩ nhiên là chu kỳ đó có thể rất lớn, không thể nào tính toán bằng tay trong phòng thi được. Nếu ở đây số nguyên tố $2017$ được thay bằng $2,3,5,7$ là các số nhỏ thì bài toán sẽ được giải quyết dễ dàng (và tất nhiên nó sẽ không còn là đề chọn đội tuyển của KHTN nữa). Để xử lý yếu tố lớn của $2017,$ ta chỉ còn cách chỉ ra mâu thuẫn nào đó trong công thức tổng quát của $(u_n)$; cụ thể hơn ở đây dùng thặng dư bậc hai để chỉ ra $\left( {\frac{5}{{2017}}} \right) = - 1$, nghĩa là 5 không là số chính phương mod 2017 như công thức tổng quát của đề bài. Tuy nhiên, ý tưởng này đã từng được KHTN sử dụng trong các đề thi cũ hơn: (1) HSG toán lớp 10 THPT chuyên KHTN 2012-2013 đợt 2: http://mathscope.org/showthread.php?t=39680 (2) [Vòng 1] Ngày thứ hai- Đề thi chọn HSG lớp 11-12 KHTN 2012-2013 http://forum.mathscope.org/showthread.php?t=36226 Dưới đây, ta sẽ giải chi tiết bài trong (2), đã nhiều năm qua nhưng chưa thấy lời giải nào post lên. Cho dãy số ${a_n}$ xác định bởi : $\left\{\begin{matrix} &a_1=33;a_2=49,a_3=177 \\ & a_{n+3}=8a_{n+2}-8a_{n+1}+a_n \end{matrix}\right.$ Chứng minh rằng với mọi giá trị của của $n$, $a_n$ không chia hết cho $2013$. Lời giải. Trước hết, ta tìm được công thức tổng quát của dãy là \[\begin{align} & {{a}_{n}}=\frac{133}{5}+\frac{16}{5}\left[ {{\left( \frac{7+3\sqrt{5}}{2} \right)}^{n-1}}+{{\left( \frac{7-3\sqrt{5}}{2} \right)}^{n-1}} \right]=\frac{133}{5}+\frac{16}{5}\left[ {{\left( \frac{\sqrt{5}+1}{2} \right)}^{4n-4}}+{{\left( \frac{\sqrt{5}-1}{2} \right)}^{4n-4}} \right] \\ & =33+16F_{2n-2}^{2} \\ \end{align}\] Ta sẽ chứng minh rằng $61\not{|}{{a}_{n}}$ để chỉ ra rằng $2013\not{|}{{a}_{n}}$. Thật vậy, giả sử tồn tại ${{a}_{n}}$ thỏa mãn thì $$61|-28+16F_{2n-2}^{2}\Rightarrow 61|-7+4F_{2n-2}^{2}\Rightarrow \left( \frac{7}{61} \right)=1.$$ Dùng luật tương hỗ Gauss với chú ý $61\equiv 1(\bmod 4)$ thì $$\left( \frac{61}{7} \right)=1\Leftrightarrow {{(-2)}^{3}}\equiv {{61}^{3}}\equiv 1(\bmod 7).$$ Đây là điều vô lý. __________________ Sự im lặng của bầy mèo |
The Following User Says Thank You to huynhcongbang For This Useful Post: | buratinogigle (04-11-2017) |
03-11-2017, 02:45 PM | #2 |
+Thành Viên+ Tham gia ngày: Oct 2017 Bài gởi: 93 Thanks: 1 Thanked 68 Times in 45 Posts | Trích: Lời giải. Giải phương trình đặc trưng $x^2=2x+3$ để có công thức truy hồi của dãy là \[{a_n} = \frac{{{{5.3}^n} - {{\left( { - 1} \right)}^n}}}{4}\quad\forall\,n\in\mathbb N.\] Giả sử tồn tại số tự nhiên $n$ để $2017\mid a_n$, lúc đó có đồng dư \[{5.3^n} \equiv {\left( { - 1} \right)^n}\pmod{2017};\;(*)\] Để ý rằng $\left( {\dfrac{{ - 1}}{{2017}}} \right) = {\left( { - 1} \right)^{\frac{{2017 - 1}}{2}}} = 1$ , và theo luật thuận nghịch thì \[\left( {\frac{3}{{2017}}} \right)\left( {\frac{{2017}}{3}} \right) = {\left( { - 1} \right)^{\frac{{\left( {3 - 1} \right)\left( {2017 - 1} \right)}}{4}}} = 1\] Trong khi $2017^{\frac{3-1}{2}}\equiv 1\pmod 3$, cho nên chứng tỏ $3$ là thặng dư bậc hai theo mod $2017$. Những điều đó kết hợp với $(*)$ cho ta $5$ là thặng dư bậc hai mod $2017$; $(1)$, đồng thời \[\left( {\frac{5}{{2017}}} \right)\left( {\frac{{2017}}{5}} \right) = {\left( { - 1} \right)^{\frac{{\left( {5 - 1} \right)\left( {2017 - 1} \right)}}{4}}} = 1\] Có điều, $2017^{\frac{5-1}{2}}\equiv -1\pmod 5$ nên \[\left( {\frac{5}{{2017}}} \right) = \left( {\frac{{2017}}{5}} \right) = - 1;\;(2).\] Từ mâu thuẫn của $(1)$ và $(2)$, cho ta điều cần chứng minh. [Only registered and activated users can see links. ] |
The Following User Says Thank You to Thụy An For This Useful Post: | buratinogigle (04-11-2017) |
09-11-2017, 06:25 PM | #3 |
Administrator | Tiếp tục một bài liên quan đến thặng dư bậc hai, mình lấy từ đề thi PTNK 2015: Cho tập hợp $A=\left\{ n\in \mathbb{N}|1\le n\le 2015,(n,2016)=1 \right\}$. Hỏi có bao nhiêu số nguyên $a\in A$ sao cho tồn tại số nguyên $b$ mà $a+2016b$ là số chính phương? Lời giải. Cho $n$ là số nguyên dương lớn hơn $1,$ ta quy ước gọi một số nguyên dương $a$ được gọi là thặng dư chính phương theo modulo $n$ nếu$(a,n)=1$ và tồn tại số nguyên $x$ sao cho $a\equiv {{x}^{2}}(\bmod n).$ Trong bài này, để đơn giản, ta quy ước xét các thặng dư chính phương nhỏ hơn $n.$ Đặt $s(n)$ là số các số nhỏ hơn $n$ và là thặng dư chính phương theo modulo $n$. Ta sẽ chứng minh hai bổ đề dưới đây: Bổ đề 1. Cho $p$ là số nguyên tố và $k$ là số nguyên dương. Khi đó:
Bổ đề 2. $s(n)$ là hàm nhân tính. Thật vậy, Trước hết, ta biết rằng $s(p)=\frac{p-1}{2}$ với $p$ là số nguyên tố lẻ. Ta sẽ tính $s({{p}^{k}})$ với $k\in {{\mathbb{Z}}^{+}}$. Xét một thặng dư chính phương $a$ của $p$, khi đó tồn tại $x$ sao cho $$a\equiv {{x}^{2}}(\bmod p).$$ Đặt $a={{x}^{2}}+pq$ thì hiển nhiên $$a\equiv {{x}^{2}}+pq(\bmod {{p}^{k}})\Leftrightarrow a-pq\equiv {{x}^{2}}(\bmod {{p}^{k}})$$ và khi đó, ta có ${{p}^{k-1}}$ cách chọn $q$ để các số $a-pq$ là các thặng dư chính phương $\bmod {{p}^{k}}$. Suy ra $$s({{p}^{k}})={{p}^{k-1}}s(p)=\frac{{{p}^{k}}-{{p}^{k-1}}}{2}.$$ Xét số nguyên tố $p=2$, với $k=1,2,3,$ dễ dàng kiểm tra được $s({{2}^{k}})=1$. Ta xét $k\ge 4$, tương tự trên, ở bước chọn $q$, ta chỉ có 2 cách nên $s({{2}^{k}})=2s({{2}^{k-1}})$. Từ đó bằng quy nạp, ta có được $$s({{2}^{k}})={{2}^{k-3}},k\ge 4.$$ Tiếp theo, xét hai số $a,b$ nguyên dương và $(a,b)=1$. Gọi $A$ là tập hợp các thặng dư chính phương theo modulo $ab$ và $B$ là tập hợp các số là thặng dư chính phương chung của $a,b.$ Nếu $x\in A$ thì tồn tại $y$ sao cho $x\equiv {{y}^{2}}(\bmod ab)$. Rõ ràng khi đó, $$x\equiv {{y}^{2}}\pmod a,x\equiv {{y}^{2}}\pmod b$$ (chú ý rằng nếu $x>a$, ta có thể chọn ${x}'$ sao cho ${x}'<a$ và $x\equiv {x}'\pmod a$; tương tự với $b$). Do đó, $x\in B$, tức là $x\in A\Rightarrow x\in B$ nên $\left| A \right|\le \left| B \right|$. Tiếp theo, xét $x\in B$. Khi đó tồn tại $r,s$ sao cho $x\equiv {{r}^{2}}\pmod a,\text{ }x\equiv {{s}^{2}}\pmod b$. Theo định lý thặng dư Trung Hoa, tồn tại số nguyên $z$ sao cho $$z\equiv r\pmod a,z\equiv s\pmod b.$$ Khi đó $$x\equiv {{z}^{2}}\pmod a,x\equiv {{z}^{2}}\pmod b$$ nên $$x-{{z}^{2}}\vdots ab \text{ hay } x\equiv {{z}^{2}}(\bmod ab).$$ Do đó: $x\in A$, tức là $x\in B\Rightarrow x\in A$ nên $\left| A \right|\ge \left| B \right|$. Từ đây ta có $$\left| A \right|=\left| B \right| \text{ hay } s(a)s(b)=s(ab).$$ Vậy $s(n)$ là hàm nhân tính. Các bổ đề đều được chứng minh. Trở lại bài toán, ta thấy rằng $$2016={{2}^{5}}\cdot {{3}^{2}}\cdot 7.$$ Rõ ràng bài toán yêu cầu đếm số thặng dư chính phương theo modulo $2016$. Theo bổ đề 2 thì $$s(2016)=s({{2}^{5}})s({{3}^{2}})s(7).$$ Theo bổ đề 1 thì $$s({{2}^{5}})={{2}^{2}}=4,s({{3}^{2}})=\frac{{{3} ^{2}}-3}{2}=3,s(7)=\frac{7-1}{2}=3.$$ Do đó, số các số $a$ cần tìm là $4\cdot 3\cdot 3=36.$ Nhận xét. Bài toán này hoàn toàn có thể giải bằng cách xét các số dư một cách tương đối "thủ công", không sử dụng các kết quả về thặng dư chính phương hay thậm chí là định lý thặng dư Trung Hoa. __________________ Sự im lặng của bầy mèo |
The Following User Says Thank You to huynhcongbang For This Useful Post: | MATHSCOPE (09-11-2017) |
10-11-2017, 08:04 AM | #4 | |
+Thành Viên+ Tham gia ngày: Oct 2017 Bài gởi: 93 Thanks: 1 Thanked 68 Times in 45 Posts | Trích:
| |
Bookmarks |
Ðiều Chỉnh | |
Xếp Bài | |
|
|