Tag Archives: Số học

Số nguyên tố – Hợp số

Leave a reply

Một lớp học có 42 học sinh, muốn chia lớp thành các nhóm thuyết trình sao cho số học sinh ở mỗi nhóm bằng nhau và số tổ lớn hơn 1 và nhỏ hơn 10. Có thể chia được không nếu số học sinh trong lớp là 43?

Định nghĩa 1. Một số nguyên dương được gọi là số nguyên tố nếu số đó lớn hơn 1 và chỉ có hai ước dương là 1 và chính nó. Số nguyên dương lớn hơn 1 không phải là số nguyên tố được gọi là hợp số.

Chú ý: Hai số 0 và 1 không phải là số nguyên tố, cũng không phải là hợp số.

Ví dụ 1. Các số 2, 3, 5, 7, 11 là các số nguyên tố đầu tiên.

Các số 4, 6, 8, 9 là các hợp số

Tính chất 1. Với mỗi số tự nhiên $n \geq 2$ thì hoặc $n$ là số nguyên tố, hoặc $n$ là tích của các số nguyên tố.

Chứng minh

Ta chứng minh bằng quy nạp.

Với $n =2, 3$ ta có $n$ là một số nguyên tố.

Gỉa sử bài toán đúng với mọi $k$ với $k \leq n$. Ta chứng minh bài toán đúng với $n +1$.

Nếu $n+1$ là số nguyên tố, ta có điều cần chứng minh. Nếu $n+1$ không phải là số nguyên tố, khi đó $n+1$ có thể phân tích thành tích hai số $p$ và $q$ $ (2\leq p, q<n) $, tức là $n=p \cdot q$. Theo giả thiết quy nạp thì $p, q$ hoặc là nguyên tố hoặc là có thể phân tích thành tích các số nguyên tố. Từ đó ta có điều cần chứng minh.

Tính chất 2.
1) Hai số nguyên tố bất kì phân biệt là số nguyên tố cùng nhau.
2) Cho số nguyên tố $p$, nếu $a$ là một số nguyên thì hoặc $ p|a $ hoặc $(a,p)=1$.
3) Nếu $p$ là số nguyên tố và $p|ab$, khi đó $p|a$ hoặc $p|b$.

Chứng minh
1) Hiển nhiên theo định nghĩa số nguyên tố.
2) Đặt $d=(p,a)$. Ta có $d|a, d|p$. Vì $p$ nguyên tố nên $d=1$ hoặc $d=p$. Từ đó suy ra điều cần chứng minh.

3) Nếu $a$ không chia hết cho $p$, suy ra $(p,a)=1$, mà $p|ab$ nên ta có $p|b$.

Phân tích một số thành thừa số nguyên tố.

Định lý 18 cho ta thấy rằng mọi số nguyên dương lớn hơn hoặc bằng 2 có thể là số nguyên tố hoặc có thể phân tích thành tích các thừa số nguyên tố. Nhưng sự phân tích đó có duy nhất không? Để biết được điều đó, sau đây chúng tôi nêu ra một định lý quan trọng của số học và không chứng minh định lý này. Bạn đọc có thể tham khảo trong [1].

Định lý 2. (Định lý cơ bản của số học) Mọi số nguyên dương lớn hơn 1 đều có thể phân tích một cách duy nhất thành tích các số nguyên tố (không tính thứ tự sắp xếp các số thừa số nguyên tố)

Ví dụ 2. $ 12=2^2.3 ; 245=5.7^2 $

Hệ quả 1. Cho hai số nguyên $a$ và $b$. Giả sử $a,b$ được phân tích thành các thừa số nguyên tố $ a=p_1^{x_1}p_2^{x_2}…p_m^{x_m}.a’, b=p_1^{y_1}p_2^{y_2}…p_m^{y_m}.b’ $. Trong đó $(a’,b’)=1$, các thừa số $ p_i $ là các thừa số nguyên tố chung.

Đặt $ z_i=\min{x_1,y_1}; t_i=\max{x_1,y_1} $, khi đó $(a, b)=p_1^{z_1}p_2^{z_2}…p_m^{z_m} $ và $ [a,b]=p_1^{t_1}p_2^{t_2}…p_m^{t_m}.a’.b’ $

Ví dụ 3. Tìm ước chung nhỏ nhất và bội chung nhỏ nhất của hai số 252 và 220.
Lời giải. Ta có $ 252=2^2.3^2.7,220=2.3^3.5 $

Do đó ước chung nhỏ nhất của 252 và 220 là $ 2.3^3=18 $ và bội chung nhỏ nhất của 252 và 220 là $ 2.3^3.5.7 $.

Hệ quả 2. Cho số nguyên $a$ và số tự nhiên $n$. Giả sử $n$ được phân tích thành các thừa số nguyên tố $ n=p_1^{a_1}p_2^{a_2}…p_k^{a_k} $. Khi đó nếu $ a \vdots p_1^{a_1} \forall i=1,…,k $ thì $ a \vdots n $

Hệ quả 3. Mỗi số tự nguyên dương $n$ tồn tại duy nhất số không âm $m$ và $q$ trong đó $q$ lẻ và $n = q.2^m$.

Ví dụ 4. $48 = 3.2^4$, $15 = 15.2^0$.

Bài tập có lời giải.

Bài 1. Tìm các số nguyên tố $p$ để: $p+2$, $p+6$, $p+8$; $p+14$ cũng là các số nguyên tố.

Lời giải: Dễ thấy $p = 2, 3$ không thỏa đề bài, $p=5$ thỏa đề bài.

Xét $p>5$.

  • Nếu $p = 5k+1$ thì $p+4$ chia hết cho $5$ và $p+4 > 5$ nên không là số nguyên tố.
  • Nếu $p = 5k+2$ thì $p+8 = 5k+10$ chia hết cho 5, không là số nguyên tố.
  • Nếu $p = 5k+3$ thì $p+2 = 5(k+1)$ chia hết cho 5, không là số nguyên tố.
  • Nếu $p= 5k+4$ thì $p+6 = 5(k+2)$ chia hết cho 5, không là số nguyên tố.

Kết luận: $p=5$.
Bài 2. Tìm các số nguyên dương $n$ để $n^5+n+1$ là số nguyên tố.

Lời giải: Ta có $A(n) = n^5 + n+ 1 = n^5 – n^2 + n^2 + n +1 = n^2(n-1)(n^2+n+1) + (n^2+n+1) = (n^2+n+1)(n^3-n^2+1)$

Vì $n^2+n+1 >1$, nên $A(n)$ là số nguyên tố thì $n^3-n^2+1  = 1$, suy ra $n=1$

Thử lại $n=1$ thỏa đề bài.

Bài 3. Cho số tự nhiên $n$, chứng minh rằng nếu $ 2^n-1 $ là số nguyên tố thì n cũng là số nguyên tố.

Lời giải. Giả sử $n$ không là số nguyên tố.

  • Với $n=0$ thì $2^0 – 1 = 0$ không là số nguyên tố.
  • Với $n=1$ thì $2^1 – 1 = 0$ không là số nguyên tố.
  • Với $n > 1$, $n = q \cdot q$ trong đó $1 < p, q < n$. Khi đó $2^n – 1 = (2^p)^q = 1$ chia hết cho $2^p-1$, mà $1 < 2^p-1 < 2^n-1$ nên $2^n-1$ không là số nguyên tố. (mâu thuẫn.

Vậy $n$ là số nguyên tố.

Bài 4. Cho các số nguyên dương $a, b, c, d$ thỏa $ac = bd$. Chứng minh rằng $a^2+b^2+c^2+d^2$ là hợp số.
Lời giải.

Đặt $d = UCLN(a,b)$, và $a = du, b = dv$, suy ra $(u,v) = 1$.

Khi đó ta có $uc = vd$, mà $u \mid vd, (u,v) = 1$, suy ra $u \mid d$, đặt $d = um$, suy ra $c = vm$.

Vậy $a + b+ c+ d = du + dv + vm + um = (u+v)(m+d)$, các số $d, m, u, v \geq 1$ nên $a+b+c+d$ là hợp số.

Bài tập rèn luyện.

Bài 1.

a) Chứng minh rằng mọi số nguyên tố lớn hơn 3 đều có dạng $ 3k+1 $ hoặc $ 3k-1(k\geq 2) $
b) Chứng minh rằng mọi số nguyên tố lớn hơn 5 đều có dạng $ 6k+1 $ hoặc $ 6k-1 (k\geq 2) $.

Bài 2. Chứng minh rằng $ n^4-1$ là hợp số với mọi số nguyên n>1.
Bài 3. Tìm số nguyên tố $p$ sao cho $p+2, p+4$ cũng là số nguyên tố.
Bài 4. Cho $n$ không phải là số nguyên tố. Chứng minh rằng nếu $p$ là ước nguyên tố lớn nhất của n thì $ p^2\leq n $.
Bài 5. Cho số nguyên tố $p$. Khẳng định sau đúng hay sai: “Nếu $ a|p(p-1) $ thì a|p hoặc a|(p-1)”.
Bài 6. Tìm tất cả các số tự nhiên $n$ lẻ để $n, n+10, n+14$ là số nguyên tố.
Bài 7. Tìm tất cả các số nguyên tố $p$ sao cho $ 2p^2+1 $ là số nguyên tố.
Bài 8. Tìm tất cả các số nguyên dương sao cho $ a^4+4b^4 $ là số nguyên tố.

Bài 9. Tìm tất cả các số nguyên tố p sao cho $ 2p^2+1 $ là số nguyên tố.
Bài 10. Chứng minh rằng nếu số nguyên dương $ n\geq 2 $ là số nguyên tố nếu nó không có ước nguyên tố nào nhỏ hơn hoặc bằng $ \sqrt n $

Ước chung – Bội chung

Leave a reply

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]$.

Chứng minh
(Dành cho bạn đọc)

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$.

Phép chia hết – Phép chia có dư

Leave a reply
Một lớp học có 40 học sinh sắp hàng vào lớp. Nếu lớp trưởng bảo sắp thành 4 hàng đều nhau thì các học sinh đều biết rằng mỗi hàng là 10 học sinh. Nhưng khi lớp trưởng vào sắp thành 3 hàng thì các bạn học sinh không thể sắp được như thế, nếu sắp mỗi hàng 13 người thì chỉ mới 39, còn dư 1 người. Khi đó người ta nói 40 học sinh có thể chia hết cho 4 và 40 chia 3 dư 1.

Trên đây là một ví dụ cho phép chia hết và phép chia có dư. Và trong thực tế chúng ta sẽ gặp rất nhiều trường hợp phải chia một đại lượng có giá trị nguyên thành nhiều phần, có thể chia đều tương ứng với phép chia hết hoặc không thể chia đều tương ứng với phép có dư.

Định nghĩa 1. Cho hai số nguyên $a$ và $b$ với $(b\neq 0) $. Nếu tồn tại số nguyên $m$ sao cho $ a=bm $ (1), ta nói rằng $a$ chia hết cho $b$ hay $b$ chia hết $a$. Kí hiệu $ a \vdots b $ hay $ b|a $. Ngược lại, nếu không có số nguyên nào thỏa mãn đẳng thức (1) thì ta nói $a$ không chia hết cho $b$.

Ví dụ 1. 6 chia hết cho 3 vì $6 = 3 \times 2$.

Tính chất 2. Cho $a, b, c$ là các số nguyên. Khi đó ta có các tính chất sau:

  1. Nếu $ a \, \vdots \, c, b\, \vdots \,c $ thì $ (a+b)\, \vdots c, (a-b)\,\vdots \,c $
  2. Nếu $ a \,\vdots \,b, b\, \vdots \,c $ thì $ a\,\vdots \,c $
  3. Nếu $ a \vdots b $, thì $ m.a\vdots m.b $ với mọi số nguyên m.
  4. Nếu $ a\,vdots \,c, b\,\vdots \,c $ thì $ (x.a+y.b)\,\vdots \,c $ với mọi số nguyên $x,y$.
  5. Số 0 chia hết cho mọi số nguyên , mọi số nguyên đều chia hết cho số 1 và chính nó.

Định lý 3. Cho $ a $ là số nguyên, $ b $ là số nguyên dương. Chứng minh rằng tồn tại duy nhất số nguyên $ q $ và số nguyên $ r $ thỏa $ 0\leq r\leq b-1 $ và $ a=bq+r. $

Chứng minh

Đặt tập $ S={a-bk , a-bk\geq 0} $ (k nguyên). Trước hết ta chứng minh $ S\neq \varnothing $.

Thật vậy, nếu $ a\geq 0 $ thì $ a=a-b\cdot 0 $, nên $ a\in S $. Nếu a<0, $ a-b\cdot a=a(1-b)\geq 0 $ vì ($ 1-b\leq 0 $). Do đó $ a-ba\in S. $

S là tập khác rỗng các số nguyên không âm nên có phần tử nhỏ nhất.

Đặt $ r=\min S $. Khi đó, có số nguyên q sao cho $ a-bq=r $ hay $ a=bq+r $.

Ta chứng minh $ 0\leq r <b $. Vì $ r\in S $ nên $ r\geq 0 $.

Giả sử $ r\geq b $. Ta có $ a=bq+r=bq+b+r-b=b(q+1)=r-b $

Suy ra $ a-b(q+1)=r-b\geq 0 $, suy ra $ r-b\in S $ và $ r-b<r $ (vô lý và r là số nhỏ nhất của tập hợp S). Vậy r<b.

Tiếp theo ta chứng minh sự duy nhất của bộ số (q,r). Giả sử tồn tại p và t sao cho $ 0\leq t<b, a=b.p+t $. Vì $ bq+r=bp+t $ nên $ t-r=b(q-p) $ chia hết cho b. Mặt khác do $ 0\leq r, t<b, $ suy ra $ 0\leq |t-r|<b .$ Từ đó ta có $ |t-r|=0 $, suy ra $ t=r, p=q. $

Sổ trong định lý 3 được gọi là số dư của a khi chia cho b, q được gọi là thương của phép chia. Vậy một số nguên khi chia cho số nguyên dương k được số k dư là 0,1,2,…,k-1. Từ đó, một số nguyên a bất kì có thể được biểu diến thành 1 trong các dạng sau: $ kq, kq+1, kq+2, …,kq+(k-1) $. Sự biểu diễn một số nguyên thành các dạng như trên sẽ rất hiệu quả khi ta giải các bài toán số học.

Hệ quả 4. Hai số nguyên $a,b$ khi chia cho $m$ có cùng số dư khi và chỉ khi $a-b$ chia hết cho $m$.

Chứng minh

Nếu $a,b$ có cùng số dư $r$ khi chia cho $m$, khi đó hai số nguyên $k,l$ thỏa mãn $ a=mk+r, b=ml+r $.

Suy ra $ a-b=m(k-l) $ chia hết cho $m$.

Cho $ a-b $ chia hết cho m, khi đó $ a-b=mp $. Giả sử số dư của a chia cho m là r. Khi đó $ a=mq+r $.

Suy ra $ b=a-(a-b)=mq+r-mp=m(q-p)+r $. Do đó số dư của b khi chia cho m cũng bằng $r$.

Ví dụ 2. Bình phương của một số nguyên khi chia cho 3 được các số dư nào?

Lời giải

Cho số nguyên $a$. Khi $a$ chia cho 3 có các số dư là 0, 1, 2. Do đó $a$ có thể có dạng $3k, 3k+1, 3k+2$.

TH1: Nếu $a=3k$, suy ra $ a^2=9k^2 $ chia hết cho 3.

TH2: Nếu $a=3k+1$, suy ra $ a^2=9k^2+6k+1 $ chia 3 dư 1.

TH3: Nếu $a=3k+2$, suy ra $ a^2=9k^2-6k+1 $ chia 3 dư 1.

Vậy bình phương một số nguyên khi chia cho 3 thì số dư là 0 hoặc 1.\\

Dấu hiệu chia hết. 

Biểu diễn thập phân của số tự nhiên. Nếu số tự nhiên a có biểu diễn thập phân là $ A=\overline{a_1a_2…a_n} $ trong đó $ 1\leq a_1\leq 9, 0\leq a_i\leq 9 $ với $ i=2,3…,n $
Thì $ A=\overline{a_1a_2…a_n}=a_1.10^{n-1}+a_2.10^{n-2}+…+a_{n-1}.10+a_n $.

Định lý 5.

  • Một số chia hết cho 2, 5 nếu chữ số tận cùng chia hết cho 2,5.
  • Một số chia hết cho 4, 25 nếu số tạo bởi hai chữ só tận cùng chia hết cho 4.
  • Một số chia hết cho 8, 125 nếu số tạo bởi ba chữ só tận cùng chia hết cho 8 , 125.\\
Chứng minh

Cho số tự nhiên A, giả sử A có biểu diễn thập phân là $ A=\overline{a_1a_2…a_n} $

Ta có $ A=\overline{a_1a_2…a_n}=a_1.10^{n-1}+a_2.10^{n-2}+…+a_{n-1}.10+a_n $
\begin{enumerate}
\item [a)] Vì $ a_i.10^{n-i} \vdots 2 $ với i=1,2,…,n-1. Suy ra $ A\vdots 2 \Leftrightarrow a_n\vdots2 $

Tương tự ta cũng có $ A\vdots5 \Leftrightarrow a_n\vdots5 $

\item [b)] Vì $ a_i.10^{n-i} \vdots 4 $ với i=1,2,…,n-2. Suy ra $ A\vdots 4 \Leftrightarrow a_{n-1}.10+a_n\vdots 4 $ hay $ \overline{a_{n-1a_n}}\vdots 4 $. Tương tự ta cũng có $ A\vdots25 \Leftrightarrow \overline{a_{n-1}a_n}\vdots 25 $.
\item [c)] Tương tự như trên.

Định lý 6.

  • Một số tự nhiên chia hết cho 3 khi và chỉ khi tổng các chữ số chia hết cho 3.
  • Một số tự nhiên chia hết cho 9 khi và chỉ khi tổng các chữ số chia hết cho 9.
Chứng minh

a) Xét số tự nhiên $ A=\overline{a_1a_2…a_n}=a_1.10^{n-1}+a_2.10^{n-2}+…+a_{n-1}.10+a_n $

Khi đó $ A-(a_1+a_2+…+a_n)=a_1.(10^{n-1}-1)+a_2.(10^{n-2}-1)+…+a_{n-1}.(10-1)+a_n-a_n $

Ta có $ 10^i-1\vdots3, \forall i=\overline{1,n-1} $, suy ra $ A-(a_1+a_2+…+a_n)\vdots3 $

Do đó $ A\vdots3 \Leftrightarrow (a_1+a_2+…+a_n)\vdots3 $
Chứng minh tương tự cho câu b.

Ví dụ 3. Tìm các số $ A=\overline{3xy4} $ chia hết cho 36.

Lời giải. Ta có A chia hết cho 36 nên chia hết cho 4 và 9.

Do đó $ \overline{y4}\vdots 4\Rightarrow y=0,2,4,6,8 $

Và $ 3+x+y+4 $ chia hết cho 9 và $ 0\leq x +y\leq 18$, suy ra $ x+y=2,11. $

Lập bảng các trường hợp và tìm được các số thỏa đề bài: 3024, 3204, 3924, 3744, 3564, 3384.

Bài tập.

Nếu không có giả thiết gì thêm, ta xét các bài toán trong tập số nguyên.

Bài 1. Chứng minh nếu $ a>0, b>0, a\vdots b, b\vdots a $ thì $a=b$.

Bài 2. Chứng minh nếu $ a\vdots b, c\vdots d $ thì $ ac \vdots bd $

Bài 3. rong các khẳng định sau, cái nào đúng, cái nào sai (nếu đúng thì chứng minh, sai thì cho một ví dụ)
a) Nếu $ bc \vdots a $ thì $ b \vdots a $ hoặc $ c\vdots a $
b) Nếu $ (b+c)\vdots a $ thì $ b \vdots a $ hoặc $ c\vdots a $
c) Nếu $ b^2\vdots a^3 $ thì $ b\vdots a $
d) Nếu $ c\vdots a^2 $ và $ c\vdots b^2 $ và $ a^2\leq b^2 $ thì $ b\vdots a $.

Bài 4. Chứng minh rằng trong hai số tự nhiên liên tiếp có một số chia hết cho 2.
a) Trong $n$ số tự nhiên liên tiếp có một số chia hết cho $n$.
b) Chứng minh rằng tích hai số tự nhiên liên tiếp chia hết cho 2, tích $n$ số tự nhiên liên tiếp chia hết cho $n$.

Bài 5. Chứng minh rằng tích hai số chẵn liên tiếp chia hết cho 8 (Số chẵn là số chia hết cho 2, số không chia hết cho 2 được gọi là số lẻ)

Bài 6. Chứng minh rằng nếu n lẻ thì $ n^2-1 $ chia hết cho 8.
Bài 7. Cho a, b là các số nguyên. Chứng minh rằng
a) $ a^n-b^n $ chia hết cho a-b với mọi số tự nhiên n.
b) $ a^n+b^n $ chia hết cho a+b với mọi số tự nhiên n lẻ.

Bài 8. Chứng minh rằng với mọi số tự nhiên n thì $ 5^{2n}+7 $ chia hết cho 8.
Bài 9. Chứng minh rằng với mọi số tự nhiên n thì $ 3^{2n+1}+2^{n+2} $ chia hết cho 7.
Bài 10. Chứng minh rằng nếu $ a^2+b^2 $ chia hết cho 3 thì a và b đều chia hết cho 3.
Bài 11. Cho n+1 số nguyên phân biệt. Chứng minh rằng có hai số sao cho hiệu của chúng chia hết cho n.
Bài 12. Chứng minh rằng nếu $ \overline{abc} $ là bội của 37 thì $ \overline{bca} $ cũng là bội của 37.
Bài 13. Tìm các số x,y thỏa $ \overline{2x7y5} $ chia hết cho 75.
Bài 14. Chứng minh rằng tồn tại một số tự nhiên khi biểu diễn thập phân chỉ toàn chữ số 1 và chia hết cho 2011.