II. Số nguyên:
1. Số nguyên và phép chia :
Trong phần sau đây kí hiệu Z để chỉ tập hợp các số 0,
±
1,
±
2, .... Khi x
∈
Z ta nói x là một
số nguyên. Bản thân Z được gọi là tập các số nguyên.
Ta cũng chấp nhận tiên đề sau đây – gọi là tiên đề về tối thứ tự (well - ordering axiom):
“Mọi tập khác rổng của các số nguyên không âm đều có phần tử nhỏ nhất.”
Điều này có nghóa là: Nếu S là tập hợp khác rổng các số nguyên
≥
0 thì tồn tại một số nguyên
n
∈
S sao cho n
≤
x đối với mọi x
∈
S
Đònh nghóa : Cho hai số nguyên a và b với a
≠
0, ta nói a chia hết cho b nếu tồn tại số nguyên c
sao cho a = bc. Khi đó ta cũng nói b chia hết a hoặc b là ước số của a hoặc a là bội số của b.
Kí hiệu: b | a.
Ví dụ: 13 | 182 17 | 0.
Chú ý rằng trong đònh nghóa nói trên ta không đònh nghóa phép chia cho 0 mặc dù, cũng theo
đònh nghóa trên, 0 chia hết cho mọi số nguyên.
Đònh lý 1: Nếu a, b, c là các số nguyên sao cho c | b và b | a thì c | a.

Từ (1) và (2) suy ra: am+bn=k
1
cm+k
2
cn=(k
1
m+k
2
n) c
QED
Đònh lý 3 : Với mọi số nguyên a và b sao cho b > 0 tồn tại duy nhất một bộ hai số nguyên
không q và r với 0
≤
r < b sao cho:
a = bq + r.
Chứng minh:
Ta cần chứng minh hai điều:
Sự tồn tại của q và r:
32
Gọi S là tập mọi số nguyên có dạng a –bk trong đó k
∈
Z: S =
{ }
|a bk k Z− ∈
.
Gọi T là mọi số nguyên không âm chứa trong S: T =
{ }
|( 0) ( )t t t S≥ ∧ ∈

Vậy T khác rổng vì với mọi số nguyên k sao cho k < a/b thì a-bk > 0. Theo tiên đề về tối thứ tự thì

)+ (r
1
-r
2
) hay: r
2
-r
1
=b(q
1
-q
2
).
Hay b chia hết r
2
-r
1
.
Từ
1
0 r b≤ <
và
2
0 r b≤ <
ta có: -b < r
2
– r
1
< b.
Nên b chia hết r

q:=q+1
End
r:=a
return(q,r)
Trong thực tế tính toán không ai chia như vậy cả. Nhưng thuật toán đó có độ phức tạp thời gian là O(n) và
trong máy tính không cần phải thiết kế một mạch chia
1
mà vẫn thực hiện được phép chia nguyên một cách
hiệu quả như thường.
Đònh nghóa: Số nguyên tố là số nguyên dương khác 1 và chỉ chia hết cho 1 và cho chính nó.
Các số nguyên dương khác 1 và không phải số nguyên tố gọi là hợp số.
Đònh lý cơ bản của số học: Mọi số nguyên dương đều có thể phân tích được một cách duy nhất
thành tích các thừa số nguyên tố sai khác một sự sắp xếp thứ tự các thừa số đó.
1
Sẽ được trình bày trong mục biểu diễn số nguyên trong máy tính.
33
Ví dụ: 100 = 2.2.5.5 =2
2
5
2
999 = 3.3.3.37 = 3
3
.37
Chúng ta chấp nhận không chứng minh đònh lý đó.
Đònh lý 4: Nếu n là một hợp số thì n có ước số nguyên tố bé hơn hoặc bằng
n
Chứng minh:
Vì n là một hợp số nên n phải viết được thành dạng n = ab với 1<a<n và 1<b<n.
Nếu (a >
n

phải là số nguyên tố hay không:
34
Procedure KiemTraNguyenTo(n: số nguyên dương)
Ketqua:=TRUE
IF (n>1) THEN
Begin
i:=2
WHILE (i
≤

n
) DO
Begin
IF ( i | n) THEN
Begin
KetQua:=FALSE
i:=(phần nguyên của
n
)+1
End
ELSE i:=i+1
End
End
ELSE KetQua:=FALSE
Return(KetQua)
ƯỚC SỐ CHUNG LỚN NHẤT – BỘI SỐ CHUNG NHỎ NHẤT.
Đònh nghóa: Cho a và b là hai số nguyên không đồng thời bằng 0. Số nguyên d lớn nhất sao cho
d|a và d|b gọi là ước số chung lớn nhất của a và b và được kí hiệu là UCLN(a,b).
Theo đònh nghóa trên và theo các tính chất đã học ta thấy rằng nếu d=UCLN(a,b) thì, giả sử (a–
b >b), d cũng là UCLN(a-b,b). Thật vậy nếu d là ước chung lớn nhất của a và b thì d cũng là ước chung

t:=a
a:=b
b:=t
End
a:=a-b
End
Return(a)
Việc xác đònh hai số nguyên không có ước số chung nào ngoài 1 có một vò trí rất quan trọng
trong các phép tính.
Đònh nghóa: Các số nguyên a và b gọi là nguyên tố cùng nhau nếu UCLN(a,b)=1.
Đònh nghóa : Các số nguyên a
1
,a
2
,a
3
, ..., a
n
gọi là đôi một nguyên tố cùng nhau nếu:
n...1j,n...1i =∀=∀
: i
≠
j
⇒
UCLN(a
i
,a
j
)=1
Đònh nghóa: Bội số chung nhỏ nhất của hai số nguyên a và b là số nguyên dương nhỏ nhất chia

-k
1
) m +r với (0
≤
r < m)
Vậy a và b có cùng dư số trong phép chia cho m.
2) Ngược lại nếu a và b có cùng dư số trong phép chia cho m thì



+=
+=
rmkb
rmka
2
1
⇒
a-b = (k
1
-k
2
) m
⇒
m | (a-b).
Ví dụ: 22
≡
4 (mod 9) vì 9 | (22-4)=18
3
≡
-6 (mod 9) vì 9 | (3+(-6))

Z : a
≡
a (mod m)
b) Tính đối xứng (Symmetric):
∀
a, b
∈
Z : a
≡
b (mod m)
⇒
b
≡
a (mod m)
c) Tính truyền (Transitive):
∀
a, b, c
∈
Z : a
≡
b (mod m) và b
≡
c (mod m)
⇒
a
≡
c (mod m)
Chứng minh
Chứng minh các tính chất a) và b) là đơn giản, xin nhường cho người đọc.
Để chứng minh c) , ta có:

≡
8
≡
12
≡
16 (mod 4)
... -7
≡
-3
≡
1
≡
5
≡
9
≡
13
≡
17 (mod 4)
... -6
≡
-2
≡
2
≡
6
≡
10
≡
14

)m(modba
⇒




≡
+≡+
)m(modbdac
)m(moddbca
với mọi số nguyên a,b,c,d
(Chứng minh khá đơn giản nên dành cho người đọc.)
37
Đònh lý 9: Nếu a, b, c là các số nguyên sao cho m>0, ta có:



=
≡
)m,c(UCLNd
)m(modbcac

⇒
a
≡
b (mod (m/d))
Chứng minh
Vì ac
≡
bc (mod m) suy ra m | (ac-bc). Từ đó:

0

≡
b (mod m) nên x
1
cũng là một nghiệm của (1). Nói cách khác nếu (1)
có nghiệm thì nó cũng có một họ nghiệm. Vì vậy nói đến các Hàn Tín điểm binhnghiệm của (1) là nói
đến các nghiệm (nếu có) không đồng dư modulo m với nhau. Các đònh lý dưới đây sẽ dẫn ta đến việc
xác đònh các nghiệm đó (nếu có).
Đònh lý 10: Nếu d=UCLN(a,m) với a, m là các số nguyên dương không đồng thời bằng 0 thì
tồn tại các số nguyên s và k sao cho d là số nguyên dương nhỏ nhất thoả d = as+mk.
Chứng minh:
Xét tập H gồm các số nguyên dương dạng as+mk. Tập H
≠

φ
vì 1.a+0.m
∈
H, do đó tồn tại
phần tử d nhỏ nhất thuộc H. Ta có thể viết d = as+mk với s,k
∈
Z.
Theo thuật chia Euclide ta có a= dq + r, 0
≤
r < d .
Vậy: r = a – dq = a – (as+mk)q = a(1 – sq) + m(-kq)
∈
H
Nhưng 0
≤

Do đó nếu b không chia hết cho d sẽ dẫn đến mâu thuẩn. Nói cách khác phương trình ax+my=b
vô nghiệm.
Trường hợp 2: Giả sử b chia hết cho d.
d = UCLN(a,m). Vậy theo đònh lý 10 tồn tại các số nguyên s và k sao cho:
d = as+mk (*)
Vì d | b nên tồn tại e sao cho b = de. (**)
Từ (*) và (**): b = de = (as + mk)e = a (se) + m (ke) (***)
Từ (***) ta có: (x
0
,y
0
) với x
0
=se và y
0
=ke là một nghiệm của ax+my=b.
Bây giờ đặt x=x
0
+(m/d)t và y=y
0
– (a/d)t với t
∈
Z. (****)
Ta có: ax+my=ax
0
+a(m/d)t + my
0
-m(a/d)t=ax
0
+my

0
-y).
Vậy:
∃
t
∈
Z : ( y
0
-y) = (a/d)t.
Hay y=y
0
– (a/d)t (++)
Thay (++) vào (+), được: a(x-x
0
) = m(a/d)t.
Hay x =x
0
+ (m/d)t. Chứng minh tương tự được y=y
0
-(a/d)t.
QED
2
Phương trình dạng này còn có tên gọi là Phương trình vô đònh hay phương trình Diophant (gọi theo tên nhà
toán học Ai cập Diophantus (250 - ?).
39