Một lớp học có 18 nam và 12 nữ, ta muốn chia lớp thành các nhóm thuyết trình sao cho số nam ở mỗi nhóm bằng nhau. Vậy ta phải chia như thế nào?
Một lớp học khi sắp thành 6 hàng hoặc 7 hàng thì số học sinh mỗi hàng đều có số học sinh bằng nhau. Vậy lớp học đó có ít nhất bao nhiêu học sinh?
Định nghĩa 1. Cho hai số nguyên $a, b$. Số nguyên $d$ thỏa $d|a$ và $d|b$ được gọi là ước chung của $a$ và $b$.
Ví dụ 1. 2 là ước chung của 4 và 6 vì $2|4$ và $2|6$.
Định nghĩa 2. Cho hai số nguyên $a$ và $b$ (không đồng thời bằng 0). Số nguyên dương $d$ là ước chung $a$, $b$ và $d$ là số lớn nhất trong các ước chung của $a, b$ được gọi là ước chung lớn nhất của $a, b$.
Rõ ràng tập các ước dương của $a, b$ là khác rỗng vì có chứa số 1 và là tập hữu hạn, do nhỏ hơn hoặc bằng $\max{|a|, |b|}$, nên $d$ là tồn tại.
Kí hiệu ước chung lớn nhất của $a, b$ là $gcd(a,b), UCLN(a,b)$ hoặc đơn giản nhất là $(a,b)$.
Tính chất 1. Gọi $d = UCLN(a,b)$, $a’ = \dfrac{a}{d}, b’ = \dfrac{b}{d}$. Khi đó
a) $(a’,b’) = 1$.
b) $(a-b, b) = (a,b) = d$.
Chứng minh
a) Đặt $a = d.a’,b = d.b’$, ta chứng minh $(a’,b’) =1$. Giả sử ngược lại $(a’,b’)= m>1$. Khi đó $a= d.a’ = d.m.a”, b = d.m.b”$, suy ra $md(>d)$ là ước chung của $a,b$ vô lý vì $d$ là ước chung lớn nhất của $a$ và $b$.
Vậy $(a’,b’) = \dfrac{a}{d}, \dfrac{b}{d} =1$
b) Gọi $d$ là ước của $a, b$, khi đó $d \mid a, d \mid b \Rightarrow d \mid a-b$, do đó $d$ cũng là ước chung của $a-b$ và $b$.
Ngược lại nếu $e$ là ước chung của $a-b, b$ thì $e$ cũng là ước của $a,b$
Do đó tập ước chung của $(a,b)$ và $a-b,b$ bằng nhau. Do đó $UCLN(a-b,b) = UCLN(a,b)$.
Từ đây ta có nếu $a = bq + r$ thì $UCLN(a,b) = (r,b)$.
Tính chất 2. Cho $a, b$ là các số nguyên dương, gọi $d = UCLN(a,b)$, khi đó mọi ước chung của $a, b$ đều là ước của $d$.
Chứng minh
Gọi $d=ULCN(a,b)$ và $m$ là một ước chung khác, ta chứng minh $m|d$.
Đặt $d = qm + r, 0\leq r \leq m-1$. Ta có $a=d \cdot a’, b = d\cdot b’$, ta có $(a’,b’)=1$.
Suy ra $a = a'(qm+r)=a’qm+a’r, b = b’qm+b’r$, suy ra $a’r, b’r$ chia hết cho $m$.
Nếu $(r,m) = t < m$ và $m= t\cdot m’, r= t\cdot r’$, suy ra $a’, b’$ chia hết cho $m’$, mà $(a’,b’)=1$ nên $m’=1$, suy ra $t=m$ vô lí.
Suy ra $(r,m)=m$, suy ra $r=0$ hay $d$ chia hết cho $m$.
Định nghĩa 3. Nếu ước chung lớn nhất của hai số nguyên $a$ và $b$ bằng 1 thì ta nói $a, b$ là nguyên tố cùng nhau.
Ví dụ 2. 12 và 35 có ước chung lớn nhất bằng 1 nên ta nói 12 và 35 là nguyên tố cùng nhau. Kí hiệu $(12, 35)=1$.
Tính chất 4. Cho $a, b$ là hai số nguyên. Ta có các tính chất sau:
1) $ (ca,cb) = c \cdot (a,b) $ với mọi số nguyên $c$.
2) Nếu $ ax + by = m $ thì $(a,b) |m$.
Chứng minh
1) Đặt $d = (a,b),d’ = (ca,cb)$. Chứng minh $dc| d’, d’| dc$. Thật vậy $dc | ca,dc| cb$, suy ra $dc|d’$. Giả sử $d’ = dc.m, a = da’, b =db’.
Ta có $dcm| cda’, dcm| cdb’$, suy ra $m|a’, m|b’$ mà $(a’,b’) =1$ nên $m =1$. Vậy $d’ = dc$.
2) Đặt $d= (a,b)$ ta có $d|a,d|b \Rightarrow d| (xa+yb)$ hay $d|m$.
Ví dụ 3. Với n là số tự nhiên. Tìm
a) $(n,n+1)$.
b) $(4n +6, 6n +8)$.
Lời giải
a) Ta có $(n, n+1) = (n. n+1) -1) = (n,1) = 1$.
Từ đây ta thấy, hai số nguyên liên tiếp có ước chung lớn nhất bằng 1, hay là hai số nguyên tố cùng nhau.\\
b) $(4n +6,6n+8) = 2(2n+3,3n+4)$.
Mà $(2n+3,3n+4) = (2n +3, n+1) =(n+1, n+2) =1$.
Vậy $( 4n+6,6n +8) =2$.
Thuật toán Euclide tìm ước chung lớn nhất của hai số nguyên dương $a$ và $b$.
Đầu tiên ta chia $a$ cho $b$ được $r_1 ( 0 \leq r_1 <b)$ , chia $b$ cho $r_1$ được dư $r_2 ( 0 \leq r_2< r_1)$, cứ tiếp tục như thế ta được dãy giảm các số nguyên không âm $ r_1, r_2,…. $ do đó sẽ tồn tại $n$ sao cho $r_{n+1} = 0 $.
Khi đó ta có:
$a = bq + r_1 (0 \leq r_1 <b)$
$b = r_1q_1 + r_2 (0 \leq r_2< r_1)$
$r_1 = r_2q_2 +r_3 (0 \leq r_3< r_2)$
….
$r_{n -2} = r_{n-1}q_{n-1} + r_n (0 \leq r_n < r_ {n -1})$
$r_{n – 1} = r_nq_n$
Theo định lý 8 ta có $(a,b) – (b,r_1) = (r_1, r_2) = … (r_{n-1}, r_n) = r_n$.
Ví dụ 4. Tìm UCLN của $18, 42$. Ta thực hiện như sau:
$48= 18 \cdot 2 + 12$, $r_1 = 12$
$18 = 12 \cdot 1 + 6$, $r_2 = 6$
$12 = 6 \cdot 2 + 0$, $r_3 = 0$.
Khi đó $UCLN(48,18) = UCLN(18, 12) = UCLN(12, 6) = 6$.
Định lý 1. Cho $a,b$ là hai số nguyên dương.
Gọi $d = (a,b)$. Khi đó tồn tại các số nguyên $x,y$ sao cho $xa+yb =d$.
Chứng minh
Cách 1. Từ thuật toán Euclide trên ta có
$r_1 = a- bq, r_2 = b -r_1q_1 = b – q_1(a-bq) = (1-qq_1)b +a(-q_1) = x_1a+y_1b$, với $y_1=1-qq_1, x_1 = -q_1$ là các số nguyên.
$r_3 = r_1 -r_2q_2 = a-bq – (x_1b+y_1a)q_2 = (1-y_1q_2)a + (-q-x_1q_2) = x_2a + y_2b$
…..
$r_n = r_{n-2} -r_{n-1}q_{n-1} = xa + yb$.
Cách 2. Sử dụng nguyên lí cực hạn
Đặt T = ${xa + yb| x,y \in Z, xa +yb >0}$. Không mất tính tổng quát, ta có thể giả sử $a \neq 0$.
Nếu $a>0$, ta có $1.a + 0.b = a>0$, suy ra $a \in T$.
Nếu $a < 0$, ta có $-a = (-1) .a + b.0 = -a >0$, suy ra $-a \in T$. Vậy $T\neq \oslash$.
Khi đó T có phần tử nhỏ nhất, ta đặt $e = xa + yb$.
Giả sử $a = ek +r$, với $ 0 \leq r < e$ , suy ra $r = a – ek = a – (xa +yb).k = a(1 – xk) + b. yk$.
Nếu $r >0$ thì $r \leq T$ mâu thuẫn vì $e$ là phần tử nhỏ nhất của T.
Vậy $r =0$ suy ra $e|a$. Chứng minh tương tự ta có $e|b, do đó e|d$.
Mặt khác $d|a, d|b$ suy ra $d|(xa + yb)$ hay $d|e$. Từ đó ta có $d = e$.
Hệ quả 1. Cho $a, b$ là các số nguyên tố cùng nhau. Khi đó tồn tại hai số nguyên $x,y$ sao cho $xa + yb =1$.
Tính chất 5. Cho các số nguyên $a, m,n$
a) Nếu $m|a, n|a$ và $m,n$ nguyên tố cùng nhau thì $mn|a$.
b)Nếu $a|mn$ và $(a,m) = 1$ thì $a|n$.\
Chứng minh
a) Vì m|a, n|a nên có hai số x, y sao cho a = mx = ny. Vì (m,n) = 1 nên có hai số nguyên u, v thõa mãn um + vn = 1. Nhân a vào hai vế ta có: a = nym + mxvn = mn ( uy+ vx). Do đó mn|a.\\
b)Vì (a,m) =1 nên có hai nguyên x, y sao cho ax+ my =1. Suy ra n = anx + mny. Mà a|mn nên ta có a|(anx + mny) hay a|n. \\
Bội chung, bội chung nhỏ nhất
Định nghĩa 3. Cho hai số nguyên $a, b$. Số nguyên $m$ vừa chia hết cho $a$, vừa chia hết cho $n$ được gọi là bội chung của $a$ và $b$.
Ví dụ 5. Số 12 là bội chung của 2 và 3.
Nhận xét.
Nếu có trong hai số $a, b$ bằng 0 thì chỉ có 0 là bội chung của $a$ và $b$. Nếu hai số nguyên $a$ và $b$ đồng thời khác 0 sẽ có vô số bội chung. Khi đó ta xét tập các bội chung dương, tập này khác rỗng và sẽ có số nhỏ nhất. Từ đó ta có định nghĩa sau:
Định nghĩa 4. Cho hai số nguyên $a, b$ đồng thời khác 0. Số nguyên $m$ được gọi là bôi chung nhỏ nhất của $a$ và $n$ nếu thỏa đồng thời các điều kiệ sau đây:
i) $m > 0$;
ii) $a|m$ và $b|e$ thì $m|e$;
iii) Nếu $a|e$ và $b|e$ thì $m|e$.
Bội chung nhỏ nhất của hai số nguyên $a$ và $b$, kí hiệu là $lcm (a,b)$ hoặc BCNN $(a,b)$ hoặc đơn giản nhất $[a,b]$.
Ví dụ 6. Bội chung nhỏ nhất của 4 và 6 là 12.
Tính chất. Cho hai số nguyên $a, b$.
a) Nếu $m = [a,b]$ thì $(\dfrac{m}{n}, \dfrac{m}{b}) =1$.
b) $[ca,cb] = c[a,b]$.
Tính chất 6. Cho hai số nguyên $a,b$. Khi đó:
$[a,b] = \dfrac{ab}{(a,b)} $
Chứng minh.
Đặt $d = (a,b),m = [a,b],a = dx,b = dy$. Ta chứng minh $m = dxy$
Ta có $a|dxxy,b| dxy \Rightarrow m|dxy$
Gỉa sử $m = au = dxu, m= byv$.
Do đó $x|\dfrac{m}{d}$ và $| \dfrac{m}{d}$, mà $(x,y) =1$ nên $xy| \dfrac{m}{d}$ hay $dxy|m$.
Vậy $m= dxy = \dfrac{ab}{(a,b)}$.
Ví dụ 7. Tìm hai số tự nhiên có ước chung lướn nhất bằng 6 và bội chung nhỏ nhất bằng 36.\
Lời giải. Gọi hai số cần tìm là a va b $(a\leq b)$. Ta có $a \cdot b = 6.36 = 216$.
Ta có $a = 6m, b =6n$. Khi đó $mn =6$.
Suy ra $m =1, n = 6$ hoặc $m =2, n=3$.
Ta có hai cặp số thõa là (6,36) hoặc (12,18).
Bài tập rèn luyện.
Bài 1. Chứng minh tính chất 15.
Bài 2. Chứng minh rằng với mọi số nguyên $n$ thì $(22n+ 7,33n +10) =1$.
Bài 3. Chứng minh rằng không có các số nguyên $a, b$ thõa mãn $(a,b) = 3$ và $a+b =65$.
Bài 4. Chứng minh răng nếu $(a,b) = 1$ thì $(a +ab, b)=1$.
Bài 5. Chứng minh rằng nếu $a|b$ thì $(a,b) = |a|$ và $[a,b] = |b|$.
Bài 6. Cho $n$ là số nguyên dương. Tìm $[n, n+1]$.
Bài 7. Cho $n$ là số nguyên dương. Chứng minh răng $[9n +8,6n +5] = 54n^2 + 93n +40$.
Bài 8. Tìm tất cả các cặp số nguyên dương $a,b$ khác nhau thỏa $(a,b) = 8, [a,b] = 384$.
Bài 9. Chứng minh rằng nếu $(a,b) = 1, (a,c) =1$ thì $(a,bc) = 1$.
Bài 10. chứng minh nếu $(a,b) =1$ thì $(a^m, b^n)=1$ với mọi số nguyên dương $m,n$.