Diễn Đàn MathScopeDiễn Đàn MathScope
  Diễn Đàn MathScope
Ghi Danh Hỏi/Ðáp Thành Viên Social Groups Lịch Ðánh Dấu Ðã Ðọc

Go Back   Diễn Đàn MathScope > Sơ Cấp > Lý Thuyết Số

News & Announcements

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é !

* Nội quy MathScope.Org

* Một số quy định chung !

* 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

* Những câu hỏi thường gặp

* Về việc viết bài trong Box Đại học và Sau đại học


Trả lời Gởi Ðề Tài Mới
 
Ðiều Chỉnh Xếp Bài
Old 03-11-2017, 06:55 AM   #1
huynhcongbang
Administrator

 
huynhcongbang's Avatar
 
Tham gia ngày: Feb 2009
Đến từ: Ho Chi Minh City
Bài gởi: 2,413
Thanks: 2,165
Thanked 4,188 Times in 1,381 Posts
Gửi tin nhắn qua Yahoo chát tới huynhcongbang
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ý.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
__________________
Sự im lặng của bầy mèo
huynhcongbang is offline   Trả Lời Với Trích Dẫn
The Following User Says Thank You to huynhcongbang For This Useful Post:
buratinogigle (04-11-2017)
Old 03-11-2017, 02:45 PM   #2
Thụy An
+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:
Nguyên văn bởi huynhcongbang View Post
Trước hết, mọi người có thể xem bài toán tại post 27 của:

[Only registered and activated users can see links. ]

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.$
Cắt lời giải bài này từ bên kia qua đây để tiện theo dõi.

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. ]
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
Thụy An is offline   Trả Lời Với Trích Dẫn
The Following User Says Thank You to Thụy An For This Useful Post:
buratinogigle (04-11-2017)
Old 09-11-2017, 06:25 PM   #3
huynhcongbang
Administrator

 
huynhcongbang's Avatar
 
Tham gia ngày: Feb 2009
Đến từ: Ho Chi Minh City
Bài gởi: 2,413
Thanks: 2,165
Thanked 4,188 Times in 1,381 Posts
Gửi tin nhắn qua Yahoo chát tới huynhcongbang
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 đó:
  • Nếu $p=2$ thì $s({{2}^{k}})={{2}^{\max (k-3,0)}}$.
  • Nếu $p>2$ thì $s({{p}^{k}})=\dfrac{{{p}^{k}}-{{p}^{k-1}}}{2}$.

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.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
__________________
Sự im lặng của bầy mèo
huynhcongbang is offline   Trả Lời Với Trích Dẫn
The Following User Says Thank You to huynhcongbang For This Useful Post:
MATHSCOPE (09-11-2017)
Old 10-11-2017, 08:04 AM   #4
Thụy An
+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:
Nguyên văn bởi huynhcongbang View Post
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}}$.
Đoạn này, anh thấy Lữ trình bày chưa rõ ràng lắm. Nhưng kết quả Lữ đưa thì đúng nếu ta dùng căn nguyên thuỷ mod p.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
Thụy An is offline   Trả Lời Với Trích Dẫn
Trả lời Gởi Ðề Tài Mới

Bookmarks

Ðiều Chỉnh
Xếp Bài

Quuyền Hạn Của Bạn
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is Mở
Smilies đang Mở
[IMG] đang Mở
HTML đang Tắt

Chuyển đến


Múi giờ GMT. Hiện tại là 02:31 PM.


Powered by: vBulletin Copyright ©2000-2024, Jelsoft Enterprises Ltd.
Inactive Reminders By mathscope.org
[page compression: 61.25 k/66.90 k (8.44%)]