Number Theory 30

September 20, 2014 by Hoàng Đức Hưng

[Bài toán]: CMR: Với mỗi $n\in \mathbb{Z^+}$ đều chọn được $k\in \mathbb{Z^+}$ để $2^n|19^k-97$
Lời Giải
$\blacktriangleright$ Bổ đề: Với $n\in \mathbb{N}, n\geq 3$ . Khi đó $19^{2^{h-2}}-1=2^ht$ với $t$ lẻ
Ta CM bằng quy nạp.
Với $h=3$ dễ thấy thỏa mãn
Giả sử ta có dpcm với $h=k$ . Do đó có giả thiết quy nạp $19^{2^{k-2}}-1=2^kt$
Ta CM với $h=k+1$ có $19^{2^{k-1}}-1=2^{k+1}l$ với $l$ lẻ
Thật vậy $19^{2^{k-1}}-1=(19^{2^{k-2}}-1)(19^{2^{k-2}}+1)$ .
Mặt khác, $\gcd(19^{2^{k-2}}-1;19^{2^{k-2}}+1=2$ . Kết hợp giả thiết quy nạp $\Rightarrow 19^{2^{k-2}}+1=2s$ với $s$ lẻ
Do đó $19^{2^{k-1}}-1=2^{k+1}st=2^{k+1}l$ với $l$ lẻ. Vậy bổ đề được CM.

$\blacktriangleright$ Áp dụng: Lại sử dụng quy nạp. Giả sử $\forall k=k_n$ đúng. Giả thiết: $19^{k_n}-97=2^nh, h$ lẻ
Ta CM với $k_{n+1}=k_n+2^{n-2}$ , có $19^{k_{n+1}}-97=2^{n+1}m, m$ lẻ.
Với $h$ chẵn, thỏa mãn
Với $h$ lẻ. Ta có: $19^{k_n+1}-97=19^{2^{n-2}}(19^{k_n}-97)+97(19^{2^{n-2}}-1)=2^n(19^{2^{n-2}}h+97g)=2^{n+1}m$

Kết luận: Vậy có $Q.E.D$ $\blacksquare$

Number Theory 29

September 10, 2014 by Hoàng Đức Hưng

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

August 13, 2014 by Hoàng Đức Hưng

[Bài toán]: Cho $a,b,c,d\in \mathbb{Z^+}$ thỏa mãn $a^2+b^2\mid ac+bd$ . CMR: $\gcd(a^2+b^2,c^2+d^2)>1$
Lời giải
Ta có: $(a^2+b^2)(c^2+d^2)=(ac+bd)^2+(ad-bc)^2$
mà $a^2+b^2\mid ac+bd\Rightarrow a^2+b^2\mid (ad-bc)^2$
Giả sử $\gcd(a^2+b^2,c^2+d^2)=1\qquad (*)$
$\blacktriangleright$ Xét $a^2+b^2$ không là số chính phương $\Rightarrow \exists p$ có số mũ lớn nhất là số lẻ, với $p$ là ước nguyên tố của $a^2+b^2$ , gọi số mũ đó là $2k+1$ với $k\in \mathbb{N}$
Ta có: $p^{2k+1}\mid a^2+b^2\Rightarrow p^{2k+1}\mid (ad-bc)^2\Rightarrow p^{2k+2}\mid (ad-bc)^2$ mà $p^{2k+1}\mid ac+bd\Rightarrow p^{2k+2}\mid p^{4k+2}\mid (ac+bd)^2$
$\Longrightarrow p^{2k+2}\mid (ad-bc)^2+(ac+bd)^2\Rightarrow p^{2k+2}\mid (a^2+b^2)(c^2+d^2)$ mà từ $(*)\Rightarrow \gcd(p^{2k+2},c^2+d^2)=1\Rightarrow p^{2k+2}\mid a^2+b^2\rightarrow \text{False}$
$\blacktriangleright$ Xét $a^2+b^2$ là số chính phương. Đặt $a^2+b^2=t^2$ với $t\in \mathbb{Z^+}$
Ta có: $t^2\mid (ad-bc)^2\Rightarrow t\mid ad-bc\Rightarrow ad-bc=ty$ với $y\in \mathbb{Z}$
Lại có: $t^2\mid ac+bd\Rightarrow ac+bd=t^2x$ với $x\in \mathbb{Z^+}$
$\Longrightarrow \begin{cases}a^2d^2-b^2c^2=ty(ad+bc)\\a^2c^2-b^2d^2=t^2x(ac-bd)\end{cases}$ $\Rightarrow (a^2-b^2)(c^2+d^2)=t[y(ad+bc)+x(ac-bd)]\Rightarrow t\mid (a^2-b^2)(c^2+d^2)$ mà $(*)\Rightarrow \gcd(t,c^2+d^2)=1\Rightarrow t\mid a^2-b^2$ $\Rightarrow \left | a^2-b^2 \right |\geq t$
+, Nếu $a^2-b^2\geq t, b^2-a^2\geq t\rightarrow \text{False}$
+, Nếu $a^2=b^2\Rightarrow a=b\Rightarrow 2a^2=t^2\rightarrow \text{False}$
Kết luận: Vậy giả sử sai, ta có $Q.E.D$ $\blacksquare$

Number Theory 22

August 9, 2014 by Hoàng Đức Hưng

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

Number Theory 14

July 9, 2014 by Hoàng Đức Hưng

Cho $a,b\in \mathbb{P}$ sao cho $b\mid a-1,a\mid b^3-1$ .
CMR: $\sqrt{a+b}$ là một số nguyên.
Lời Giải
Ta có: $b\mid a-1$ $\Rightarrow a-1\geq b$ $\Leftrightarrow a\geq b+1$ (vì $a-1>0$ )
Lại có: $a\mid b^3-1$ $\Rightarrow a\mid (b-1)(b^2+b+1)$ mà $a\in \mathbb{P}$ nên ta có $2$ trường hợp sau:
+, Nếu $a\mid b-1$ $\Rightarrow b-1\geq a$ $\Leftrightarrow b\geq a+1\geq b+2$ (vô lí)
+, Nếu $a\mid b^2+b+1$ mà $b^2+b+1>0$ $\Rightarrow b^2+b+1-a\geq 0 (1)$
Ta có: $b\mid a-1, a\mid b^2+b+1$ $\Rightarrow ab\mid (a-1)(b^2+b+1)$
$\Rightarrow ab\mid b^2+b+1-a \qquad (2)$
Từ $(1),(2)$ $\Rightarrow 2$ trường hợp sau:
• Nếu $b^2+b+1-a\geq ab$ $\Leftrightarrow b^2\geq (a-1)(b+1)$
mà $a-1\geq b, b+1>b$ $\Rightarrow (a-1)(b+1)> b^2$ (mâu thuẫn)
• Nếu $b^2+b+1=a$ $\Leftrightarrow \sqrt {a+b}=b+1$
Vậy ta có $Q.E.D$ $\blacksquare$