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

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

$▶$ 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í)

$▶$ Trường hợp $5^{m} - 1$ có ước nguyên tố lẻ.
Ta có: $φ (5^{m} - 1) = 2^{k - 1} \prod_{i = 1}^{h} p_{i}^{α_{i}} \prod_{i = 1}^{h} (p_{i} - 1) = 5^{n} - 1$
Lại có: $g cd (5^{m} - 1, 5^{n} - 1) = 5^{g c d (m, n)} - 1 = 4 (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 Z^{+}, α_{j} > 1 \Rightarrow 5^{m} - 1 \equiv 5^{n} - 1 \equiv 0 (mod p)_{j}$ , mâu thuẫn với $(1)$ . Dẫn tới $a_{i} = 1\forall i = \overline{1, h}$
Ta có: ${5^{m} - 1 = 4 \prod_{i = 1}^{h} p_{i} 5^{n} - 1 = 2 \prod_{i = 1}^{h}$
Vì $4∣∣ 5^{m} - 1 \Rightarrow m$ lẻ. Ta có: $5^{m} \equiv 1 (mod p_{i}) \Leftrightarrow 5^{m + 1} \equiv 5 (mod p_{i})$ $\Rightarrow (\frac{5}{p _{i}}) = 1\forall i = \overline{1, h}$
Theo Luật Thuận nghịch bình phương $G a u ss$ : $(\frac{5}{p _{i}}) (\frac{p _{i}}{5}) = (- 1)^{\frac{( p _{i} - 1 ) ( 5 - 1 )}{4}} = 1$
$\Rightarrow (\frac{p _{i}}{5}) = 1 \Rightarrow p_{1} \equiv \pm 1 (mod 5)$
Nếu $p_{i} \equiv 1 (mod 5) \Rightarrow 5∣ 5^{n} - 1$ (vô lí). Do đó $p_{i} \equiv - 1 (mod 5)$
Ta có: $5^{m} - 1 \equiv 4 \equiv 4 \prod_{i = 1}^{h} p_{i} \equiv 4 (- 1)^{h} (mod 5) \Rightarrow h$ chẵn
$\Rightarrow 5^{n} - 1 \equiv 2^{h + 1} \equiv - 1 (mod 5) \Rightarrow 2^{h + 2} \equiv 3 (mod 5) \Rightarrow (\frac{3}{5}) = 1$ (vô lí)

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

Number Theory 32

Đề bài

Mô tả