Number Theory 33

by

(Gabriel Dospinescu)
[Bài toán]: CMR 2^{3^n}+1 có ít nhất n ước nguyên tố dạng 8k+3
                                                      Lời giải
Nhận xét (Tương tự bài Vietnam TST 2004): 2^n+1 không có ước nguyên tố dạng 8k-3,8k-1
Xét n chẵn: Ta có 2^n\equiv -1\pmod p\Rightarrow \left ( \frac{-1}{p} \right )=1\Rightarrow (-1)^{\frac{p-1}{2}}\equiv 1\pmod 4\Rightarrow p\equiv 1\pmod 4 (mâu thuẫn)
Xét n lẻ. Ta có: 2^{n+1}\equiv -2\pmod p\Rightarrow \left ( \frac{-2}{p} \right )=\left ( \frac{-1}{p} \right )\left ( \frac{2}{p} \right )=1
(-1)^{\frac{p-1}{2}}.(-1)^{\frac{p^2-1}{8}}=1. Mặt khác: p\equiv 5;7\pmod 8\Rightarrow (-1)^{\frac{p-1}{2}}.(-1)^{\frac{p^2-1}{8}}=-1 (mâu thuẫn) \rightarrow Q.E.D
Từ nhận xét trên, do đó mọi ước ước nuyên tố của 2^{3^n}+1 đều có dạng 8k+1,8k+3
Ta có: 2^{3^n}+1=(2+1)(2^2-2+1)(2^{2.3}-2^3+1)...(2^{2.3^{n-1}}-2^{3^{n-1}}+1)
Đặt S_i=2^{2.3^i}-2^{3^i}+1\forall i=\overline{1,n-1}
Ta có: S_i\equiv 1-(-1)+1\equiv 3\pmod 9\Rightarrow 3||S_i\forall i=\overline{1,n-1}\qquad (1)
Gọi p|\gcd(S_i,S_j)\forall i,j=\overline{1,n-1}. Ta có: p|S_i|2^{3^{i+1}}+1
Ta có: 2^{3^j}=(2^{3^{i+1}})^{3^{j-i-1}}\equiv (-1)^{3^{j-i-1}}\equiv -1\pmod p
\Rightarrow 0\equiv S_j\equiv 2^{2.3^j}-2^{3^j}+1\equiv 1+1+1\equiv 3\pmod p\Rightarrow p=3\qquad (2)
Từ (1),(2)\Rightarrow \gcd(S_i,S_j)=3\forall i,j=\overline{1,n-1}
Nếu mọi ước nguyên tố của S_i (trừ 3) đều có dạng 8k+1\Rightarrow S_i\equiv 3\pmod 8 (vô lí)
Do đó S_i có ước nguyên tố dạng 8k+3 mà p_i\neq 3 do \gcd(S_i,S_j)=3
\Rightarrow p_i\neq p_i\forall i,j=\overline{1,n-1}
Vậy  2^{3^n}+1 có ít nhất n ước nguyên tố dạng 8k+3 là 3,p_1,p_2,...,P_{n-1} \blacksquare

Number Theory 32

by

(Taiwan TST 2005)
[Bài toán]: Cho m,n\in \mathbb{Z^+} thỏa mãn \varphi(5^m-1)=5^n-1. CMR: \gcd(m,n)>1
                                                                 Lời Giải
Đặt 5^m-1=2^k\prod_{i=1}^{h}p_{i}^{\alpha_i}. Phản chứng giả sử \gcd(m,n)=1

\blacktriangleright Trường hợp 5^m-1 không có ước nguyên tố lẻ
\Rightarrow 5^m-1=2^k\Rightarrow 5^n-1=2^{k-1}\Rightarrow 5^m-5^n=2^{k-1} (vô lí)

\blacktriangleright Trường hợp 5^{m}-1 có ước nguyên tố lẻ.
Ta có: \varphi(5^m-1)=2^{k-1}\prod_{i=1}^{h}p_i^{\alpha_i}\prod_{i=1}^{h}(p_i-1)=5^n-1
Lại có: \gcd(5^m-1,5^n-1)=5^{\gcd(m,n)}-1=4\qquad (1)
Nếu k\geq 3 thì 8|5^n-1,5^m-1, trái với (1). Nếu k=1\Rightarrow 2||5^m-1, cũng trái với (1)
Do đó k=2. Xét \exists j\in \mathbb{Z^+},\alpha_j>1\Rightarrow 5^m-1\equiv 5^n-1\equiv 0\pmod p_j, mâu thuẫn với (1). Dẫn tới a_i=1\forall i=\overline{1,h}
Ta có: \begin{cases} 5^m-1=4\prod_{i=1}^{h}p_i\\5^n-1=2\prod_{i=1}^{h}\end{cases}
Vì 4||5^m-1\Rightarrow m lẻ. Ta có: 5^m\equiv 1\pmod{p_i}\Leftrightarrow 5^{m+1}\equiv 5\pmod{p_i} \Rightarrow \left ( \frac{5}{p_i} \right )=1\forall i=\overline{1,h}
Theo Luật Thuận nghịch bình phương Gauss: \left ( \frac{5}{p_i} \right )\left ( \frac{p_i}{5} \right )=(-1)^{\frac{(p_i-1)(5-1)}{4}}=1
\Rightarrow \left ( \frac{p_i}{5} \right )=1\Rightarrow p_1\equiv \pm 1\pmod 5
Nếu p_i\equiv 1\pmod 5\Rightarrow 5|5^n-1 (vô lí). Do đó p_i\equiv -1\pmod 5
Ta có: 5^m-1\equiv 4\equiv 4\prod_{i=1}^{h}p_i\equiv 4(-1)^h\pmod 5\Rightarrow h chẵn
\Rightarrow 5^n-1\equiv 2^{h+1}\equiv -1\pmod 5\Rightarrow 2^{h+2}\equiv 3\pmod 5\Rightarrow \left ( \frac{3}{5} \right )=1 (vô lí)

Kết luận: Vậy giả sử sai, ta có Q.E.D

Number Theory 31

by

(Chọn đội tuyển KHTN 2009)
[Bài toán]: Tìm a,b,c,d\in \mathbb{N} đôi một phân biệt thỏa mãn: a^2-b^2=b^2-c^2=c^2-d^2

Lời Giải. Bài toán tương đương với việc tìm một cấp số cộng thực sự gồm 4 số chính phương. Ta chứng minh rằng không tồn tại một cấp số cộng như vậy. Giả sử ngược lại tồn tại 4 số chính phương A^2,B^2,C^2,D^2 lập thành một cấp số cộng tăng, tức là A^2-B^2=B^2-C^2. Trong các cấp số như thế, chọn cấp số có công sai nhỏ nhất. Ta có thể giả sử rằng các số chính phương này đôi một nguyên tố cùng nhau, và tính chẵn lẻ của các phương trình chứng tỏ rằng mỗi một số chính phương này phải lẻ. Như vậy tồn tại các số nguyên nguyên tố cùng nhau u,v sao cho A=u-v,C=u+v,u^2+v^2=B^2, và công sai của cấp số cộng bằng \displaystyle{\frac{C^2-A^2}{2}=2uv}

Ta cũng có D^2-B^2=4uv, và có thể viết thành \displaystyle{[\frac{D+B}{2}.\frac{D-B}{2}]}=uv. Hai thừa số ở vế trái nguyên tố cùng nhau, và u và v cũng thế. Như vậy tồn tại 4 số nguyên đôi một nguyên tố cùng nhau a,b,c,d (trong đó có đúng 1 số chẵn) sao cho u=ab,v=cd,D+B=2ac,D-B=2bd. Từ đây suy ra B=ac-bd, và như vậy ta có thể thế vào phương trình u^2+v^2=B^2 để được (ab)^2+(cd)^2=(ac-bd)^2. Phương trình này là đối xứng đối với 4 biến số nên ta có thể giả sử c là chẵn và a, b, d là lẻ. Từ phương trình bậc 2 này ta suy ra c là hàm hữu tỷ của căn bậc 2 của a^4-a^2d^2+d^4, từ đó suy ra tồn tại số nguyên lẻ m sao cho a^4-a^2d^2+d^2=m^2

Vì a và d là lẻ nên tồn tại các số nguyên nguyên tố cùng nhau x và y sao cho a^2=k(x+y) và d^2=k(x-y), trong đó k=\pm 1. Thay vào phương trình nói trên, ta được x^2+3y^2=m^2, từ đó rõ ràng là y phải là số chẵn và x lẻ. Đổi dấu x nếu cần, ta có thể giả sử m+x\vdots 3, ta có \displaystyle{3(\frac{y}{2})^2=\frac{(m+x)(m-x)}{4}}, từ đó suy ra \displaystyle{\frac{m+x}{2}} là ba lần số chính phương còn \displaystyle{\frac{m-x}{2}} là số chính phương. Như vậy ta có các số nguyên nguyên tố cùng nhau r, s (một số chẵn và một số lẻ) sao cho \displaystyle{\frac{3+x}{2}=3r^2,\frac{m-x}{2}=s^2,m=3r^2+s^2,x=3r^2-s^2, y=\pm 2rs}

Thay x và y vào các biểu thức của a^2,d^2 (và biến đổi nếu cần) ta được a^2=k(s+r)(s-3r) và d^2=k(s-r)(s+3r). Vì các thừa số ở vế phải là nguyên tố cùng nhau nên 4 đại lượng s-3r,s-r,s+r,s+3r phải có trị tuyệt đối chính phương, với công sai 2r. Các đại lượng này tất cả phải cùng dấu vì nếu ngược lại thì tổng của hai số chính phương lẻ bằng hiệu của hai số chính phương lẻ, tức là, 1+1\equiv 1-1\pmod 4, mâu thuẫn.

Vì thế, ta phải có \left | 3r \right |<s, và do m=3r^2+s^2 ta có 12r^2<m. Mặt khác, từ phương trình bậc 4 ta có m<a^2+d^2, như vậy ta có bất đẳng thức \left | 2r \right |<\left | max(a,d) \right |. Như vậy ta có 4 số chính phương lập thành một cấp số cộng với công sai \left | 2r \right |<\left | 2abcd \right |, và số cuối cùng chính là công sai của cấp số cộng ban đầu. Điều này mâu thuẫn với cách chọn bốn số chính phương ban đầu, phép chứng minh hoàn tất. \blacksquare
_________________________________

Nhận xét: Bài toán Fermat của học sinh, còn kia là bài toán Fermat của các GS,TS @@

Number Theory 30

by

[Bài toán]: CMR: Với mỗi n\in \mathbb{Z^+} đều chọn được k\in \mathbb{Z^+} để 2^n|19^k-97
                                                 Lời Giải
\blacktriangleright Bổ đề: Với n\in \mathbb{N}, n\geq 3. Khi đó 19^{2^{h-2}}-1=2^ht với t lẻ
Ta CM bằng quy nạp.
Với h=3 dễ thấy thỏa mãn
Giả sử ta có dpcm với h=k. Do đó có giả thiết quy nạp 19^{2^{k-2}}-1=2^kt
Ta CM với h=k+1 có 19^{2^{k-1}}-1=2^{k+1}l với l lẻ
Thật vậy 19^{2^{k-1}}-1=(19^{2^{k-2}}-1)(19^{2^{k-2}}+1).
Mặt khác, \gcd(19^{2^{k-2}}-1;19^{2^{k-2}}+1=2. Kết hợp giả thiết quy nạp \Rightarrow 19^{2^{k-2}}+1=2s với s lẻ
Do đó 19^{2^{k-1}}-1=2^{k+1}st=2^{k+1}l với l lẻ. Vậy bổ đề được CM.

\blacktriangleright Áp dụng: Lại sử dụng quy nạp. Giả sử \forall k=k_n đúng. Giả thiết: 19^{k_n}-97=2^nh, h lẻ
Ta CM với k_{n+1}=k_n+2^{n-2}, có 19^{k_{n+1}}-97=2^{n+1}m, m lẻ.
Với h chẵn, thỏa mãn
Với h lẻ. Ta có: 19^{k_n+1}-97=19^{2^{n-2}}(19^{k_n}-97)+97(19^{2^{n-2}}-1)=2^n(19^{2^{n-2}}h+97g)=2^{n+1}m

Kết luận: Vậy có Q.E.D \blacksquare

Number Theory 29

by

(VMO 2001)
[Bài toán]: Cho n,a,b nguyên dương, a,b>1 nguyên tố cùng nhau. Giả sử p,q là hai ước nguyên tố lẻ của a^{6^n}+b^{6^n}. Tìm số dư trong phép chia p^{6^n}+q^{6^n} cho 6.(12)^n
                                                Lời giải
Trước hết ta cần hai bổ đề:
\blacktriangleright Bổ đề 1: Với a,b\in \mathbb{Z^+},\gcd(a,b)=1. Cho p là ước nguyên tố lẻ của a^{6^n}+b^{6^n}. CMR: p\equiv 1\pmod {2^{n+1}}
Chứng minh: Vì p|a^{6^n}+b^{6^n}\Rightarrow a^{6^n}+b^{6^n}=tp\qquad (t\in \mathbb{Z^+})
Viết p=2^mv+1\qquad (m,v\in \mathbb{Z^+},v lẻ
Xét m<n+1. Theo định lí Fermat nhỏ vì \gcd(a,p)=\gcd(b,p)=1
Ta có: (a^{3^m.2^{n-m}})^{p-1}\equiv (b^{3^{n-m}.2^m})\equiv 1\pmod p
\Leftrightarrow (a^{6^n})^{2^mv}\equiv (b^{6^n})^{2^mv}\equiv 1\pmod p\Leftrightarrow (a^{6^n})^v\equiv (b^{6^n})^v\equiv 1\pmod p (1)
Lại có: (a^{6^n})^v=(tp-b^{6^n})^v\equiv -(b^{6^n})^v\pmod p\qquad (2)
Từ (1),(2)\Rightarrow 2(b^{6^n})^v\equiv 0 (vô lí)
Do đó m\geq n+1\rightarrow p=2^mv+1\equiv 1\pmod 2^{n+1}\rightarrow Q.E.D

\blacktriangleright Bổ đề 2: Cho x,c,m,k\in \mathbb{Z^+} thỏa x\equiv 1\pmod {c^k}.
CMR: x^{c^m}\equiv 1\pmod {c^{k+m}}
Chứng minh: Vì x\equiv 1\pmod {c^k}\Rightarrow x-1=tc^k
Ta có: x^{c^m}=(tc^k+1)^{c+m}=A.(c^k)^{c^m}+1=A.c^{k+c^m}+1
mà  k+c^m>k+m\forall c\geq 2 (vì c=1 luôn đúng) \Rightarrow Q.E.D

\blacktriangleright Áp dụng:  Ta có: p,q|a^{6^n}+b^{6^n}\Rightarrow p\equiv q\equiv 1\pmod {2^{2n+1}} (Bổ đề 1)
\Rightarrow p^{3^n}\equiv q^{3^n}\equiv 1\pmod {2^{2n+1}}\qquad (3)
Mặt khác, vì \gcd(a,b)=1;p,q|a^{6^n}+b^{6^n}\Rightarrow p^{6^n}\equiv q^{6^n}\equiv 1\pmod 3
\Rightarrow p^{2^n}\equiv q^{2^n}\equiv 1\pmod 3 mà theo bổ đề 2 \Rightarrow p^{6^n}\equiv q^{6^n}\equiv 1\pmod 3 (4)
Từ (3),(4) mà \gcd(2,3)=1\Rightarrow p^{6^n}\equiv q^{6^n}\equiv 1\pmod {2^{2n+1}.3^{n+1}}
\Longrightarrow p^{6^n}+q^{6^n}\equiv 2 \pmod {6.(12)^n}
Kết luận: Vậy dư là \boxed{2}

Number Theory 27

by

(Middle European MO 2012)
[Bài toán]:Tìm x,y,z\in \mathbb{Z^+} thỏa mãn: \begin{cases}x^y+y^x=z^y\qquad (1)\\x^y+2012=y^{z+1}\qquad (2)\end{cases}
                                                              Lời giải
Từ (2)\Rightarrow x,y cùng dấu \Rightarrow z chẵn. Đặt z=2c với c nguyên dương

\blacktriangleright Xét x,y cùng chẵn, đặt x=2a,y=2b với a,b nguyên dương
Ta có: (2)\Leftrightarrow (2a)^y+2^2.503=(2b)^{z+1}\Leftrightarrow 2^{2b-2}a^y+503=2^{2c-1}b^{2c-1}
\Rightarrow 2^{2b-2}.a^y lẻ \Rightarrow a lẻ, 2^{2b-2}=1\Leftrightarrow b=1\Rightarrow y=2
Thay vào (1), ta có: x^2+2^x=z^2\Leftrightarrow 2^x=(z-x)(z+x)\Rightarrow \begin{cases}z-x=2^m\\z+x=2^n\end{cases} với m<n,m+n=x nguyên dương
• Với m\geq 2. Ta có: 2x=2^n-2^m\Leftrightarrow a=2^{m-2}(2^{n-m}-1) mà a lẻ
\Rightarrow m=2\Leftrightarrow z-x=4\Leftrightarrow z=4+x\Rightarrow 2^x=8x+16
Ta thấy với x\in \{1;...;5\} không thỏa mãn, x\geq 7\rightarrow 2^x>8x+16 (theo quy nạp) \Rightarrow x=6\rightarrow z=10. Thử lại thỏa mãn.
• Với m=1\Rightarrow z-x=2\Leftrightarrow z=2+x\Rightarrow 2^x=4x+4
Với x=1 không thỏa mãn, x\geq 2\Rightarrow x+1=2^{x-2}\Rightarrow x=2 (không thỏa mãn)

\blacktriangleright Xét x,y cùng lẻ. Trừ (1)-(2), ta có: y^x+y^{z+1}=z^y+2012\qquad (3)
• Với y=1\Rightarrow x=-2011 (vô lí)
• Với y\geq 3. Từ (1)\Rightarrow x^y<z^y\Rightarrow x\leq z+1
Ta có: (3)\Rightarrow y^x(1+y^{z+1-x})\equiv 0\pmod 4 mà y lẻ \Rightarrow 4\nmid y^x, z+1-x chẵn, y lẻ
\Rightarrow 1+y^{z+1-x}\equiv 2\pmod 4\Rightarrow VT\equiv 2\pmod 4 (mâu thuẫn!)
Kết luận: Vậy \boxed{(x,y,z)=(6;2;10)} thỏa mãn ycđb \blacksquare

Geometry 3

by

(Korea TST Final Round 2013)
[Bài toán]: Cho \triangle ABC thỏa AB<AC, D\in AC sao cho \widehat{ABD}=\widehat{C}.I là tâm nội tiếp \triangle ABC và E=(CDI) giao với AI. Đường thẳng qua E//AB giao BD tại P. Giả sử J là tâm nội tiếp \triangle ABD và A' là đối xứng của A qua I, PJ giao với A'C tại Q. CMR: QJ=QA'.
       korea hình                                                Lời giải
Ta thấy IDCE:tgnt\Rightarrow \widehat{AED}=\widehat{ACI} mà \widehat{ABD}=\widehat{ACB}\Rightarrow \widehat{ACI}=\widehat{DBJ}
\Longrightarrow \widehat{DBJ}=\widehat{DEJ}\Rightarrow BJDE:tgnt\Rightarrow \widehat{BJE}=\widehat{BDE} mà \widehat{BIE}=\widehat{BAE}=\widehat{ABJ}=90^0-\widehat{BDJ}\Rightarrow \widehat{BDE}+\widehat{BDJ}=\widehat{JDE}=90^0
Lấy X là trung điểm BE\qquad (1)
Vì AB//EP\Rightarrow \widehat{BAE}=\widehat{PEA}
Mặt khác: BIDE:tgnt\Rightarrow \widehat{BDJ}=\widehat{JEB} \Longrightarrow \widehat{BEA}+\widehat{PEA}=\widehat{BAE}+\widehat{BDJ}=90^0-\widehat{DBJ}
Cũng từ BIDE:tgnt\Rightarrow \widehat{JBE}=90^0\Rightarrow \widehat{PBE}=90^0-\widehat{DBJ}
Do đó: \widehat{PBE}=\widehat{PEB}\Rightarrow \triangle PBE cân tại P\qquad (2)
Từ (1),(2)\Rightarrow PX là đường cao cũng là trung tuyến của \triangle PBE\Rightarrow PX vuông góc với BE.
Xét \triangle PXE,EDJ đồng dạng \Rightarrow \displaystyle{\frac{JE}{PE}=\frac{JD}{EX}\Leftrightarrow \frac{JE}{PE}=\frac{2JD}{BE}}\qquad (3)
\triangle AJD,ABE đồng dạng \Rightarrow \displaystyle{\frac{2JD}{BE}=\frac{2AD}{AE}}\qquad (4)
IDCE:tgnt\Rightarrow 2AD.AC=2AI.AE\Leftrightarrow \displaystyle{\frac{AA'}{AC}=\frac{2AD}{AE}}\qquad (5)
Từ (3),(4),(5)\Rightarrow \displaystyle{\frac{JE}{PE}=\frac{AA'}{AC}}, \widehat{JEP}=\widehat{EAC}\Rightarrow \triangle JEP,A'AC đồng dạng \widehat{JA'Q}=\widehat{QJA'}\Rightarrow \triangle QJA' cân tại Q\Rightarrow QJ=QA' \blacksquare