Toán 8 Bổ đề Bezout và modulo nghịch đảo

[K.o.w]

[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!

ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.

Topic này mình tạo ra để ae cùng nhau chia sẻ các bài toán hay liên quan tới chủ đề trên.Đặc biệt là modulo nghịch đảo vì tính chất của nó có thể ứng dụng để đi giải hệ phương trình đồng dư thức

 

[K.o.w]

[tex]\begin{array}{l} \mathtt{I.Bổ\ đề\ Bezout}\\ \mathtt{-Bổ\ đề\ phát\ biểu\ như\ sau\ :\ Nếu\ d=( a,b) \ thì\ sẽ\ tồn\ tại\ ít\ nhất\ 1\ cặp\ số\ ( x,y) \ thỏa\ mãn\ }\\ \mathtt{d=ax+by}\\ \mathtt{-Phương\ trình\ trên\ được\ gọi\ là\ đồng\ nhất\ thức\ Bezout\ và\ các\ số\ x,y\ được\ gọi\ là\ hệ\ số\ Bezout}\\ \mathtt{Để\ tìm\ được\ các\ hệ\ số\ như\ trên\ ta\ cần\ sử\ dụng\ thuật\ toán\ Euclid\ mở\ rộng.Thuật\ toán\ Euclid\ như\ sau\ :}\\ \mathtt{-\ Nếu\ d=( a,b) \ thì\ d\ =\ ( a,b\bmod a) \ =( b,a\bmod b)}\\ \mathtt{Tức\ nếu\ b=aq+r\ thì\ d=( a,b) =( b,r)}\\ \mathtt{a\bmod b\ là\ phép\ chia\ lấy\ dư\ của\ a\ cho\ b\ }\\ \mathtt{II.Một\ số\ ví\ dụ\ }\\ \mathtt{Tìm\ hệ\ số\ Bezout\ cho\ các\ cặp\ số\ ( a,b) \ sau\ }\\ \mathtt{1) \ ( 252,198)}\\ \mathtt{2) \ ( 45,155)}\\ \mathtt{Bài\ làm\ :\ }\\ \mathtt{1) \ Ta\ có\ :}\\ \mathtt{252\ =\ 198\ *\ 1\ +\ 54}\\ \mathtt{198=\ 54\ *3\ +\ 36}\\ \mathtt{54=36\ *\ 1\ +18}\\ \mathtt{36\ =\ 18\ *2\ +0\ }\\ \mathtt{Vậy\ ( 252,198) =18.\ Đây\ là\ bước\ quan\ trọng\ :\ Ta\ đi\ ngược\ từ\ dưới\ lên\ để\ tìm\ được\ hệ\ số\ x,y\ thỏa}\\ \mathtt{Ta\ có\ :\ }\\ \mathtt{18=54-36*1}\\ \mathtt{18=54-( 198-54*3) =54*4-198}\\ \mathtt{18=( 252-198*1) *4-198=252*4-198*3\ }\\ \mathtt{Vậy\ ( x,y) =( 4,-3)}\\ \mathtt{2) \ ( 45,155)}\\ \mathtt{Ta\ có}\\ \mathtt{155=45*3+20}\\ \mathtt{45=20*2+5}\\ \mathtt{20=5*4+0}\\ \mathtt{Vậy\ gcd( 45,155) =5.Sử\ dụng\ phương\ pháp\ tương\ tự\ ta\ được}\\ \mathtt{5=45-20*2}\\ \mathtt{5=45-( 155-45*3) *2}\\ \mathtt{5=45*7-155*2}\\ \mathtt{Vậy\ ( x,y) =( 7,-2)}\\ \end{array}[/tex]

 

[Hồng Vânn]

Hihi, mình cũng góp vui ! ^^
Những định lý cần lưu ý của phương trình đồng dư:

1. Nghịch đảo của a theo modulo m tồn tại duy nhất khi và chỉ khi a nguyên tố cùng nhau với m.
2. Gọi d là một ước của m. Nếu x là một nghiệm của phương trình đồng dư f(x) đồng dư với 0 theo mod m thì x cũng là nghiệm của pt đồng dư f(x) đồng dư với 0 theo mod d.
3. Phương trình đồng dư tuyến tính : Cho a,m là các số nguyên và m>0, d= gcd(a,m). ĐK cần đủ để phương trình ax + b đồng dư với 0( mod m) có nghiệm là d | b. Nếu đk này thỏa mãn thì pt có d nghiệm phân biệt lập thành một cấp số cộng với công sai m/d

Còn nhiều lắm luôn !

 

[K.o.w]

[tex]\begin{array}{l} \mathtt{( *) \ Định\ lý\ phần\ dư\ Trung\ Hoa}\\ \mathtt{Định\ lý\ trên\ dùng\ để\ giải\ hệ\ phương\ trình\ đồng\ dư\ bậc\ nhất\ có\ dạng\ như\ sau\ }\\ \mathtt{\begin{cases} x\equiv a_{1} & ( mod\ m_{1})\\ x\equiv a_{2} & ( mod\ m_{2})\\ ... & \\ x\equiv a_{n} & ( mod\ m_{n}) \end{cases} \ }\\ \mathtt{Phương\ trình\ trên\ có\ nghiệm\ khi\ và\ chỉ\ khi\ gcd( m_{1} ,m_{2} ,...m_{n}) =1}\\ \mathtt{Nội\ dung\ định\ lý:}\\ \mathtt{( *) \ Hệ\ phương\ trình\ đồng\ dư\ bậc\ nhất\ nói\ trên\ chỉ\ có\ một\ nghiệm\ duy\ nhất\ theo\ modun\ M\ trong\ đó}\\ \mathtt{\ \ \ \ \ \ \ \ M=m_{1} m_{2} ...m_{n}}\\ \mathtt{Trong\ đó\ nghiệm\ x\ được\ biểu\ diễn\ như\ sau\ :}\\ \mathtt{x\equiv a_{1} .M_{1} .y_{1} +a_{2} .M_{2} .y_{2} +...+a_{n} .M_{n} .y_{n}}\\ \mathtt{Và\ với}\\ \mathtt{\begin{cases} M_{1} =\frac{M}{m_{1}} ,...,M_{n} =\frac{M}{m_{n}} & \\ y_{1} ,y_{2} ,...y_{n} \ lần\ lượt\ là\ modulo\ nghịch\ đảo\ theo\bmod m_{1} \ của\ M_{1} & \end{cases}}\\ \mathtt{Tức\ y_{1} .M_{1} \equiv 1\ ( mod\ m_{1})}\\ \mathtt{Như\ bạn\ trên\ đã\ nói\ thì\ để\ lấy\ được\ modulo\ nghịch\ đảo\ bắt\ buộc\ ( M_{1} ,m_{1}) =1}\\ \mathtt{Vì\ :\ Giả\ sử\ ta\ có\ x\ là\ nghịch\ đảo\ modulo\ của\ a\ theo\bmod b\ thì\ khi\ đó}\\ \mathtt{ax\equiv 1\ ( mod\ b) \ \Longrightarrow \ ax-1\vdots b\ \Longrightarrow ax-1=by}\\ \mathtt{\Longrightarrow ax-by=1}\\ \mathtt{Đây\ là\ đồng\ nhất\ thức\ bezout\ cho\ hai\ số\ a\ và\ b\ có\ gcd( a,b) =1}\\ \mathtt{Mình\ cũng\ xin\ giới\ thiệu\ luôn\ cách\ để\ lấy\ nghịch\ đảo\ bằng\ Thuật\ toán\ Euclid}\\ \mathtt{( *) Tìm\ nghịch\ đảo\ modulo\ của\ 35\ theo\bmod 3\ tức\ tìm\ một\ số\ x\ sao\ cho\ }\\ \mathtt{35x\equiv 1(\bmod 3\ )}\\ \mathtt{Bài\ làm\ :}\\ \mathtt{Thực\ hiện\ thao\ tác\ lấy\ gcd( 35,3)}\\ \mathtt{35=3*11+2}\\ \mathtt{3=2*1+1}\\ \mathtt{2=1*1+0}\\ \mathtt{\Longrightarrow \ gcd( 35,3) =1( thỏa)}\\ \mathtt{Tiếp\ tục\ ta\ đưa\ về\ đồng\ nhất\ thức\ Bezout}\\ \mathtt{1=3-2*1=3-( 35-3*11) =3*12-35*1}\\ \mathtt{Vậy\ x=( -1)}\\ \mathtt{Thử\ lại\ :-35\equiv 1\ ( mod\ 3)}\\ \mathtt{Một\ số\ VD\ }\\ \mathtt{VD1\ :\ Giải\ hệ\ phương\ trình\ đồng\ dư\ sau\ :}\\ \mathtt{\begin{cases} x\equiv 4 & ( mod\ 5\ )\\ x\equiv 2 & ( mod\ 7\ )\\ x\equiv 3 & ( mod\ 13) \end{cases}}\\ \mathtt{Bài\ làm:}\\ \mathtt{Ta\ có\ M=5*7*13=455}\\ \mathtt{\Longrightarrow \ M_{1} =91,M_{2} =65,M_{3} =35}\\ \mathtt{Ta\ đi\ tìm\ các\ số\ nghịch\ đảo\ modulo\ của\ từng\ trường\ hợp}\\ \mathtt{Xét\ y_{1} M_{1} \equiv 1\ (\bmod 5) \ \Longrightarrow \ 91y_{1} \equiv 1\ (\bmod 5)}\\ \mathtt{Làm\ tương\ tự\ như\ trên\ mọi\ người\ sẽ\ tìm\ được\ gcd( 91,5) =1\ và\ có\ được\ đồng\ nhất\ thức\ 91-5*18=1}\\ \mathtt{\Longrightarrow \ y_{1} =1}\\ \mathtt{Tương\ tự\ }\\ \mathtt{\begin{cases} 65y_{2} \equiv 1 & ( mod\ 7)\\ 35y_{3} \equiv 1 & ( mod\ 13) \end{cases} \Longrightarrow \begin{cases} y_{2} =-3 & \\ y_{3} =3 & \end{cases}}\\ \mathtt{Do\ đó}\\ \mathtt{x\equiv 4*91*1+( -3) *65*2+3*35*3\ ( mod\ 455)}\\ \mathtt{\Longrightarrow \ x\equiv 289\ ( mod\ 455)}\\ \mathtt{\Longrightarrow \ x=455k+289\ với\ k\ nguyên\ }\\ \mathtt{Một\ số\ bài\ tập\ vận\ dụng\ }\\ \mathtt{Tìm\ nghiệm\ của\ các\ hệ\ phương\ trình\ đồng\ dư\ sau\ }\\ \mathtt{1)\begin{cases} x\equiv 2 & (\bmod 3)\\ x\equiv 3 & (\bmod 5\ )\\ x\equiv 5 & (\bmod 7) \end{cases}}\\ \mathtt{2) \ \begin{cases} x\equiv 3 & ( mod\ 4)\\ x\equiv 4 & ( mod\ 5)\\ x\equiv 5 & ( mod\ 7) \end{cases}}\\ \mathtt{3) \ \begin{cases} x\equiv 4 & ( mod\ 5)\\ x\equiv 2 & ( mod\ 7)\\ x\equiv 3 & ( mod\ 13) \end{cases}} \end{array}[/tex]