Number Theory 26

(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\ge q+2$.
                                                Lời giải
Phản chứng, nếu $p\ge q$, gọi ${\text{ord}}_{p}b=h(h\in {\mathbb{Z}}^{+})(1)$
ta có: $p|b^y+1\iff b^{2y}\equiv 1(\mathrm{mod}p)$ $⟹h|2y(2)$
Từ $(1)\Rightarrow h|p-1\Rightarrow p-1\ge h\iff p\ge h+1;p\le q\Rightarrow h+1\le q\Rightarrow h<q\Rightarrow \gcd (y,h)=1(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)\iff p|q(q-2)$. Nếu $\gcd (q,q-2)>1\Rightarrow q$ chẵn $\Rightarrow q=2$ (vô lí) $⟹\gcd (q,q-2)=1$. Nếu $p|q-2\Rightarrow p|b-1\Rightarrow q=2$ (vô lí) $⟹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(\mathrm{mod}{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$ $\iff 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í)
$⟹k$ lẻ. Ta thấy $q^n=(q-1{)}^y+1=[(q-1{)}^q{]}^k+1=[(q-1{)}^q+1].A⋮(q-1{)}^q+1$ mà $q\in \mathbb{P}\Rightarrow \exists m\in {\mathbb{Z}}^{+}:(q-1{)}^q+1=q^m$
Vì $q\ge 5\Rightarrow (q-1{)}^q+1\ge (q-1{)}^5+1\ge q^3\Rightarrow q^m\ge q^3\iff m\ge 3$
Ta có: $(q-1{)}^q+1=q^q-{\text{C}}_p^1{q}^{q-1}+...+q^2\equiv q^2(\mathrm{mod}{q}^3)$ mà $q^m\equiv 0(\mathrm{mod}{q}^3)\forall m\ge 3\Rightarrow VT\ne 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\ge q+2$
Kết luận: Vậy ta có $Q.E.D$ $■$