Ước chung lớn nhất, bội chung nhỏ nhất

Chọn $x_1;\,x_2;\, \ldots ;\, x_n$ là $n$ số nguyên bất kì. Ta kí hiệu $\min\left(x_1;\,x_2;\, \ldots ;\, x_n\right)$ và $\max\left(x_1;\,x_2 \ldots ;\, x_n\right)$ lần lượt là số nhỏ nhất và số lớn nhất trong các số $x_1;\,x_2;\, \ldots ;\, x_n$ đó. Định lý nêu ra sau đây là hiển nhiên.

Định lý 6.1. Với $a,\,b$ là hai số nguyên dương và $p_1,\,p_2,\,\ldots,p_s$ là những ước nguyên tố thì, lúc đó ta có thể viết
\[\begin{align*}
a &= p_1^{{a_1}}p_2^{{a_2}} \ldots p_s^{{a_s}},\quad {a_v} \ge 0,\\ \\
b &= p_1^{{b_1}}p_2^{{b_2}} \ldots p_s^{{b_s}},\quad {b_v} \ge 0,\,{\mkern 1mu} {\mkern 1mu} {\mkern 1mu} {\mkern 1mu} {p_1} < {p_2} < \ldots {p_s}.
\end{align*}\] Lúc đó ta sẽ có được\[\gcd(a,\,b)=p_1^{c_1}p_2^{c_2}\ldots p_s^{c_s}\]
Trong đó $c_v=\min(a_v,\,b_v),$ $1 \le v \le s.$

Định nghĩa. Với $a,\,b$ là hai số nguyên dương. Số nguyên là bội của cả $a$ và $b$ gọi là bội chung nhỏ nhất của $a$ và $b$. Từ $ab$ chắc chắn là số bội chung nguyên dương của $a$ và $b$, bội chung nhỏ nhất của $a$ và $b$ luôn luôn tồn tại.

Định lý 6.2. Dưới những giả thiết của Định lý 6.1, bội chung nhỏ nhất của $a$ và $b$ được cho bởi \[e=p_1^{e_1}p_2^{e_2}\ldots p_s^{e_s}\] trong đó $e_v=\max(a_v,\,b_v),\, 1 \le v \le s.$

Chứng minh. Rõ ràng rằng cả $a$ và $b$ đều là ước của $e$. Tuy nhiên, nếu \[e’=p_1^{e_1}p_2^{e_2}\ldots p_s^{m_s}\] là bội của $a$, lúc đó $a_v \le m_v.$ Từ đó, nếu $e’$ là bội của cả $a$ và $b,$ lúc đó $a_v \le m_v$ và $b_v \le m_v,$ và ta có $\max(a_v,\,b_v) \le m_v.$ Vì thế $e\mid e’$. Nên ta có điều phải chứng minh.

$\square$

Định lý 6.3. Mọi bội chung bất kì của $a$ và $b$ là một bội của bội chung nhỏ nhất của $a$ và $b$.

Định lý lý 6.4. Chúng ta kí hiệu $\text{lcm}(a,\,b)$ là bội chung nhỏ nhất của $a$ và $b$. Lúc đó \[\text{lcm}(a,\,b)\gcd(a,\,b)=ab.\]

Chứng minh. Viết \[a=p_1^{a_1}p_2^{a_2}\ldots p_s^{a_s},\quad b=p_1^{b_1}p_2^{b_2}\ldots p_s^{b_s},\quad p_1<p_2<\ldots<p_s.\] Lúc đó \[ab=p_1^{a_1+b_1}p_2^{a_2+b_2}\ldots p_s^{a_s+b_s}.\] Cũng có \[\text{lcm}(a,\,b)\gcd(a,\,b)=p_1^{\max(a_1,\,b_1\min(a_1,\,b_1)}p_2^{\max(a_2,\,b_2\min(a_2,\,b_2)}\ldots p_s^{\max(a_s,\,b_s\min(a_s,\,b_s)}\] Mà ta luôn có \[x+y=\max(x,\,y)+\min(x,\,y,).\] Từ đó định lý được chứng minh hoàn toàn.

$\square$

Giờ chúng ta xác định ước chung lớn nhất và bội chung nhỏ nhất như sau: Với $a_1,\,a_2,\,\ldots,\,a_n$ là những số nguyên. Lúc đó ước chung lớn nhất của chúng là số \[\gcd(a_1,\,a_2,\,\ldots,\,a_n)=\gcd(\gcd(a_1,\,a_2,\,\ldots,\,a_{n-1}),\,a_n),\] và bội chung nhỏ nhất là số \[\text{lcm}(a_1,\,a_2,\,\ldots,\,a_n)=\text{lcm}(\text{lcm}(a_1,\,a_2,\,\ldots,\,a_{n-1}),\,a_n).\]

Định lý 6.5. Với \[a_1=p_1^{e_{11}}p_2^{e_{12}}, \quad \ldots,\quad a_n=p_1^{e_{n1}}p_1^{e_{n2}}\ldots p_1^{e_{ns}},\] \[p_1<p_2<\ldots<p_s,\quad e_{\mu v} \ge 0. \]
Lúc đó \[\gcd(a_1,\,a_2,\,\ldots,\,a_n)=p_1^{e_1}p_2^{e_2}\ldots p_s^{e_s},\quad e_v=\min(e_{1v},\,a_{2v},\,\ldots,\,a_{nv}),\] \[\text{lcm}(a_1,\,a_2,\,\ldots,\,a_n)=p_1^{d_1}p_2^{d_2}\ldots p_s^{d_s},\quad d_v=\min(e_{1v},\,a_{2v},\,\ldots,\,a_{nv}).\]

Bài tập 1. Chứng minh hai đẳng thức sau \[\gcd(a_1,\,a_2,\,\ldots,\,a_n)=\gcd(\gcd(a_1,\,a_2,\,\ldots,\,a_s),\,(\gcd(a_{s+1},\,a_2,\,\ldots,\,a_n))),\] \[\text{lcm}(b_1,\,b_2,\,\ldots,\,b_n)=\text{lcm}(\text{lcm}(b_1,\,b_2,\,\ldots,\,b_s),\,\text{lcm}(b_{s+1},\,b_2,\,\ldots,\,b_n)).\]

Bài tập 2. Chứng minh hai đẳng thức sau
\[\begin{align*}
\gcd ({a_1},{\mkern 1mu} {a_2},{\mkern 1mu} \ldots ,{\mkern 1mu} {a_n}) &= \dfrac{{{a_1}{a_2} \ldots {a_n}}}{\text{lcm}{\left( {{a_2} \ldots {a_n},\,{a_1}{a_3} \ldots {a_n},\, \ldots ,\,{a_1} \ldots {a_{n – 1}}} \right)}} \\ \\ \text{lcm}({a_1},{\mkern 1mu} {a_2},{\mkern 1mu} \ldots ,{\mkern 1mu} {a_n}) &= \dfrac{{{a_1}{a_2} \ldots {a_n}}}{{\gcd \left( {{a_2} \ldots {a_n},\,{a_1}{a_3} \ldots {a_n},\, \ldots ,\,{a_1} \ldots {a_{n – 1}}} \right)}}.
\end{align*}\]

Bài tập 3. Với ${a_1},{\mkern 1mu} {a_2},{\mkern 1mu} \ldots ,{\mkern 1mu} {a_n}$ là $n$ số nguyên. Lúc đó $\gcd ({a_1},{\mkern 1mu} {a_2},{\mkern 1mu} \ldots ,{\mkern 1mu} {a_n})$ là số nguyên dương lớn nhất trong modulus của những số nguyên dạng $$a_1x_1+a_2x_2+\ldots+a_nx_n.$$

Bài tập 4. Tìm các số nguyên $x,\,y,\,z$ thoả \[6x+15y+20z=17.\]

Bài tập 5. Cho một số tiền. Biết rằng khi chia số tiền đó cho $77$ thì dư $50$, còn nếu chia cho $78$ thì không dư. Hỏi có bao nhiêu tiền?

Tags: , , , , ,

Reply

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *