Chuyen de boi duong HSG dai so

CHUYÊN ĐỀ SỐ HỌC

CHUYÊN ĐỀ I :

PHÉP CHIA CÓ DƯ – ĐỒNG DƯ THỨC

I. Phép chia hết, phép chia có dư

1. Cho a, b
Z, b > 0 ; khi chia a cho b ta có:
a) a
b (hay a b) khi và chỉ khi có số nguyên q sao cho a = b.q
b) a không chia hết cho b : khi đó chia a cho b ta được thương gần đúng là q và số dư r (0 < r < b) ; ta viết : a = b.q + r (với 0 < r < b)

Chú ý :
Khi chia một số nguyên a cho một số nguyên b > 0 thì số dư là một trong b số từ 0 đến b – 1.
Trong trường hợp a không chia hết cho b (r ( 0). Ta có thể lấy số dư là số âm r’ với r’ = r – b (do đó
< b).
Ví dụ : Chia 23 cho 3, ta có thể viết :
23 = 3.7 + 2 (7 gọi là thương gần đúng thiếu, vì 3.7 = 21 < 23)
23 = 3.8 + (–1) (8 gọi là thương gần đúng thừa, vì 3.8 = 24 > 23)
Coi số dư có thể là số âm như trên, thì mọi số nguyên a khi chia cho 2, 3, 4, … , b có dạng :
a = 2k ; a = 2k + 1 hoặc a = 2k ; a = 2k – 1 (k
Z)
a = 3k ; a = 3k ( 1 (k
Z)
a = 4k ; a = 4k ( 1 ; a = 4k + 2 hoặc a = 4k ; a = 4k ( 1 ; a = 4k – 2 (k
Z)
………………………………………………………………………………………………
Tổng quát : nếu a = bk + r (b > 0), thì :
b chẵn :
r = 0 ; r = (1 ; r = (2 ; …… ;

hoặc r = 0 ; r = (1 ; r = (2 ; …… ; –

b lẻ
r = 0 ; r = (1 ; r = (2 ; …… ; (


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

Cho hai số nguyên dương a và b.
Ước chung lớn nhất của a và b, kí hiệu ƯCLN(a,b) hay (a,b). Một số d là ước chung của a và b khi và chỉ khi d là ước chung của ƯCLN(a,b).
d a và d b
d (a,b)
Bội chung nhỏ nhất của a và b, kí hiệu BCNN(a,b) hoặc
. Một số m là bội chung của a và b khi và chỉ khi m là bội của BCNN(a,b).
m
a và m
b
m


Hai số được gọi là nguyên tố cùng nhau khi và chỉ khi (a,b) = 1
Ta chứng minh được :
=

Từ đó :
= ab nếu (a,b) = 1
3. Thuật toán Ơclit (Tìm ƯCLN dựa vào định lí phép chia có dư) :

Thuật toán Ơclit dựa vào hai mệnh đề sau :
a = bq
(a,b) = b
a = bq + r (r ( 0)
(a,b) = (b,r)
Ví dụ : Tìm (702,306)
Ta có : 702 = 306.2 + 90
(702,306) = (306,90)
306 = 90.3 + 36
(306,90) = (90,36)
90 = 36.2 + 18
(90,36) = (36,18) = 18
Vậy (702,306) = 18.
Trong thực hành, người ta thường đặt phép tính như sau :



Nếu thực hiện thuật toán Ơclit để tìm ƯCLN của hai số mà đến một lúc nào đó có số dư là 1 thì hai số đó là nguyên tố cùng nhau.
Áp dụng : Cho n là số tự nhiên bất kì ; Chứng minh rằng :
không thể giản ước được.
(Đề thi học sinh giỏi toán cấp II toàn quốc năm 1970)
Giải : 21n + 4 = (14n + 3).1 + 7n + 1
(21n + 4,14n +3) = (14n + 3,7n + 1)
14n + 3 = (7n + 1).2 + 1
(14n + 3,7n + 1) = (7n +1,1) =