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

By

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à \left\{\begin{matrix} m=dm'\\ n=dn' \end{matrix}\right.\;\;gcd(m',n')=1

Ta có a^m-1=a^{dm'}-1\;\vdots \;a^d-1 và a^n-1=a^{dn'}-1\;\vdots \;a^d-1

Gọi d'=gcd(a^m-1,a^n-1) thì d'\;\vdots \;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\;\vdots \;a^{m}-1\;\vdots \;d' và a^{ny}-1\;\vdots \;a^{n}-1\;\vdots \;d'

Do đó (a^{mx}-1)-(a^{ny}-1)\;\vdots \;d'\Rightarrow a^{ny}(a^{mx-ny}-1)\;\vdots\; d'\Rightarrow a^{ny}(a^d-1)\;\vdots \;d'

Nhưng vì a^{ny}-1\;\vdots d'\;\Rightarrow d'\nmid a^{ny}-1

Nên a^{d}-1\;\vdots \;d'\;\;(2)

Từ (1)(2) suy ra a^d-1=d'.

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

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

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

\left\{\begin{matrix} 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{matrix}\right.

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\neq 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.

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

  1. Pingback: Danh sách tổng hợp các bài toán số học | Juliel's Blog

Leave a comment