Tag Archives: cấp

Number Theory 26

by

(Phát triển từ bài toán Taiwan 1999)
[Bài toán]: Cho b nguyên dương sao cho b+1=q là số nguyên tố. Gọi p là ước nguyên tố lớn nhất của b^y+1,q là ước nguyên tố nhỏ nhất của y. CMR: p\geq q+2.
                                                Lời giải
Phản chứng, nếu p\geq q, gọi \text{ord}_pb=h\qquad (h\in \mathbb{Z^+}) \qquad (1)
ta có: p|b^y+1\Leftrightarrow b^{2y}\equiv 1\pmod p \Longrightarrow h|2y\qquad (2)
Từ (1)\Rightarrow h|p-1\Rightarrow p-1\geq h\Leftrightarrow p\geq h+1;p\leq q\Rightarrow h+1\leq q\Rightarrow h<q\Rightarrow \gcd(y,h)=1\qquad (3)
Từ (2),(3)\Rightarrow h|2\Rightarrow h\in \{1;2\}
• Xét h=1\Rightarrow p|b-1. Ta có: p|b^y+1\Rightarrow p|2\Rightarrow p|2\Rightarrow p=2\Rightarrow b lẻ \Rightarrow q chẵn \Rightarrow q=2 (vô lí)
• Xét h=2\Rightarrow p|(b-1)(b+1)\Leftrightarrow p|q(q-2). Nếu \gcd(q,q-2)>1\Rightarrow q chẵn \Rightarrow q=2 (vô lí) \Longrightarrow \gcd(q,q-2)=1. Nếu p|q-2\Rightarrow p|b-1\Rightarrow q=2 (vô lí) \Longrightarrow p|q\Rightarrow q=p mà p là ước nguyên tố lớn nhất của b^y+1
\Rightarrow q là ước duy nhất của b^y+1. Đặt b^y+1=q^n với n\in \mathbb{Z^+}
Ta có phương trình: (q-1)^y+1=q^n\Rightarrow (q-1)^{2y}\equiv 1\pmod {q^n}. Đặt \text{ord}_{q^n}q-1=h với h\in \mathbb{Z^+}
\Rightarrow h|2y mà \text{ord}_q(q-1)=2\Rightarrow \text{ord}_{q^n}q-1=2q^{n-1}\Rightarrow 2q^{n-1}|2y \Leftrightarrow q^{n-1}|y\Rightarrow q|y. Đặt y=kq với k\in \mathbb{Z^+}
Dễ dàng thấy y lẻ, nếu y chẵn \Rightarrow q|2\Rightarrow q=2 (vô lí)
\Longrightarrow k lẻ. Ta thấy q^n=(q-1)^y+1=[(q-1)^q]^k+1=[(q-1)^q+1].A\vdots (q-1)^q+1 mà q\in \mathbb{P}\Rightarrow \exists m\in \mathbb{Z^+}:(q-1)^q+1=q^m
Vì q\geq 5\Rightarrow (q-1)^q+1\geq (q-1)^5+1\geq q^3\Rightarrow q^m\geq q^3\Leftrightarrow m\geq 3
Ta có: (q-1)^q+1=q^q-\text{C}_p^1q^{q-1}+...+q^2\equiv q^2\pmod {q^3} mà q^m\equiv 0\pmod {q^3}\forall m\geq 3\Rightarrow VT\neq NP (mâu thuẫn). Vậy giả thiết phản chứng sai \Rightarrow p>q mà p,q nguyên tố \Rightarrow p\geq q+2
Kết luận: Vậy ta có Q.E.D \blacksquare

Number Theory 22

by

(USA Team Selected Test 2003)
[Bài toán]: Tìm bộ ba số nguyên tố p,q,r thỏa mãn điều kiện: p\mid q^r+1,q\mid r^p+1,r\mid p^q+1
                                                                     Lời Giải
\blacktriangleright Bổ đề: Cho a,b,c\in \mathbb{P},c lẻ sao cho c\mid a^b+1 thì 2b\mid c-1;c\mid a^2-1
\rightarrow CM: Đặt d=\text{ord}_c(a)\qquad (d\in \mathbb{Z^+})
Ta có: c\mid a^b+1;c>2\Rightarrow a^b\equiv -1\pmod c,a^{2b}\equiv 1\pmod c
\Rightarrow d\mid 2b;d\mid b\Rightarrow d\in \{2;2b\}
+, Với d=2b mà d\mid c-1 (vì \text{ord}_c(a)\mid \phi(c)=c-1 do c\in \mathbb{P}) \Rightarrow 2b\mid c-1
+, Với d=2\Rightarrow a^2\equiv 1\pmod c\Rightarrow c\mid a^2-1
\blacktriangleright Áp dụng:
(*) Nếu có ít nhất 2 số bằng nhau, dễ dàng ta thấy điều vô lí!
(*) Không mất tính tổng quát, giả sử r<p<q
+, Nếu cả p,q,r đều lẻ. Ta có: q\mid r^p+1 \Rightarrow \begin{cases} 2p\mid q-1\\q\mid r^2-1\end{cases} \Rightarrow \begin{cases} q-1\geq 2p\\q\mid (r-1)(r+1)\end{cases}
Dễ dàng thấy trường hợp thứ nhất vô lí vì q<p
Ở trường hợp thứ hai, ta thấy \gcd(r-1;r+1)=2,p\in \mathbb{P}\Rightarrow q\mid \displaystyle{\frac{r-1}{2}} hoặc q\mid \displaystyle{\frac{r+1}{2}} mà q<\displaystyle{\frac{r-1}{2}<\frac{r+1}{2}}<r (trái với giả thiết nên trường hợp này loại)
+, Nếu trong 3 số có 1 số chẵn mà r<q<p\Rightarrow r=2
Ta có: r\mid p^q+1\Rightarrow \begin{cases}4=2q\mid r-1\\r\mid p^2-1\end{cases} p\mid q^r+1\Rightarrow \begin{cases} 2r\mid p-1\\p\mid q^2-1\end{cases} \Leftrightarrow p\mid 3\Rightarrow p=3
\Rightarrow r\mid 10 mà p\in \mathbb{P}\Rightarrow r\in \{2;5\} mà r>2\Rightarrow r=5 (Thử lại thỏa mãn)
Vậy (p,q,r)=(2;3;5) và hoán vị thỏa mãn ycđb \blacksquare