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

(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ổ đề:
$▶$ Bổ đề 1: Với $a, b \in Z^{+}, g cd (a, b) = 1$ . Cho $p$ là ước nguyên tố lẻ của $a^{6^{n}} + b^{6^{n}}$ . CMR: $p \equiv 1 (mod 2^{n + 1})$
Chứng minh: Vì $p ∣ a^{6^{n}} + b^{6^{n}} \Rightarrow a^{6^{n}} + b^{6^{n}} = tp (t \in Z^{+})$
Viết $p = 2^{m} v + 1 (m, v \in Z^{+}, v$ lẻ
Xét $m < n + 1$ . Theo định lí $F er ma t$ nhỏ vì $g cd (a, p) = g cd (b, p) = 1$
Ta có: $(a^{3^{m} . 2^{n - m}})^{p - 1} \equiv (b^{3^{n - m} . 2^{m}}) \equiv 1 (mod p)$
$\Leftrightarrow (a^{6^{n}})^{2^{m} v} \equiv (b^{6^{n}})^{2^{m} v} \equiv 1 (mod p) \Leftrightarrow (a^{6^{n}})^{v} \equiv (b^{6^{n}})^{v} \equiv 1 (mod p)$ $(1)$
Lại có: $(a^{6^{n}})^{v} = (tp - b^{6^{n}})^{v} \equiv - (b^{6^{n}})^{v} (mod p) (2)$
Từ $(1), (2) \Rightarrow 2 (b^{6^{n}})^{v} \equiv 0$ (vô lí)
Do đó $m \geq n + 1 \to p = 2^{m} v + 1 \equiv 1 (mod 2)^{n + 1} \to Q . E . D$

$▶$ Bổ đề 2: Cho $x, c, m, k \in Z^{+}$ thỏa $x \equiv 1 (mod c^{k})$ .
CMR: $x^{c^{m}} \equiv 1 (mod c^{k + m})$
Chứng minh: Vì $x \equiv 1 (mod c^{k}) \Rightarrow x - 1 = t c^{k}$
Ta có: $x^{c^{m}} = (t c^{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$

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

Number Theory 29

Đề bài

Mô tả