Số chính phương modulo p | .: Hoang Hung Chelski 's Blog :.

(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$

(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í)