Number Theory

Bài toán  (Đề nghị Olympic 30-4 toán 10 năm 2013 THPT Chuyên Lương Văn Chánh, Phú Yên)

 Cho số nguyên dương $n>1$. Chứng minh rằng $2^{n-1}+1$ không chia hết cho $n$.

Lời giải :

Bổ đề quen thuộc : Cho hai số nguyên dương $a,b$ mà $p\mid a^{2^t}+b^{2^t}$ trong đó $p$ là số nguyên tố mà $p=2^t.s+1,(2\nmid s,t\in {\mathbb{N}}^{\ast })$ thì $a$ và $b$ đồng thời chia hết cho $p$.

Trở lại bài toán :

Dễ thấy $n$ phải lẻ. Ta đặt $n=2^k.A+1(k\in {\mathbb{N}}^{\ast },2\nmid A)$

Gọi $p_i$ là các ước nguyên tố của $n$, vì $p_i$ lẻ nên ta cũng đặt $p_i=2^{t_i}.B_i+1(t\in {\mathbb{N}}^{\ast },2\nmid B_i)$.

Trong các số $p_i$ này ta chọn ra số nguyên tố $p_j=2^{t_j}.B_j+1$ mà $t_j$ là nhỏ nhất.

Để ý ta thấy $n=\prod p_i=\prod \left(2^{t_i}.B_i+1\right)=2^{t_j}.S+1(2\nmid S)$

Do vậy $k=t_j$.

Theo đề bài ta có :

$$2^{n-1}=-1(mod{p}_j)\Rightarrow 2^{2^k.A}\equiv -1(mod{p}_j)$$

Theo định lí $Fermat$ nhỏ ta có :

$2^{p_j-1}$$=1(mod{p}_j)$$\Rightarrow 2^{2^{t_j}.B}$$\equiv 1(mod{p}_j)$$\Rightarrow 2^{2^k.B}$$\equiv 1(mod{p}_j)$

Từ đó có :

$2^{2^k.A}+2^{2^k.B}$$\equiv -1+1$$=0(mod{p}_j)$$\Rightarrow (2^A{)}^{2^k}+(2^B{)}^{2^k}$$\equiv 0(mod{p}_j)$

Theo bổ đề trên ta có :

$$2^A,2^B$$ đồng thời chia hết cho $$p_j$$ và điều này thì vô lí.

Ta có điều phải chứng minh.