ĐẠI HỌC ĐÀ NẴNG
TRƯỜNG ĐẠI HỌC SƯ PHẠM
KHOA TỐN

KHĨA LUẬN TỐT NGHIỆP
Đề tài:
ĐỒNG DƯ THỨC VÀ ỨNG DỤNG

Sinh viên thực hiện

: Huỳnh Thanh Thảo

Chuyên ngành

: Sư phạm Toán học

Lớp

: 11ST

Người hướng dẫn

: TS. Nguyễn Ngọc Châu

Đà Nẵng, tháng 5 năm 2015


MỤC LỤC
MỞ ĐẦU

1

MỘT SỐ KÍ HIỆU VÀ CHỮ VIẾT TẮT TRONG ĐỀ TÀI

2

Chương 1: KIẾN THỨC CƠ SỞ

3

1.1. Chia hết và chia có dư trong vành các số ngun

3

1.1.1. Tính chia hết

3

1.1.2. Phép chia có dư

4

1.2. Ước chung lớn nhất (ƯCLN)

4

1.2.1. Ước chung, ước chung lớn nhất

4

1.2.2. Số nguyên tố cùng nhau


5

1.2.3. Tìm ước chung lớn nhất của hai số nguyên - Thuật toán
Ơ-clit

5

1.3. Bội chung nhỏ nhất (BCNN)

9

1.4. Biểu diễn số ngun

9

1.5. Phương trình Đi -ơ-phăng

10

1.5.1. Phương trình Đi -ơ-phăng bậc nhất

10

1.5.2. Tập hợp nghiệm ngun

11

1.5.3. Tìm nghiệm riêng của phương trình Đi -ơ-phăng bằng
thuật tốn Ơ-clit mở rộng


13

1.6. Hàm số Ơle  (m)

17

Chương 2:

19

ĐỒNG DƯ THỨC VÀ ỨNG DỤNG

2.1. Đồng dư thức

19

2.2. Tập các lớp thặng dư - Hệ thặng dư đầy đủ - Hệ thặng dư thu gọn

21

2.2.1. Tập các lớp thặng dư

22

2.2.2. Hệ thặng dư đầy đủ

23

2.2.3. Hệ thặng dư thu gọn


25

2.3. Phương trình đ ồng dư bậc nhất một ẩn

29


2.3.1. Một số khái niệm về phương trình đồng dư

29

2.3.2. Nghiệm của phương trìn h đồng dư

30

2.3.3. Phương trình đ ồng dư bậc nhất một ẩn

32

2.3.4. Mối liên hệ giữa phương trình đ ồng dư bậc nhất và
phương trình Đi-ơ-phăng bậc nhất hai ẩn.
2.4. Một số ứng dụng của đồng dư thức

36
37

2.4.1. Tìm số dư trong một phép chia

37


2.4.2. Chứng minh sự chia hết

38

2.4.3. Dấu hiệu chia hết cho 2k ; 5k với k  *

40

2.4.4. Tìm chữ số tận cùng

41

2.4.5. Ứng dụng phương trình đ ồng dư để giải phương
trình Đi -ơ phăng

44

2.5. Tính cyclic của nhóm nhân các phần tử khả nghịch của vành các số
nguyên môđun m.

47

2.5.1. Vành  m các lớp thặng dư môđun m

47

2.5.2. Căn nguyên thủy

48


KẾT LUẬN

57

TÀI LIỆU THAM KHẢO

58


MỞ ĐẦU
Lý thuyết đồng dư là một nội dung quan trọng của lý thuyết số. Phương
pháp đồng dư do nhà Toán học người Đức C.Gauss (1777-1855) đề xuất, là
một phương pháp hữu ích trong cơng việc giải quyết nhiều vấn đề liên quan
đến các số nguyên. Phương pháp đồng dư cho phép chuyển việc nghiên cứu
trên một tập vô hạn về nghiên cứu trên một tập hữu hạn. Bằng công cụ
đồng dư, nhiều định lí tốn học đã được chứng minh cũng như gi ải quyết
được nhiều bài toán phức tạp trong số học.
Trong chương trình tốn bậc phổ thơng, môn số học và đặc biệt là lý
thuyết số chưa được dành nhiều thời gian, vì thế mà học sinh thường lúng
túng khi giải các bài toán số học, đặc biệt là trong các kì thi học sinh giỏi.
Nhằm tìm hiểu lý thuyết đồng dư cũng như nh ững ứng dụng của nó, tơi
chọn đề tài khóa luận của mình là: “Đ ồng dư thức và ứng dụng”.
Nội dung của khóa luận được chia làm hai chương:
Chương 1: Kiến thức cơ sở
Chương này trình bày một số kiến thức cơ sở của vành số ngun cùng
với phương trình Đi -ơ-phăng bậc nhất, để làm tiền đề cho phần sau.
Chương 2: Đồng dư thức và ứng dụng
Chương này trình bày cơ sở của lý thuyết đồng dư cùng những ứng
dụng của nó để giải một số bài tốn số học thuộc chương trình phổ thơng

trung học. Phần cuối của chương này dành cho việc xác định số nguyên
dương m sao cho nhóm *m là nhóm cyclic.

1


MỘT SỐ KÍ HIỆU VÀ CHỮ VIẾT TẮT TRONG ĐỀ TÀI
 : tập hợp số tự nhiên

 * : tập hợp số nguyên dương

 : tập hợp số nguyên
 : tập hợp các số thực
 m : tập hợp các lớp thặng dư môđun m
*m : tập hợp các lớp thặng dư môđun m nguyên tố với m

b│a : b chia hết a hay b là ước của a
b  a : b chia hết cho a hay b là bội của a

 (m) : số các số tự nhiên không vượt quá m  1 và nguyên tố với m
  x  : tập hợp các đa thức của ẩn x với hệ số nguyên

ƯC(a, b): tập hợp các ước chung của hai số nguyên a và b
BC(a, b) : tập hợp các bội chung của hai số nguyên a và b
ƯCLN : ước chung lớn nhất
BCNN : bội chung nhỏ nhất
ƯCLN  a1 , a2 , ... an  : ước chung lớn nhất dương của a1 , a2 , ... an
BCNN  a1 , a2 , ... an  : bội chung nhỏ nhất dương của a1 , a2 , ... an

a (mod m) : tập hợp các số nguyên đồng dư với a theo môđun m


a  b (mod m) : a đồng dư với b theo môđun m
Hệ TDĐĐ : hệ thặng dư đầy đủ môđun m
Hệ TDTG : hệ thặng dư thu gọn môđun m

2


Chương 1: KIẾN THỨC CƠ SỞ
Chương này trình bày một số kiến thức cơ sở của vành số nguyên cùng
với phương trình Đi-ơ-phăng bậc nhất, để làm tiền đề cho phần sau. Các chi
tiết liên quan có thể tìm xem trong 1 ,  2 , 3 , 5 , 8.

1.1. Chia hết và chia có dư trong vành các số nguyên
1.1.1. Tính chia hết
Định nghĩa 1.1.  2
Giả sử a và b là hai số nguyên, với a  0 , ta nói, a chia hết b
(hay a là một ước của b) và viết a│b nếu tồn tại một số nguyên c sao
cho b  ac .
Khi ấy, ta cịn nói b chia hết cho a hay b là bội của a và viết
b  a.

Ví dụ 1.1.
3 chia hết 12 hay 12 chia hết cho 3 , vì 12  (3).(4) .

Tính chất 1.1. 8
a) 1│a với mọi a   .
b) Nếu a│b và b│c thì a│c .
c) Nếu a  0 và a│b thì a  b .
n


d) Nếu a│bi thì a│ bi xi với mọi xi   .
i 1

e) Quan hệ chia hết trong  có tính phản xạ, bắc cầu, nhưng khơng có
tính đối xứng và tính phản đối xứng.

3


1.1.2. Phép chia có dư
Định lí 1.1. 5
Với mỗi cặp số nguyên a, b cho trước, b  0 , tồn tại duy nhất cặp
số nguyên q, r thỏa mãn các hệ thức
a  bq  r

0  r  b

Ta nói rằng a chia cho b được thương q và dư r.

1.2. Ước chung lớn nhất (ƯCLN)
1.2.1. Ước chung, ước chung lớn nhất
Định nghĩa 1.2. 8
Số nguyên d là một ước chung của các số nguyên a1 , a2 , ... , ak nếu
d

là ước đồng thời của mỗi số nguyên đó, khi đó ta viết

d


ƯC( a1 , a2 , ... an ).
Một ước chung d của các số nguyên a1 , a2 , ... , ak

mà mọi ước

chung của a1 , a2 , ... , ak đều là ước của d thì d được gọi là ước chung
lớn nhất (ƯCLN) của các số đó.
Chú ý 1.1. 1
a) Tập hợp các ước chung của hữu hạn số cho trước trùng với tập hợp các
ước của một ước chung lớn nhất của các số đó.
b) Nếu tất cả các số a1 , a2 , ... , ak đều bằng 0 thì tập hợp các ước chung
của chúng là 

0 .

Khi ấy, khái niệm ước chung lớn nhất khơng có

nghĩa nữa. Mặt khác, tập hợp các ước chung của các số đang xét không
thay đổi nếu ta thêm hay bớt một số bằng 0. Bởi vậy, có thể giả thiết các
số a1 , a2 , ... , ak đang xét đồng thời khác 0.

4


c) Nếu d là một ƯCLN của a1 , a2 , ... , ak thì –d cũng là m ột ƯCLN
của các số đó. Hơn nữa, nếu d và d ' cùng là ƯCLN của a1 , a2 , ... , ak
thì d '   d .

Do đó, ta sẽ lấy số dương


d

trong các ƯCLN của

a1 , a2 , ... , ak làm ƯCLN của chúng và kí hiệu d  ƯCLN( a1 , a2 , ... , ak ).

d) Với chú ý trên ta có thể định nghĩa: Ư ớc chung lớn nhất của các số
nguyên a1 , a2 , ... , ak

là số lớn nhất trong tập hợp các ước chung của

chúng.
1.2.2. Số nguyên tố cùng nhau
Định nghĩa 1.3. 3
a) Các số nguyên a1 , a2 , ... , ak được gọi là nguyên tố cùng nhau nếu như
ƯCLN( a1 , a2 , ... , ak )  1.
b) Các số nguyên a1 , a2 , ... , ak được gọi là đôi một nguyên tố cùng nhau
hay ngun tố sánh đơi nếu hai số bất kì trong chúng nguyên tố cùng nhau.
Chú ý 1.2.
Các số nguyên đơi một ngun tố cùng nhau thì ngun tố cùng nhau
nhưng điều ngược lại thì khơng đúng.
Ví dụ 1.2.
a) 4, 7, 15 là đơi một ngun tố cùng nhau vì ƯCLN(4, 7)  ƯCLN(7, 15)

 ƯCLN(4, 15)  1.
b) 6, 10, 15 là nguyên tố cùng nhau vì ƯCLN(6, 10, 15)  1, nhưng
không đôi một nguyên tố cùng nhau.
1.2.3. Tìm ước chung lớn nhất của hai số nguyên - Thuật toán Ơ-clit
Với hai số nguyên a, b mà a  0, b  0 , và a  b , ta có
Mệnh đề 1.1. 1

Giả sử a, b, c, q là những số nguyên thỏa mãn a  bq  c .
5


Khi ấy ta có ƯCLN(a, b)  ƯCLN(b, c).
Thuật tốn Ơ-clit 1
Cho trước hai số nguyên a và b (a  b  0) , tìm số tự nhiên d sao
cho d  ƯCLN(a, b), người ta tiến hành như sau: Thực hiện phép chia có
dư a cho b ta được a  bq  r , 0  r  b .
Đặt

r0  a, r1  b, q1  q, r2  r .

Vậy với hai số nguyên

a  r0 , b  r1 cho trước (a  b  0) tồn tại hai số nguyên q1 , r2 sao

cho r0  r1 q1  r2 , 0  r2  r1 .
Bước 1: Nếu r2  0 nghĩa là b(  r1 ) chia hết a (  r0 ) . Khi ấy
d  ƯCLN(a, b)  ƯCLN( r0 , r1 )  r1  b .

Quá trình kết thúc.
Bước 2: Nếu r2  0 nghĩa là
r0  r1 q1  r2 , 0  r2  r1 .

Khi ấy theo mệnh đề ta có
ƯCLN(a, b)  ƯCLN( r0 , r1 )  ƯCLN( r1 , r2 ).
Thực hiện phép chia có dư r1 cho r2 ta có
r1  r2 q2  r3 , 0  r3  r2


Nếu r3  0 ta có d  r2 . Q trình kết thúc.
Cịn nếu r3  0 ta quay lại Bước 2,…
Thực hiện liên tiếp quá trình này ta được dãy giảm nghiêm ngặt những
số tự nhiên r1  r2  r3  ...  0 nên dãy này phải dừng, nghĩa là có số
tự nhiên n ( n  b ) sao cho rn 1  rn qn . Khi ấy, tồn bộ q trình đó là
r0  r1 q1  r2 , 0  r2  r1 ( a  r0 , b  r1 )
r1  r2 q2  r3 , 0  r3  r2

………….
6


rn  2  rn 1 qn 1  rn , 0  rn  rn 1
rn 1  rn qn .

Khi đó d  ƯCLN(a, b)  ƯCLN( r0 , r1 )  ƯCLN( r1 , r2 )  … 
ƯCLN( rn 1 , rn )  rn .
Quá trình như trên gọi là thuật tốn Ơ-clit tìm ư ớc chung lớn nhất thực
hiện trên hai số a và b.
Như vậy ƯCLN(a, b) bằng số dư khác không cuối cùng trong thuật
tốn này.
Ví dụ 1.3.
Cho hai số ngun dương a  804, b  288 . Hãy tìm ư ớc chung lớn
nhất d của a và b.
Trong thực hành khi sử dụng thuật tốn Ơ-clit để tìm d  ƯCLN(804, 288)
người ta thường đặt phép tính như sau:

804 288

228

60
48

12

48

288

228

60

1

2

3

1

0 4
Ta được ƯCLN(804, 288)  12 .
Nhận xét 1.1.
Nếu hai số a, b có một số bằng 0 thì ư ớc chung lớn nhất của chúng là
số còn lại.

7



Thuật toán Ơ-clit mở rộng 1
Với hai số nguyên a, b cho trước (a  b  0) , luôn tồn tại ước chung
lớn nhất d của chúng và cặp số nguyên x, y sao cho d  ax  by . Ta
đã có thu ật tốn Ơ-clit tìm ư ớc chung lớn nhất d, từ đây ta suy ra được
một thuật tốn cho phép tìm đồng thời d  ƯCLN(a, b) và cặp số nguyên
x, y sao cho d  ax  by . Thuật toán như vậy được gọi là thuật toán Ơclit mở rộng.
Theo thuật toán Ơ-clit như trên ta có d  rn cho nên để tìm cặp số
nguyên x, y sao cho

ax  by  d  rn , ta tìm cơng thức tính của

xk , yk sao cho ở từng bước của thuật toán Ơ-clit xảy ra đẳng thức
rk  axk  byk

(*)

Vì r0  a  a .1  b . 0 , nên có thể lấy x0  1, y0  0 .
Tiếp theo, vì r1  b  a . 0  b .1 , nên có thể lấy x1  0, y1  1 .
Giả sử đã tính đư ợc xk  2 , yk  2 , xk 1 , yk 1 ( k  2 ), ta hãy tìm cơng thức
truy hồi tính xk , yk (k  n) . Từ rk  2  rk 1 qk 1  rk suy ra
rk  rk  2  rk 1 qk 1
 (axk  2  byk  2 )  (axk 1  byk 1 ) qk 1
 a ( xk  2  xk 1 qk 1 )  b( yk  2  yk 1 qk 1 )

cho nên ta có thể lấy
 xk  xk  2  xk 1 qk 1

 yk  yk  2  yk 1 qk 1

(2  k  n).


Khi thuật toán Ơ-clit kết thúc tức là lúc rn 1  0 , thuật toán Ơ-clit mở
rộng kết thúc, ta được

d  rn

và đẳng thức

(*)

trở thành

rn  axn  byn với xn  xn  2  xn 1 qn 1 , yn  yn  2  yn 1 qn 1 .

8


Vậy khi rn 1  0 thuật toán Ơ-clit mở rộng kết thúc, bấy giờ ta được
d  rn , x  xn , y  yn thỏa mãn d  ƯCLN(a, b) và ax  by  d .

1.3. Bội chung nhỏ nhất (BCNN)
Định nghĩa 1.4. 8
Số nguyên

b

là một bội chung của các số nguyên khác không

a1 , a2 , ... , ak nếu b là bội của đồng thời mỗi số nguyên đó, khi đó ta viết


b  BC( a1 , a2 , ... , ak ).

Một bội chung b của các số nguyên khác không a1 , a2 , ... , ak sao
cho mọi bội chung của a1 , a2 , ... , ak đều là bội của b được gọi là bội
chung nhỏ nhất (BCNN) của các số đó.
Chú ý 1.3.
a) Tập hợp các bội chung của hữu hạn số nguyên cho trước trùng với tập
hợp các bội của một bội chung nhỏ nhất của các số đó.
b) Nếu b là một BCNN của a1 , a2 , ... , ak thì –b cũng là m ột BCNN
của các số đó. Hơn nữa, nếu b và b ' cùng là BCNN của a1 , a2 , ... , ak thì
b '   b . Do đó, ta sẽ lấy số dương b trong hai BCNN của a1 , a2 , ... , ak

làm BCNN của chúng và kí hiệu b  BCNN ( a1 , a2 , ... , ak ).
c) Với chú ý trên ta có thể định nghĩa: Bội chung nhỏ nhất của các số
nguyên a1 , a2 , ... , ak là số nhỏ nhất trong tập hợp các bội chung dương
của chúng.

1.4. Biểu diễn số nguyên
Định lí 1.2.  2
Giả sử b là một số nguyên và b  1. Khi đó mọi số nguyên
dương

n

đều có thể viết một cách duy nhất dưới dạng

9


n  ak b k  ak 1b k 1  ...  a1b1  a0 , trong đó k   , a j là số nguyên,

0  a j  b  1 với j  0, 1, 2, ... , k đồng thời ak  0 .

Biểu diễn số n với điều kiện trên được gọi là khai triển b phân của n,
các số a0 , a1 ,..., ak được gọi là các chữ số, trong đó
a0 được gọi là chữ số hàng đơn vị
a1 được gọi là chữ số hàng b1
a2 được gọi là chữ số hàng b 2

…
ak được gọi là chữ số hàng b k .

Ta cũng kí hi ệu n  (ak ak 1 ... a1 a0 )b .
Chú ý 1.4.
Ta thường khai triển n dưới dạng thập phân, tức là khai triển n với
b  10 .

Ví dụ 1.4.
1052  1.103  0.102  5.101  2.100

1.5. Phương trình Đi -ơ-phăng
1.5.1. Phương trình Đi -ơ-phăng bậc nhất
Định nghĩa 1.5. 8
Xét phương trình ax  by  c

(1)

ở đó a, b, c là những số nguyên cho trước, a và b đồng thời khác
khơng, x và y là các số ngun cần tìm. Khi đó, ta gọi phương trình (1)
là phương trình Đi -ô-phăng bậc nhất hai ẩn, a và b gọi là hệ số của ẩn, c
gọi là số hạng tự do.


10


Định lí 1.3. (điều kiện có nghiệm) 8
Điều kiện cần và đủ để phương trình (1) có nghiệm ngun là ước
chung lớn nhất của các hệ số của ẩn là ước của số hạng tự do.
Chứng minh:
Điều kiện cần: Giả sử phương trình (1) có nghiệm ngun, nghĩa là có
cặp số nguyên x0 , y0 sao cho có đẳng thức ax0  by0  c . Gọi d 
ƯCLN(a, b). Khi ấy, d là ước của a và b nên d là ước của ax0  by0
nghĩa là d là ước của c.
Điều kiện đủ: Giả sử d  ƯCLN(a, b) là ước của c, nghĩa là có s ố
nguyên c1 sao cho c  c1d . Ta phải chứng minh phương trình (1) có
nghiệm ngun, nghĩa là có cặp số nguyên x0 , y0 sao cho xảy ra đẳng
thức ax0  by0  c .
Thật vậy, vì d  ƯCLN(a, b) nên ắt có cặp số nguyên x1 , y1 sao
cho d  ax1  by1 .

Nhân hai vế của đẳng thức này với c1 ta được

dc1  a (c1 x1 )  b (c1 y1 ) , tức là c  a (c1 x1 )  b(c1 y1 ) .

Đẳng thức này chứng tỏ cặp số nguyên x0  c1 x1 , y0  c1 y1 là một
nghiệm nguyên của phương trình (1).
Hệ quả 1.1.
Nếu ƯCLN(a, b)  1 thì phương trình (1) có nghiệm ngun.
1.5.2. Tập hợp nghiệm ngun
Định lí 1.4.  2
Nếu phương trình (1) có một nghiệm ngun ( x0 , y0 ) thì nó có vơ số

nghiệm ngun và tập hợp các nghiệm ngun của nó gồm các cặp số
nguyên ( x, y) xác định bởi:

11


b

x

x

t
0

d
,

a
y  y  t
0

d

d  ƯCLN(a, b) ; t  0,  1,  2,...

Chứng minh:

b
a 


Với mỗi t , cặp  x0  t , y0  t  là một nghiệm của phương
d
d 

trình (1). Thật vậy, theo giả thiết ( x0 , y0 ) là một nghiệm của phương
trình (1) nên ta có đẳng thức ax0  by0  c , từ đó

b 
a 


a  x0  t   b  y0  t   c
d 
d 


b
a 

Đẳng thức này chứng tỏ  x0  t , y0  t  là một nghiệm nguyên
d
d 

của phương trình (1).
Bây giờ, giả sử ( x1 , y1 ) là nghiệm nguyên tùy ý của phương trình (1),
ta phải chứng minh rằng có một số nguyên t sao cho x1  x0 
y1  y0 

b

t,
d

a
t.
d

Thật vậy, vì ( x0 , y0 ) , ( x1 , y1 ) là hai nghiệm của phương trình (1)
nên ta có
ax0  by0  c,
ax1  by1  c

Các đẳng thức này cho ta a ( x1  x0 )  b( y0  y1 )
hay

a
b
( x1  x0 )  ( y0  y1 )
d
d

Đẳng thức sau cùng chứng tỏ

b
d

| ad ( x  x ) .
1

12


0


Nhưng
b
d

|x

1

d  ƯCLN(a, b)

nên

a b
ƯCLN  ,   1,
d d 

 x0 , nghĩa là tồn tại số nguyên t sao cho x0  x1 

x1  x0 

suy ra

b
t hay
d


b
a
b
t . Từ đây, cùng với đẳng thức
( x1  x0 )  ( y0  y1 )
d
d
d

ta được y1  y0 

a
t.
d

1.5.3. Tìm nghiệm riêng của phương trình Đi -ơ-phăng bằng thuật tốn
Ơ-clit mở rộng 1
Xét phương trình Đi-ô-phăng bậc nhất hai ẩn ax  by  c

(1)

với d  ƯCLN(a, b) là một ước của c, chẳng hạn c  dc ' ( c' ).
Thực hiện thuật tốn Ơ-clit mở rộng trên hai số a, b tìm được số
nguyên d, hai số nguyên x ', y ' và có đẳng thức a x '  b y '  d . Nhân
hai vế của đẳng thức này với c ' sẽ được a (c ' x ')  b (c ' y ')  dc ' .
Đẳng thức sau cùng này chứng tỏ c ' x ' , c ' y ' là nghiệm riêng của
phương trình (1) và áp dụng Định lí 1.4 ta được tất cả các nghiệm ngun
của nó.
Ví dụ 1.5. Tìm các nghiệm nguyên của phương trình:


1821x  675 y  6
Giải:
Trước hết ta tìm cặp số nguyên x, y sao cho 1821x  675 y  d , với
d  ƯCLN (1821,675) .

Thực hiện thuật toán Ơ-lit mở rộng trên hai số 1821 và 675, ta có bảng
sau:

13


i

q

r0

r1

r2

x0

x1

x2

y0

y1


y2

0

2

1821

675

471

1

0

1

0

1

-2

1

1

675


471

204

0

1

-1

1

-2

3

2

2

471

204

63

1

-1


3

-2

3

-8

3

3

204

63

15

-1

3

-10

3

-8

27


4

4

63

15

3

3

-10

43

-8

27

-116

5

5

15

3


0

-10

43

27

-116

Nhìn vào bảng trên ta được d  ƯCLN(1821, 675)  3 , x  43,

y   116 và có đẳng thức 1821.43  675.(116)  3 .
Suy ra

1821.86  675.(232)  6

đẳng thức này chứng tỏ

(x  86, y   232) là một nghiệm riêng của phương trình đã cho và do
đó nghiệm tổng qt của nó là

675

 x  86  3 t  86  225t
, t  0,  1,  2 ,…

1821
 y   232 

t   232  607t

3
Ví dụ 1.6. Tìm các số tự nhiên n có hai chữ số sao cho n chia hết cho 9
và n  1 chia hết cho 25.
Giải:
Trước hết ta tìm n sao cho n  9 x, x  và n  1  25 y, y  .
Từ

đó

dẫn

đến

phương

trình

Đi-ơ-phăng

9 x  25 y  1

hay

25.4  9.11  1

nên

25 y  9 x  1.

Áp dụng thuật toán Ơ-clit mở rộng ta có

x 0  11, y0  4 là một nghiệm riêng của phương trình trên nên nó có
 x  11  25t
nghiệm tổng quát là 
, t  .
 y  4  9t
14


Mà n là một số tự nhiên có hai chữ số nên ta phải lấy t  0 và ta
được n  99 .
Nhận xét 1.2. 1
Để đi đến cách thực hành giải phương trình (1), ta có nh ận xét sau:
a) Nếu a hoặc b

bằng 1 thì việc tìm nghiệm nguyên của phương

trình (1) coi như được giải quyết.
Thật vậy, chẳng hạn

a 1

thì phương trình

(1)

trở thành

x  by  c có tập hợp nghiệm nguyên gồm các cặp số nguyên (x, y) ở

đó
 x  c  bt
,

y  t

t  0,  1,  2 ,…

b) Nếu a và b đều lớn hơn 1, ta có mệnh đề sau:
Mệnh đề 1.2. 1
Nếu a và b đều lớn hơn 1, bao giờ cũng có thể chuyển việc tìm
nghiệm ngun của phương trình (1) v ề việc tìm nghiệm nguyên của một
phương trình b ậc nhất hai ẩn mà có ít nhất một hệ số của ẩn là 1 .
Chứng minh:
Thật vậy, giả sử 1  a  b , thêm nữa ta có thể giả thiết a  0 .
Thực hiện phép chia có dư b cho a ta được b  aq  a1 ; a1 , q  ,
0  a1  a .

Nếu a1  0, b  aq thì phương trình (1) tr ở thành ax  aqy  c .
Nhưng ƯCLN(a, b)  ƯCLN(a, aq)  a

là ước của c, chẳng hạn

c  ac1 , c1   , nên phương trình (1) tương đương v ới phương trình
x  qy  c1 có một hệ số của ẩn là 1.

15


Nếu 0  a1  a


thì bằng cách đặt

x  qy  z  ta được

az  a1 y  c (2) với 0  a1  a  b .

Mỗi nghiệm nguyên ( x0 , y0 ) của phương trình (1) cho ta m ột nghiệm
nguyên ( z1 , y1 ) của phương trình (2), ở đó z1  x0  qy0 , y1  y0 .
Ngược lại mỗi nghiệm nguyên ( z1 , y1 ) của phương trình (2) cho ta
một nghiệm nguyên ( x0 , y0 ) của phương trình (1), ở đó x0  z1  qy1 ;
y0  y1 .

Như vậy việc tìm nghiệm nguyên của phương trình (1) chuyển về việc
tìm nghiệm nguyên của phương trình (2) , với 0  a1  a  b .
Bây giờ ta lại xét phương trình (2). Thực hiện phép chia có dư a cho
a1 ta được a  a1 q1  a2 , 0  a2  a1 .

Nếu

a2  0, a  a1 q1

thì

phương

trình

(2)


tr ở

thành

a1 q1 z  a1 y  c . Nhưng a1  ƯCLN (a1 q1 , a1 )  ƯCLN (a, a1 ) 

ƯCLN(b, a) là ước của c, chẳng hạn c  a1 c2 , c2   nên phương trình
(2) tương đương với phương trình q1 z  y  c2 có hệ số của ẩn là 1.
Nếu 0  a2  a1 ta tiếp tục lặp lại lí luận như trên. Quá trình này d ẫn
đến dãy các số tự nhiên b  a  a1  a2  ... giảm dần, nên sau không
quá a bước ta chuyển được việc tìm nghiệm nguyên của phương trình (1)
về việc tìm nghiệm nguyên của một phương trình b ậc nhất hai ẩn với hệ số
ngun có ít nhất một hệ số của ẩn là 1 . Mệnh đề được chứng minh.
Ví dụ 1.7. Giải phương trình vơ đ ịnh
17x  47y  5.
Giải:
Vì

 47  17.(3)  4 nên ta viết phương trình dư ới dạng

17 ( x  3 y)  4 y  5 .

16


Đặt ( x  3 y )  z  ta được phương trình 17 z  4 y  5 .
Vì 17  4.4  1 nên phương trình này được viết dưới dạng

4 ( y  4 z)  z  5 .
Đặt y  4 z  t  ta được phương trình 4t  z  5 .

Đây là phương trình bậc nhất hai ẩn số có hệ số của ẩn z là 1, nó cho
ta z  5  4t , t   .
Từ đó,

y  t  4 z  t  4 (5  4t )   20  17 t

x  z  3 y  (5  4t )  3 (  20  17t )   55  47t .
Vậy phương trình cho có nghiệm là
 x   55  47t

 y   20  17t ,

t  0,  1,  2,...

1.6. Hàm số Ơle  (m)
Định nghĩa 1.5. 1
Cho số nguyên dương m. Ta định nghĩa hàm s ố  (m) như sau:
Với m  1 ta đặt  (m)  1 .
Với m  1,  (m) là số các số tự nhiên không vượt quá m  1 và
nguyên tố với m.
Ví dụ 1.8.
 (2)  1,  (6)  2,  (12)  4,  ( p )  p  1 (ở đó p là một số

nguyên tố).
Mệnh đề 1.2. 1
 (m) là hàm số có tính chất nhân, nghĩa là với a và b là hai số

nguyên dương nguyên tố cùng nhau thì (ab)  (a ).(b) .

17



Định lí 1.2. 1
a) Với m  1 ta có  (1)  1 ;
b) Với p là một số nguyên tố và  là một số tự nhiên khác 0 ta có

1
 ( p )  p  p 1  p 1   ;
p


c) Với số tự nhiên
m  p11 p2 2 ... pk k

m 1

ta có

có dạng phân tích tiêu chuẩn là

1 
1  
1 
 (m)  m 1  1   ... 1   .
p1 
p2  
pk 


18



Chương 2:

ĐỒNG DƯ THỨC VÀ ỨNG DỤNG

Chương này trình bày cơ sở của lý thuyết đồng dư cùng những ứng
dụng của nó để giải một số bài tốn số học thuộc chương trình phổ thơng
trung học. Phần cuối của chương này dành cho việc xác định các số nguyên
dương m sao cho nhóm *m là nhóm cyclic.

2.1. Đồng dư thức
Định nghĩa 2.1. 8
Cho m là một số nguyên dương. Hai số nguyên a và b đồng dư với
nhau theo môđun m nếu hiệu a  b chia hết cho m.
Khi a và b đồng dư với nhau theo môđun m ta viết a  b (mod m)
và gọi đó là một đồng dư thức, khi a không đồng dư với b theo môđun m
ta viết a  b (mod m) .
Nhận xét 2.1.

a  b (mod m) khi và chỉ khi a và b chia cho m (với thuật toán Ơclit) thì nhận cùng một số dư.
Ví dụ 2.1.
a) 10  2 (mod 8) , 11  9 (mod 10) .
b) 12  3 (mod 11) , 25  3 (mod 13) .
Mệnh đề 2.1.  2
Nếu a, b là các số nguyên thì a  b (mod m) khi và chỉ khi tồn tại
số nguyên t sao cho a  b  mt .
Chứng minh:

19



Giả sử a  b (mod m) , khi đó m │ a  b , tức là a  b  tm với
số nguyên

t nào đó. Ngược lại, nếu tồn tại số nguyên

t

sao cho

a  b  tm thì m │ a  b , tức là a  b (mod m) .

Tính chất 2.1.  2
2.1.1. Quan hệ đồng dư là một quan hệ tương đương trên tập số nguyên  ,
nghĩa là
a) a   :

a  a (mod m);

b) a, b   : a  b (mod m)  b  a (mod m);
c) a, b, c   : a  b (mod m) , b  c (mod m)  a  c (mod m).
2.1.2. a) Ta có thể cộng hoặc trừ từng vế của nhiều đồng dư thức theo cùng
một môđun. Cụ thể là
ai  bi (mod m), i  1, n
 a1  a2  ....  ak  b1  b2  b3    bk ( mod m)

b) Ta có thể nhân từng vế của nhiều đồng dư thức theo cùng một môđun.
Cụ thể là
ai  bi (mod m), i  1, n  a1 a2 ... ak  b1 b2 ...bk (mod m)


Hệ quả 2.1.  2
a) a  b (mod m)  a  c  b  c (mod m)
b) a  c  b (mod m)  a  b  c (mod m)
c) a  b (mod m)  a  km  b (mod m), k 
d) a  b (mod m)  ac  bc (mod m)
e) a  b (mod m)  a n  b n (mod m), với n  , n  0 .
f) Giả sử f ( x) là một đa thức với hệ số nguyên và    (mod m) .
Khi ấy ta có f ( )  f (  ) (mod m) .
Đặc biệt nếu có f ( )  0 (mod m)
20


thì ta cũng có f (  km)  0 (mod m) , k  .
2.1.3. Ta có thể chia hai vế của một đồng dư thức cho một ước chung của
chúng nguyên tố với môđun. Cụ thể là

ac  bc (mod m) và ƯCLN (c, m)  1  a  b (mod m) .
2.1.4. a) Ta có thể nhân hai vế và môđun của một đồng dư thức với cùng
một số nguyên dương. Cụ thể là

a  b (mod m)  ac  b c (mod mc), với c  , c  0 .
b) Ta có thể chia hai vế và môđun của một đồng dư thức cho một ước
chung dương của chúng. Cụ thể là

a  b (mod m), 0   ,  ƯCLN (a, b, m) 

a
b
m


(mod ) .




2.1.5. Nếu hai số đồng dư với nhau theo nhiều mơđun thì chúng đ ồng dư
với nhau theo môđun là bội chung nhỏ nhất của các môđun ấy. Cụ thể là

a  b (mod mi ), i  1, 2,..., k
 a  b (mod m) , m  BCNN (m1 , m2 ,..., mk ) .

2.1.6. Nếu hai số đồng dư với nhau theo một mơđun thì chúng cũng đ ồng
dư với nhau theo mơđun là ước chung dương của môđun ấy. Cụ thể là

a  b (mod m),  | m,   0  a  b (mod  ) .
2.1.7. Nếu hai số đồng dư với nhau theo một mơđun thì chúng có cùng ư ớc
chung lớn nhất với mơđun ấy. Cụ thể là

a  b (mod m)  ƯCLN (a, m)  ƯCLN (b, m) .

2.2. Tập các lớp thặng dư - Hệ thặng dư đầy đủ - Hệ thặng
dư thu gọn
Do quan hệ đồng dư môđun m là một quan hệ tương đương nên các
phần tử thuộc tập  sẽ được phân ra thành các lớp tương đương. Kí hiệu
 m là tập các lớp tương đương của quan hệ đồng dư môđun m. Lớp tương
21


đương chứa a   là a   x  , x  a (mod m) .

2.2.1. Tập các lớp thặng dư
Định nghĩa 2 .2. 8
Các lớp tương đương theo quan hệ đồng dư môđun m được gọi là các
lớp thặng dư môđun m.
Mỗi phần tử A của  m được gọi là một lớp thặng dư môđun m.
Mỗi lớp thặng dư A mơđun m có dạng a (mod m) , với a là một
phần tử tùy ý của A, phần tử a như thế được gọi là một đại diện của lớp
A và cũng còn g ọi là một thặng dư mơđun m.
Ví dụ 2.2.
Trong  8 , lớp thặng dư 3 (mod 8) là
3   x  │ x  3 (mod 8)  ...,  13,  5, 3, 11, 19, ...

Nhận xét 2.2. Ta có
a) b  a (mod m)  b  a (mod m)  b  a ,
b) b  a (mod m)  b  a (mod m)  b  a   .
Nhận xét 2.3.
Tất cả các thặng dư của cùng một lớp thặng dư có cùng ước chung lớn
nhất với mơđun. Từ đây, ta có định nghĩa sau:
Định nghĩa 2.3. 8
Ước chung lớn nhất của một lớp với môđun là ước chung lớn nhất của
một thặng dư tùy ý của lớp đó với mơđun.
Khi ƯCLN bằng 1, ta nói lớp thặng dư A là lớp nguyên tố với
mơđun.
Ví dụ 2.3.

22