[Bài toán] Ứng dụng định lí phần dư Trung Hoa

Bài toán : Chứng minh rằng với mọi số nguyên dương $n$ luôn tồn tại một dãy gồm $n$ số nguyên liên tiếp sao cho bất kì số nào trong dãy cũng đều có ước dạng $2^k-1$.

Lời giải :

Bổ đề : Với $m,n$ là các số nguyên dương và $a$ là số nguyên dương khác $1$ thì ta có $gcd(a^m-1,a^n-1)=a^{gcd(m,n)}-1$

Chứng minh bổ đề :

Đặt $d=gcd(m,n)$ và $\{\begin{array}{c}m=d{m}^{\prime }\\ n=d{n}^{\prime }\end{array}gcd(m^{\prime },n^{\prime })=1$

Ta có $a^m-1=a^{d{m}^{\prime }}-1⋮a^d-1$ và $a^n-1=a^{d{n}^{\prime }}-1⋮a^d-1$

Gọi $d^{\prime }=gcd(a^m-1,a^n-1)$ thì $d^{\prime }⋮a^d-1(1)$

Vì $d=gcd(m,n)$ nên theo định lí $Bezout$ thì tồn tại hai số nguyên dương $x,y$ sao cho $mx-ny=1$

Từ đó $a^{mx}-1⋮a^m-1⋮d^{\prime }$ và $a^{ny}-1⋮a^n-1⋮d^{\prime }$

Do đó $(a^{mx}-1)-(a^{ny}-1)⋮d^{\prime }\Rightarrow a^{ny}(a^{mx-ny}-1)⋮d^{\prime }\Rightarrow a^{ny}(a^d-1)⋮d^{\prime }$

Nhưng vì $a^{ny}-1⋮d^{\prime }\Rightarrow d^{\prime }\nmid a^{ny}-1$

Nên $a^d-1⋮d^{\prime }(2)$

Từ $(1)(2)$ suy ra $a^d-1=d^{\prime }$.

Bổ đề chứng minh hoàn tất.

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

Xét hệ đồng dư tuyến tính :

$$\{\begin{array}{c}x\equiv -1(mod{2}^{p_1}-1)\\ x\equiv -2(mod{2}^{p_2}-1)\\ ....\\ x\equiv -n(mod{2}^{p_n}-1)\end{array}$$

Với $p_1,p_2,...,p_n$ là các số nguyên tố phân biệt

Theo bổ đề ta có $gcd(2^{p_i}-1,2^{p_j-1})=2^{gcd(p_i,p_j)}-1=2-1=1$ với mọi $i\ne j,i,j\in \left\{1,2,...,n\right\}$

Từ đó theo định lí phần dư Trung Hoa thì hệ này có nghiệm.

Suy ra điều cần chứng minh.