[tex]\begin{array}{l} \mathtt{{\textstyle \ ( Ký\ hiệu\ b\ |\ a\ tức\ b\ là\ ước\ của\ a)}}\\ \mathtt{{\textstyle I.Lý\ thuyết\ về\ ước\ chung\ lớn\ nhất\ ( \ The\ greatest\ common\ divisor)}}\\ \mathtt{{\textstyle 1.1.\ Định\ nghĩa}}\\ \mathtt{{\textstyle -\ Cho\ một\ số\ nguyên\ k\ bất\ kỳ,gọi\ tập\ D_{k} \ là\ các\ ước\ nguyên\ dương\ của\ k\ sao\ cho\ mỗi\ phần\ tử\ d_{n}}}\\ \mathtt{{\textstyle trong\ tập\ đều\ thỏa\ d_{n} \ |\ k.Dễ\ thấy\ tập\ D_{k} \ là\ một\ tập\ hữu\ hạn}}\\ \mathtt{{\textstyle -Với\ mỗi\ số\ nguyên\ dương\ m,n\ thì\ phần\ tử\ lớn\ nhất\ của\ D_{m} \ \cap \ D_{n} \ được\ gọi\ là\ ước\ chung\ lớn\ nhất\ của}}\\ \mathtt{{\textstyle m\ và\ n.Ta\ có\ thể\ ký\ hiệu\ max\ \{\ D_{m} \ \cap \ D_{n}\} \ =\ gcd( m,n) \ hoặc\ cho\ thuận\ thiện\ thì\ ta\ ký\ hiệu\ ( m,n)}}\\ \mathtt{{\textstyle -Trong\ trường\ hợp\ D_{m} \cap D_{n} =\{1\} \ thì\ ta\ nói\ hai\ số\ ( m,n) \ nguyên\ tố\ cùng\ nhau\ }}\\ \mathtt{{\textstyle 1.2\ Tính\ chất}}\\ \mathtt{{\textstyle a) \ Nếu\ d\ =\ ( m,n) \ thì\ m=d.m'\ và\ n=d.n'\ ,\ khi\ đó\ ( m',n') =1}}\\ \mathtt{{\textstyle Chứng\ minh\ :}}\\ \mathtt{{\textstyle Giả\ sử\ ( m',n') =k\ >1\ thì\ khi\ đó\ m'=k.m''\ và\ n'=k.n''}}\\ \mathtt{{\textstyle Khi\ đó\ m=m'.d=d.k.m''\ và\ n\ =n'.d=d.k.n''}}\\ \mathtt{{\textstyle Nhận\ thấy\ d.k\ \in \ D_{m} \ \cap \ D_{n} \ mà\ d.k\ >\ d\ vì\ k\ >\ 1\ tức\ còn\ tồn\ tại\ 1\ ước\ khác\ lớn\ hơn\ d\ mà\ d\ =\ ( m,n)}}\\ \mathtt{{\textstyle \Longrightarrow \ Vô\ lý\ vậy\ ( m',n') =1}}\\ \mathtt{{\textstyle b) Nếu\ d=( m,n) \ ,\ m=d'.m''\ ,\ n=d'.n''\ và\ ( m'',n'') =1\ thì\ d=d'}}\\ \mathtt{{\textstyle c) Nếu\ d'\ là\ một\ ước\ chung\ của\ m\ và\ n\ thì\ d'\ |\ ( m,n)}}\\ \mathtt{{\textstyle d) \ Nếu\ m=nq+r\ thì\ \ ( m,n) =( n,r)}}\\ \mathtt{{\textstyle Chứng\ minh\ :}}\\ \mathtt{{\textstyle Đặt\ d=( m,n) \ và\ d'=( n,r) \ khi\ đó\ ta\ có:}}\\ \mathtt{{\textstyle Bởi\ vì\ d\ |\ n\ và\ \{\ d'\ |\ n\ ,\ d'\ |\ r\ \} \ nên\ d\ |\ r}}\\ \mathtt{{\textstyle Mặt\ khác\ vì\ d'\ |\ r\ và\ d\ |\ r\ nên\ d'\ |\ m,vì\ vậy\ d'\ |\ d}}\\ \mathtt{{\textstyle 2.1\ Thuật\ toán\ Euclid}}\\ \mathtt{{\textstyle -Thuật\ toán\ Bezout\ được\ ứng\ dụng\ để\ tìm\ gcd( m,n) \ khi\ m\ \not{\vdots } n}}\\ \mathtt{{\textstyle -\ Thuật\ toán\ được\ biểu\ diễn\ như\ sau\ }}\\ \mathtt{{\textstyle \ \ \ \ \ \ \ m=nq_{1} +r_{1}}}\\ \mathtt{{\textstyle \ \ \ \ \ \ \ n=r_{1} q_{2} +r_{2}}}\\ \mathtt{{\textstyle \ \ \ \ \ \ \ r_{1} =r_{2} .q_{3} +r_{3}}}\\ \mathtt{{\textstyle \ \ \ \ \ \ \ ....}}\\ \mathtt{{\textstyle \ \ \ \ \ \ \ r_{k-2} =r_{k-1} q_{k} +r_{k}}}\\ \mathtt{{\textstyle \ \ \ \ \ \ \ r_{k-1} =r_{k} q_{k+1} +r_{k+1}}}\\ \mathtt{{\textstyle Chuổi\ đẳng\ thức\ trên\ là\ hữu\ hạn\ vì\ n >r_{1} >r_{2} >... >r_{k}}}\\ \mathtt{{\textstyle Thuật\ toán\ dừng\ lại\ r_{k} \ là\ số\ dư\ cuối\ cùng\ khác\ 0\ trong\ thuật\ toán\ nên\ \ ( m,n) =r_{k}}}\\ \mathtt{{\textstyle Hay\ ( m,n) =( n,r_{1}) =( r_{1} ,r_{2}) =...=( r_{k-1} ,r_{k}) =r_{k}}}\\ \mathtt{{\textstyle 2.2\ Bổ\ đề\ Bezout\ }}\\ \mathtt{{\textstyle Bổ\ đề\ như\ sau\ :\ \forall m,n\ \in Z^{+} \ tồn\ tại\ ít\ nhất\ một\ cặp\ số\ nguyên\ a\ và\ b\ thỏa\ am+bn=( m,n)}}\\ \\ \end{array}[/tex]
[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
