Lớp thặng dư và hệ thặng dư. Các định lí cơ bản về đồng dư

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:29

Thêm vào BST

Báo xấu

23
lượt xem 1
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tài liệu "Lớp thặng dư và hệ thặng dư. Các định lí cơ bản về đồng dư" có ba nội dung chính được trình bày lồng ghép với nhau. Phần thứ nhất của bài học tập trung làm rõ các khái niệm lớp thặng dư và hệ thặng dư, khái niệm nghịch đảo modulo và cách vận dụng các khái niệm này trong các bài toán số học. Phần thứ hai trong bài học trình bày các định lí cơ bản về đồng dư, bao gồm định lí Fermat, định lí Euler, định lí Wilson và định lí Wolstenholme. Phần cuối cùng dành thời lượng để giới thiệu về quan hệ đồng dư trên Q.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Lớp thặng dư và hệ thặng dư. Các định lí cơ bản về đồng dư

§3. Lớp thặng dư và hệ thặng dư. Các định lí cơ bản về đồng dư Bài học này có ba nội dung chính được trình bày lồng ghép với nhau. Phần thứ nhất của bài học tập trung làm rõ các khái niệm lớp thặng dư và hệ thặng dư, khái niệm nghịch đảo modulo và cách vận dụng các khái niệm này trong các bài toán số học. Phần thứ hai trong bài học trình bày các định lí cơ bản về đồng dư, bao gồm định lí Fermat, định lí Euler, định lí Wilson và định lí Wolstenholme. Phần cuối cùng dành thời lượng để giới thiệu về quan hệ đồng dư trên  . Cần chú ý rằng vì mục đích sư phạm mà nhiều nội dung (đặc biệt là phần khái niệm) trong tài liệu này được phát biểu một cách hết sức nôm na (nhưng vẫn giữ được bản chất của khái niệm). Tài liệu tham khảo: Các bài giảng về số học, Nguyễn Vũ Lương (Chủ biên). Lectures of Modulo Arithmetic, Yufei Zhao. I. Nội dung bài học 1. Lớp thặng dư và hệ thặng dư Cho trước một số nguyên dương m . Ta biết rằng có vô hạn số nguyên, nhưng khi chia các số nguyên cho m thì các số dư thu được chỉ có thể là 0 , 1 , … và m 1 . Do đó tập các số nguyên có thể được phân hoạch thành m tập hợp: Tập A0 gồm các số chia hết cho m , Tập A1 gồm các số chia m dư 1 , … Tập Am1 gồm các số chia m dư m 1 . Để cho tiện, ta kí hiệu các tập hợp trên lần lượt là 0m , 1m , … và m 1m . Mỗi tập hợp trên được gọi là một lớp thặng dư modulo m . Nếu không có nhầm lẫn gì, đôi khi ta kí hiệu các lớp thặng dư trên là 0 , 1 , … và m 1 hoặc thậm chí đơn giản hơn nữa là 0 , 1 , … và m 1 . Ví dụ 1.1. Ta có 3, 2, 7  25 vì 3  7  2 (mod 5) . Định nghĩa. Cho m   . Một tập hợp m số nguyên a1 , a2 ,..., am  được gọi là một hệ thặng dư đầy đủ modulo m (hay hệ đầy đủ modulo m ) nếu m số này thuộc đúng m lớp thặng dư phân biệt modulo m . Nói cách khác, khi đem m số a1 , a2 ,..., am chia cho m ta thu được đúng m số dư là 0,1,..., m1 . Ví dụ 1.2. (a) 0,1, 2,3, 4 và 12,8, 1,5, 4 là các hệ thặng dư đầy đủ modulo 5 . (b) 3;12; 9;8; 5 không là hệ thặng dư đầy đủ modulo 5 vì 3  8 (mod 5) . Nhận xét 1. Từ Ví dụ 1.2 ta rút ra điều kiện cần và đủ để tập hợp m số nguyên a1 , a2 ,..., am  là một hệ thặng dư đầy đủ modulo m là ai  a j (mod m) với mọi i  j .  Trang 1
Mệnh đề 1. Cho m   . Giả sử a1 , a2 ,..., am  là một hệ thặng dư đầy đủ mod m . Khi đó (a) Với mọi b   thì a1  b, a2  b,..., an  b là một hệ thặng dư đầy đủ mod m . (b) Với mọi a   , (a, m)  1 thì aa1 , aa2 ,..., aam  là một hệ thặng dư đầy đủ mod m . Chứng minh (a) Áp dụng Nhận xét 1 ta chỉ cần chứng minh ai  b  a j  b (mod m) với mọi i  j , tức là  ai  a j (mod m) với mọi i  j . Tuy nhiên đây là điều hiển nhiên đúng do ai i1 là một hệ thặng  m dư đầy đủ mod m . (b) Giả sử aai i1 không là một hệ thặng dư đầy đủ mod m , khi đó tồn tại i, j  1, 2,..., m , m i  j sao cho aai  aa j (mod m) . Do đó a (ai  a j )  m , mà (a, m)  1 nên ta có ai  a j  m , mâu thuẫn với giả thiết ai i1 là một hệ thặng dư đầy đủ mod m . m Lưu ý. Giả thiết a và m nguyên tố cùng nhau ở kết quả (b) đóng vai trò then chốt, nếu thiếu giả thiết này thì aai i1 không thể là hệ thặng dư đầy đủ mod m . Để dễ hình dung, ta có ví dụ sau. m Ví dụ 1.3. Xét hệ thặng dư đầy đủ mod 12 0,1, 2,3, 4,5, 6, 7,8,9,10,11 . Khi “nhân” hệ thặng dư trên với 8 ta được 0,8,16, 24,32, 40, 48,56, 64, 72,80,88  0, 4,8 (mod12) . Rõ ràng hệ mới không là hệ thặng dư đầy đủ mod 12 . Nhận xét 2. (a) Từ kết quả của Mệnh đề 1 ta rút ra hệ quả dưới đây “Cho a, b   , (a, m)  1 . Nếu x chạy khắp một hệ thặng dư đầy mod m thì ax  b cũng chạy khắp một hệ thặng dư đầy đủ mod m ”. (b) Cho m   , a   và (a, m)  1 . Do 1, 2,..., m là một hệ đầy đủ mod m nên theo Mệnh đề 1 (b) ta thấy a.1, a.2,..., a.m là một hệ thặng dư đầy đủ mod m , do đó trong tập hợp này phải chứa một số nguyên có dạng ax , với x  1, 2,..., m , sao cho ax  1 (mod m) . Số nguyên dương x như vậy được gọi là một nghịch đảo của a modulo m . Nghịch đảo của a modulo m không là duy nhất, chẳng hạn 2 và 7 đều là nghịch đảo của 3 modulo 5 vì 3.2  3.7  1 (mod 5) . Tuy nhiên tất cả các nghịch đảo của a modulo m đều đồng dư với nhau theo mod m (như trong ví dụ trên ta có 2  7 (mod 5) ). Do đó nghịch đảo của a modulo m là duy nhất theo modulo m . Bởi vậy ta có thể kí hiệu chung các nghịch đảo của a modulo m là a1 . Ví dụ 1.4. Ta có 51  3 (mod 7) và 61  2 (mod13) . Cũng cần phải chú ý thêm rằng chỉ có các số a nguyên tố cùng nhau với m mới có nghịch đảo modulo m . Ví dụ 1.3 là một minh chứng cho khẳng định này khi 81 mod12 không tồn tại. Trang 2
Sau đây ta cùng xem xét một số bài toán mà việc vận dụng khái niệm hệ thặng dư đầy đủ đóng vai trò then chốt. Ví dụ 1.5. Tìm tất cả các số nguyên tố p sao cho p  2 và p  4 cũng là các số nguyên tố. Hướng dẫn giải Dễ thấy  p, p  2, p  4   p, p 1, p  2 (mod 3) nên  p, p  2, p  4 là một hệ đầy đủ mod 3 . Do đó trong ba số p, p  2, p  4 phải có đúng một số chia hết cho 3 , mà chúng đều là các số nguyên tố nên p  3 . Với p  3 thử lại ta thấy p  2  5 , p  4  7 là các số nguyên tố. Ví dụ 1.6. [Định lí Bézout] Cho các số nguyên dương a và b . Khi đó (a) Nếu gcd(a, b)  1 thì tồn tại x, y   sao cho ax  by  1 . (b) Nếu gcd(a, b)  d thì tồn tại x, y   sao cho ax  by  d . Chứng minh (a) Thực ra yêu cầu bài toán tương đương với việc chứng minh sự tồn tại của x   sao cho ax  1 (mod b) . Tuy nhiên theo Nhận xét 2 (b) thì số x cần chọn chính là nghịch đảo của a mod b . 1 ax Khi đó ta đặt y  thì y   và ax  by  1 . b (b) Đặt a  a1d và b  b1d thì gcd(a1 , b1 )  1 . Khi đó tồn tại nghịch đảo x của a1 mod b1 . 1 a1 x Đặt y  thì y   và a1 x  b1 y  1 , do đó ax  by  d . b1 Lưu ý. Hãy chỉnh sửa chứng minh (a) để thu được khẳng định sau “Nếu gcd(a, b)  1 thì tồn tại x, y   sao cho ax  by  1 ”. Ví dụ 1.7. Cho a, b, c là các số nguyên dương thỏa mãn c 2 1  a(a  b)(a  2b) . Chứng minh rằng b chia hết cho 12 . Hướng dẫn giải Dễ thấy nếu b không chia hết cho 3 thì a, a  b, a  2b là một hệ thặng dư đầy đủ modulo 3 , khi đó a(a  b)(a  2b)  3 . Bởi vậy theo giả thiết ta có c 2 1  3 , vô lí vì c 2  0,1 (mod 3) . Giả sử a chẵn, khi đó a(a  2b)  4 , thành ra c 2 1  4 , vô lí vì c 2  0,1 (mod 4) . Do đó a phải là số lẻ. Theo kết quả Bài 3.10 (a) (§1) thì c 2 1 không có ước nguyên tố dạng 4k  3 nên hai ước lẻ a và a  2b của c 2 1 phải có dạng 4k  1 , tức là a  a  2b  1 (mod 4) . Từ đó suy ra 2b  0 (mod 4) nên b chẵn. Nhưng khi đó thì a  b là ước lẻ của c 2 1 nên a  b cũng phải có dạng 4k  1 , nghĩa là a  b  1 (mod 4) , kéo theo b  0 (mod 4) , hay b  4 . Trang 3
BÀI TẬP ĐỀ XUẤT Bài 1.1. Cho p là một số nguyên tố lẻ. Chứng minh   p 1 (a) 0, 1, 2,...,   là một hệ thặng dư đầy đủ mod p .    2     2 2  p 12   (b) 1 , 2 ,...,      là một hệ gồm các thặng dư phân biệt mod p .     2       (c) 12 , 2 2 ,..., ( p 1) 2 , p 2  không là một hệ thặng dư đầy đủ mod p . Bài 1.2. [May Olympiad 2021] Theo quan niệm của nhiều người, Thứ Sáu ngày 13 được cho là ngày xui xẻo và thường đem lại tai họa bất ngờ cho họ. (a) Chứng minh rằng trong một năm dương lịch có ít nhất một ngày là Thứ Sáu ngày 13 . (b) Trong một năm có thể có bao nhiêu ngày là Thứ Sáu ngày 13 ? Bài 1.3. Cho p là một số nguyên tố lẻ và a1 , a2 ,..., a p là các số nguyên. Chứng minh nếu ai i1 p là một hệ đầy đủ mod p thì (a) a1  a2  ...  a p  0 (mod p) . (b) a12  a2  ...  a 2  0 (mod p ) , với p  3 . 2 p Bài 1.4. Tìm tất cả các số nguyên dương n sao cho số 36n  6 là tích của các số nguyên dương liên tiếp. Bài 1.5. Cho x, y là các số nguyên và p là một số nguyên tố. Giả sử tồn tại các số nguyên dương m, n nguyên tố cùng nhau thỏa mãn mx  ny (mod p) . Chứng minh rằng tồn tại một số nguyên z sao cho x  nz (mod p ) và y  mz (mod p) . Bài 1.6. [Putnam MC 2017] Giả sử S là tập con nhỏ nhất của  thỏa mãn các điều kiện (i) 2  S . (ii) Với mọi n   , nếu n 2  S thì n  S . (iii) Với mọi n   , nếu n  S thì (n  5) 2  S . (a) Chứng minh rằng 3, 4, 6  S . (b) Tìm tập hợp S . 2. Định lí Fermat nhỏ1 Định lí 2.1. [Định lí Fermat] Cho p là một số nguyên tố. Khi đó (a) Nếu x   và x không chia hết cho p thì x p1  1 (mod p) . (b) Nếu x   thì x p  x (mod p) . Chứng minh Nếu để ý kĩ ta sẽ thấy hai mệnh đề (a) và (b) là tương đương, nên ta chỉ cần chứng minh (a). Do gcd( x, p)  1 nên theo Mệnh đề 1 (b) thì  x.0, x.1,..., x.( p 1) là một hệ đầy đủ mod p . 1 Định lí này được gọi là định lí Fermat nhỏ (Fermat’s little theorem) để phân biệt với định lí Fermat lớn hay định lí cuối cùng của Fermat (Fermat’s last theorem) – một bài toán kinh điển gây khó dễ cho nhân loại trong suốt ba thế kỉ. Trang 4
Bởi vậy  x.1, x.2,..., x.( p 1)  1, 2,..., p 1 (mod p) . Khi đó ( x.1)( x.2)...( x.( p 1))  1.2...( p 1) (mod p) , hay ( p 1)! x p1  ( p 1)! (mod p) . Do ( p 1)!  1.2...( p 1) nguyên tố cùng nhau với p nên ta có x p1  1 (mod p) . Ví dụ 2.1. Cho n   . Chứng minh 1112 n6  1 chia hết cho 13 . Hướng dẫn giải Theo định lí Fermat nhỏ ta có 11  1 (mod13) . Do đó 12 1112 n6 1  (1112 )n .116 1  116 1  (2)6 1  65  0 (mod13) . Ví dụ 2.2. (a) Chứng minh nếu p là số nguyên tố dạng 4k  3 thì x 2  1 (mod p) .  Từ đó chứng minh “Nếu p là số nguyên tố dạng 4k  3 , x, y   và x 2  y 2  p thì x, y  p ”. (b) Chứng minh nếu p là số nguyên tố dạng 8k  5 thì x 4  1 (mod p) .  (c) Tìm tất cả các cặp số nguyên dương ( x, y ) sao cho x 4  y 4  19971999 . Hướng dẫn giải (a) Khẳng định thứ nhất đã được chứng minh trong Bài 3.10 (a) (§1). Bây giờ ta chứng minh khẳng định thứ hai. Giả sử x không chia hết cho p . Theo giả thiết thì x 2  y 2  p nên y 2  x 2 (mod p) (1) . Mà gcd( x, p)  1 nên tồn tại nghịch đảo a : x1 của x mod p . Từ (1) ta có (ay )2  (ax)2  1 (mod p) . Điều này dẫn tới mâu thuẫn với khẳng định thứ nhất. Vậy x  p , do đó y  p . (b) Giả sử trái lại x 4  1 (mod p) . Đặt p  8k  5 thì x p1  x8k 4  ( x 4 )2 k 1  (1)2 k 1  1 (mod p) , mâu thuẫn với định lí Fermat nhỏ. (c) Từ kết quả (b) ta có thể chứng minh nếu p là số nguyên tố dạng 8k  5 , x và y là các số nguyên thỏa mãn x 4  y 4  p thì x, y  p . Để ý rằng 1997 là số nguyên tố dạng 8k  5 nên x 4  y 4  1997  x, y  1997 . Lại vì 1999 là số nguyên tố dạng 4k  3 nên x 4  y 4  1999  x, y  1999 Vậy tất cả các cặp số cần tìm là các cặp bội nguyên dương của số 1997 1999 . Trang 5
4 p 1 Ví dụ 2.3. Cho p là số nguyên tố, p  3 . Chứng minh nếu n  thì 2n  2 (mod n) . 3 Hướng dẫn giải Nhận xét rằng n là một số lẻ nên điều cần chứng minh tương đương với 2n1 1  n , hay 22 p 1 22 p 4 2 1  3 (1) . 3 Để chứng minh (1) , mạnh dạn hơn ta nghĩ đến việc chứng minh 2 2 p 4 2 3 1  22 p 1 (2) . Kết quả của Ví dụ 2.2 cho ta biết rằng (2) xảy ra khi và chỉ khi 22 p  4  2 p (3) . 3 22 p  4 Dễ thấy 22 p  4  4(4 p1 1)  2.3 nên m : là một số nguyên chẵn (4) . 3 Hơn nữa theo định lí Fermat ta lại có 4 p1  1 (mod p) , do đó 4(4 p1 1)  p . Do p  3 nên (3, p)  1 , thành thử ta có 4(4 p1 1)  3 p , do đó m  p (5) . Từ (4) và (5) ta suy ra (3) . Ta có điều phải chứng minh. Lưu ý. Số nguyên dương n trong bài toán trên là một hợp số nhưng có tính chất tựa như số nguyên tố 2n1  1 (mod n) . Số nguyên dương n như vậy được gọi là một số giả nguyên tố cơ sở 2 (a pseudo-prime to base 2 ). Một cách tổng quát, cho a là một số nguyên lớn hơn 1 . Nếu n là một hợp số và a n1  1 (mod n) thì n được gọi là một số giả nguyên tố cơ sở a . Ví dụ 2.4. Tồn tại hay không một dãy vô hạn các số nguyên tố p1  p2  ...  pn  ... thỏa mãn pn1  2 pn 1 với mọi n  1 ? Hướng dẫn giải  Giả sử tồn tại dãy số ( p ) n n1 thỏa mãn yêu cầu bài toán. Theo giả thiết ta có pn1 1  2( pn 1) với mọi n  1 . Lặp lại quá trình trên ta được pn1  1  2( pn  1)  2 2 ( pn1  1)  ...  2 n ( p1  1) với mọi n  1 . Do đó pn  2n1 ( p1  1) 1 với mọi n  1 . Để chỉ ra mâu thuẫn, ta chọn n  p1 . Trường hợp p1  2 , ta có thể loại bỏ số hạng này của dãy số và chỉ xét các số hạng từ p2 trở đi. Bởi vậy không mất tính tổng quát ta có thể giả sử p1  2 . Khi đó ta có p p1  2 p11 ( p1  1) 1  ( p1  1) 1  0 (mod p1 ) . Điều này chứng tỏ p p1  p1 , kéo theo p p1  p1 và do đó p1  1 , mâu thuẫn. Trang 6
BÀI TẬP ĐỀ XUẤT Bài 2.1. Chứng minh nếu p là một số nguyên tố lẻ thì (a) 1p1  2 p1  ...  ( p 1) p1  1 (mod p) . (b) 1p  2 p  ...  ( p 1) p  0 (mod p ) . Bài 2.2. Tìm tất cả các số nguyên tố p sao cho 5 p 1 chia hết cho p 2 . 2 Bài 2.3. Cho p là một số nguyên tố lẻ, a và b là các số nguyên dương lẻ sao cho a  b  p và a  b  p 1 . Chứng minh rằng ab  b a chia hết cho 2 p . Bài 2.4. Cho p là số nguyên tố lớn hơn 3 . Chứng minh 3 p  2 p 1  42 p . Bài 2.5. [Canada MO 1983] Cho p là một số nguyên tố. Chứng minh tồn tại vô hạn n   sao cho 2n  n  p . Bài 2.6. Chứng minh rằng tồn tại vô hạn số nguyên dương n sao cho 2n  8  n . Bài 2.7.* Cho a   , a  1 . Chứng minh rằng tồn tại vô hạn số giả nguyên tố cơ sở a . n1 Bài 2.8.* [Kazakhstan MO 2017] Chứng minh tồn tại vô hạn hợp số n sao cho 2 2 1  n . 4 1 p Gợi ý. Chọn n  . 5 Bài 2.9.* [Singapore MO 2006] Chứng minh không tồn tại dãy tăng ngặt các số nguyên tố ( pn ) 1 n thỏa mãn pn1  2 pn  1 với mọi n  1 . Bài 2.10.* Tìm tất cả các đa thức hệ số nguyên P( x) thỏa mãn P(n)  0 và P (n) 2n 1 với mọi n   . 3. Định lí Euler 3.1. Hệ thặng dư thu gọn Xét một hệ thặng dư đầy đủ modulo 6 A  0,1, 2,3, 4,5 . Trong A nếu ta bỏ đi những số có ước chung (khác 1 ) với 6 và chỉ giữ lại những phần tử nguyên tố cùng nhau với 6 thì ta thu được tập hợp mới là A  1,5 . Tập hợp này được gọi là một hệ thặng dư thu gọn modulo 6 . Ta có định nghĩa dưới đây. Định nghĩa. Từ một hệ thặng dư đầy đủ modulo m nếu ta trích ra những phần tử nguyên tố cùng nhau với m thì ta thu được một tập hợp gọi là một hệ thặng dư thu gọn modulo m (hay hệ thu gọn mod 6 ). Nhận xét 3.1. Vì mọi hệ đầy đủ mod m đều bằng 1, 2,..., m mod m nên số phần tử của một hệ thu gọn mod m đúng bằng số các số nguyên dương không vượt quá m và nguyên tố cùng nhau với m . Ta kí hiệu số này là (m) (đọc là “phi của m”). Hàm số  : m  *  (m) được gọi là phi-hàm Euler. Trang 7
Ví dụ 3.1. (a) 1,3,5,9,11,13 là một hệ thặng dư thu gọn mod 14 , do đó (14)  6 . (b) 1,5, 7,11,13,17 là một hệ thặng dư thu gọn mod 18 , do đó (18)  6 . (c) Với p là một số nguyên tố thì 1, 2,3,..., p 1 là một hệ thặng dư thu gọn mod p , nên  ( p )  p 1 . Từ Ví dụ 3.1 (c) ta thấy ( p )  p 1 với mọi số nguyên tố p . Câu hỏi đặt ra là làm thế nào để tính số (m) trong trường hợp m không phải là số nguyên tố? Câu trả lời cho câu hỏi này có trong Mệnh đề 3.1, nhưng trước tiên ta sẽ chứng minh hai bổ đề dưới đây. Bổ đề 3.1. Nếu p là số nguyên tố và k   thì ( p k )  p k  p k 1 . Chứng minh Hiển nhiên gcd(a, p k )  1  gcd(a, p)  1 , nên hệ thu gọn mod p k chỉ gồm những phần tử không chia hết cho p . Mặt khác, trong các số nguyên dương từ 1 đến p k có đúng p k 1 số chia hết cho p . Do đó số các số nguyên dương không vượt quá p k và nguyên tố cùng nhau với p là p k  p k 1 . Vậy ( p k )  p k  p k 1 . Bổ đề được chứng minh. Bổ đề 3.2. Phi-hàm Euler là một hàm nhân tính, nghĩa là (mn)  (m)(n) với mọi m, n   , (m, n)  1 . Chứng minh Rõ ràng một số nguyên tố cùng nhau với mn khi và chỉ khi nó nguyên tố cùng nhau với cả m và n . Do đó ta sẽ đếm số các số nguyên dương  mn và nguyên tố cùng nhau với cả m và n . Để dễ hình dung về cách đếm cho trường hợp tổng quát, ta hãy xét trường hợp m  5, n  8 . Ta viết tất cả các số nguyên dương từ 1 đến mn  40 theo bảng dưới đây 1 2 3 4 5 6 7 8 8 1 8 2 83 8 4 85 86 87 2.8 2.8  1 2.8  2 2.8  3 2.8  4 2.8  5 2.8  6 2.8  7 3.8 3.8  1 3.8  2 3.8  3 3.8  4 3.8  5 3.8  6 3.8  7 4.8 4.8  1 4.8  2 4.8  3 4.8  4 4.8  5 4.8  6 4.8  7 5.8 Trong bảng trên: - Những số nguyên tố cùng nhau với n  8 là những số nằm ở cột j với ( j , n)  1 (trong trường hợp này những cột như thế là các cột 1,3,5, 7 và được tô màu). Số các cột j như thế bằng (n) . - Ở mỗi cột j nói trên, các phần tử đều có dạng kn  j với k  0,1, 2,..., m 1 . Mặt khác ta biết rằng tập hợp các số này kn  j : 0  k  m 1 là một hệ đầy đủ mod m , do đó số các số trong cột j mà nguyên tố cùng nhau với m đúng bằng (m) . Trang 8
Do mỗi cột j chứa (m) số nguyên tố cùng nhau với m nên cũng chứa (m) số nguyên tố cùng nhau với mn . Mà có tất cả (n) cột j nên cả bảng có tất cả (m)(n) số nguyên tố cùng nhau với mn . Vậy (mn)  (m)(n) . Bổ đề được chứng minh. Mệnh đề 3.1. [Công thức xác định phi-hàm Euler] Cho số nguyên dương n  1 có phân tích tiêu chuẩn n  p11 p2 2 ... pk k ,   trong đó p1  p2  ...  pk là các số nguyên tố và 1 , 2 ,..., k    . Khi đó  1  1  1  (n)  n 1  1  1  .            p1    p2    pn  Chứng minh  Do các số p11 , p2 2 , …, pk k đôi một nguyên tố cùng nhau nên áp dụng Bổ đề 3.2 ta được   (n)   ( p11 )( p2 2 )... ( pk k ) .   Lại áp dụng Bổ đề 3.1 ta được  (n)   p11  p11 1  p2 2  p2 2 1 ... pk k  pk k 1       p11 1 p2 2 1... pk k 1 ( p1 1)( p2 1)...( pk 1)    1  1  1  n 1 1  1  .            p1  p2      pn  Ví dụ 3.2. Kiểm tra lại các giá trị của (14) và (18) được tính bằng định nghĩa trong Ví dụ 3.1.  1  1  (a)  (14)   (2.7)  14 1 1   6 .  2  7         1  1  (b)  (18)   (2.32 )  18 1 1   6 .  2  3        Định lí 3.1. [Định lí Euler] Cho m   , x   và gcd( x, m)  1 . Khi đó x ( m)  1 (mod m) . Chứng minh Tương tự hóa chứng minh của định lí Fermat nhỏ, ta có chứng minh dưới đây. Giả sử a1 , a2 ,..., a ( m )  là một hệ thặng dư thu gọn mod m . Khi đó do ( x, m)  1 nên  xa1 , xa2 ,..., xa ( m )  gồm các hệ thặng dư phân biệt và nguyên tố cùng nhau với m , do đó  xa1 , xa2 ,..., xa ( m )  cũng là một hệ thu gọn mod m . Từ đó suy ra ( xa1 )( xa2 )...( xa ( m ) )  a1a2 ...a ( m ) (mod m) . Do (a1a2 ...a ( m ) , m)  1 nên giản ước hai vế ta thu được x ( m)  1 (mod m) . Trang 9
Nhận xét 3.2. (a) Ta thấy định lí Fermat nhỏ thực chất là một hệ quả của định lí Euler trong trường hợp m là một số nguyên tố. (b) Từ định lí Euler ta rút ra hệ quả dưới đây (cần chú ý đây là một hệ quả mà ta sẽ sử dụng khá thường xuyên). “Cho m   , x   và ( x, m)  1 . Khi đó a, b   , a  b (mod (m))  x a  xb (mod m) ”. 2022 Ví dụ 3.3. Tìm số dư của 20202021 khi chia cho 33 . Hướng dẫn giải Theo định lí Euler, ta biết rằng do gcd(2020, 33)  1 và (33)  20 nên 202020  1 (mod 33) . Theo Nhận xét 3.2 (b) ta cần tìm số dư của 20212022 khi chia cho 20 . Tuy nhiên rõ ràng ta thấy 20212022  12022  1 (mod 20) . Bởi vậy  20201  7 (mod 33) . 2022 20202021 Ví dụ 3.4. Chứng minh nếu n là số nguyên dương chẵn thì 2n! 1 chia hết cho n 2 1 . Hướng dẫn giải Hiển nhiên mệnh đề đúng với n  2 nên ta chỉ cần xét n  4 . Do n chẵn nên gcd(n 1, n 1)  gcd(2, n 1)  1 . Do đó ta cần chứng minh 2n! 1 chia hết cho cả n 1 và n  1 . Thật vậy, theo định lí Euler ta có 2 ( n1) 1  n 1 và 2 ( n1) 1  n 1 . Mặt khác, theo công thức phi-hàm Euler dễ thấy ( x)  x với mọi x   , x  1 . Bởi vậy (n 1)  n 1  n và (n  1)  n . Điều đó chứng tỏ n ! chia hết cho (n 1) và (n 1) . Thành thử 2n! 1  2 ( n1) 1  n 1 và 2n! 1  2 ( n1) 1  n  1 . Ta có điều phải chứng minh. Ví dụ 3.5. [IMO 1971] Chứng minh dãy số (2 n  3) n chứa một dãy con gồm vô hạn số đôi một nguyên tố cùng nhau. Hướng dẫn giải Ta xây dựng (bằng quy nạp) một dãy con tăng (an ) của dãy số đã cho thỏa mãn yêu cầu bài toán. Đầu tiên ta chọn a1  22  3  1 và a2  23  3  5 . Rõ ràng a1 , a2    và (a1 , a2 )  1 . Trang 10
Giả sử ta đã chọn được k số nguyên dương a1 , a2 ,..., ak trong dãy đôi một nguyên tố cùng nhau. Ta chứng minh tồn tại một số ak 1 có dạng 2n  3 nguyên tố cùng nhau với mỗi số a1 , a2 ,..., ak . Thật vậy, nếu đặt n  (a1a2 ...ak ) thì theo định lí Euler ta có 2n 1  a1a2 ...ak . Khi đó thì (2 n  3, a1a2 ...ak )  ((2 n 1)  2, a1a2 ...ak )  (2, a1a2 ...ak )  1 . Để đảm bảo ak 1  2n  3  ak , có thể chọn n  t(a1a2 ...ak ) với t đủ lớn. BÀI TẬP ĐỀ XUẤT Bài 3.1. (a) Mệnh đề đảo của Nhận xét 3.2 (b) có đúng hay không? Tức là nếu x a  xb (mod m) thì có phải ta luôn có a  b (mod  (m)) hay không? 2001 20012003 (b) Chứng minh các số 19971999 và 19971999 có hai chữ số tận cùng bên phải giống nhau. Bài 3.2. (a) Chứng minh nếu p, q là các số nguyên tố phân biệt thì p q1  q p1 1 chia hết cho pq . (b) Chứng minh nếu a, b là các số nguyên dương nguyên tố cùng nhau thì tồn tại vô hạn cặp số nguyên dương (r , s) sao cho a r  b s 1 chia hết cho ab . Bài 3.3. (a) Tìm tất cả các số nguyên dương n sao cho (n) là một số chẵn. (b) Cho n là một số nguyên dương. Chứng minh nếu (n) là một lũy thừa bậc nguyên dương của 2 thì mọi ước nguyên tố lẻ (nếu có) của n là số nguyên tố Fermat. (Số nguyên tố Fermat là một số nguyên tố p có dạng p  2 2  1 với k   ). k Bài 3.4. Chứng minh rằng với mọi s   , luôn tồn tại r   sao cho r là bội của s và tổng các chữ số của r (viết trong hệ thập phân) bằng s . Bài 3.5.* [Romania TST 1997] Cho a   , a  1 . Chứng minh tập hợp A  a n1  a n 1: n  *  chứa một tập con gồm vô hạn các phần tử đôi một nguyên tố cùng nhau. Bài 3.6. Cho số nguyên dương m  1 và tập hợp Am  1  k (2m  1) : k   . (a) Chứng minh tồn tại số nguyên dương a sao cho 2 a  Am . (b) Giả sử 2m  1 có ít nhất hai ước nguyên tố phân biệt, chứng minh tồn tại số nguyên dương a sao cho a  m và 2 a  Am . Bài 3.7.* [USA MO 1991] Cho n   và dãy số (ak ) xác định bởi a1  2 và ak 1  2ak với mọi k  1 . Chứng minh rằng (ak ) là dãy hằng modulo n . (Một dãy số nguyên được gọi là dãy hằng modulo n nếu kể từ một vị trí nào đó trở đi các số hạng của dãy số đều đồng dư với nhau mod n ). Trang 11
Bài 3.8. [Chuyên Sư Phạm Hà Nội TST 2019] (a) Cho a, b là các số nguyên dương có cùng tập các ước nguyên tố. Chứng minh  (a)  (b)  . a b (b) Cho số nguyên tố p  5 . Tìm tất cả các số nguyên dương x thỏa mãn ( x )  2 p . 4. Định lí Wilson Định lí 4.1. [Định lí Wilson] Cho p là một số nguyên tố. Chứng minh ( p 1)!  1 (mod p) (1) . Chứng minh Hiển nhiên (1) đúng với p  2 nên ta chỉ cần xét p  3 . Chú ý rằng S  1, 2,..., p 1 là một hệ thu gọn mod p và với mỗi x  S thì tồn tại duy nhất y  S sao cho xy  1 (mod p) . Ta kí hiệu số y duy nhất đó bởi x1 . Ta sẽ nhóm các thừa số trong tích ( p 1)!  1.2...( p 1) thành các cặp số ( x, x1 ) là nghịch đảo của nhau modulo p (khi đó tích của hai số thuộc cặp này đồng dư với 1 mod p ). Tuy nhiên với những số x mà x  x1 thì ta lại không thể ghép cặp. Điều này làm nảy sinh câu hỏi rằng khi nào thì x  x1 ? Rất đơn giản, ta có  x  1 (mod p) x  x1  x 2  1 (mod p)  ( x 1)( x 1)  0 (mod p )   .  x  p 1 (mod p) Vậy trong S chỉ có hai số x có nghịch đảo bằng chính nó là x  1 và x  p 1 . Hơn nữa cũng cần chú ý rằng nếu x  x  thì ta có x1  x 1 . Bởi vậy tích các số còn lại trong S 2.3...( p  3)( p  2) có thể được nhóm thành các cặp số là nghịch đảo của nhau. Điều này chứng tỏ 2.3...( p  3)( p  2)  1 (mod p) . Bởi vậy ta có ( p 1)!  1.( p 1)  1 (mod p) . Nhận xét 4.1. Mệnh đề đảo của định lí Wilson vẫn đúng, nghĩa là ta có “Nếu n  1 là một số nguyên dương thỏa mãn (n 1)!  1 (mod n) thì n là một số nguyên tố”. Thật vậy, giả sử ngược lại rằng n là hợp số. Khi đó ta có thể viết n  uv với 1  u  v  n . Nhưng khi đó thì u  n 1 , kéo theo (n 1)!  0 (mod u ) (1) . Mặt khác theo giả thiết thì (n 1)!  1 (mod u ) , mâu thuẫn với (1) . Điều đó chứng tỏ giả sử sai. Trang 12
Ví dụ 4.1. Cho p là một số nguyên tố. (a) Chứng minh ( p  2)!  1 (mod p) . (b) Tìm số dư của ( p  2)! khi chia cho p( p 1) . Hướng dẫn giải (a) Theo định lí Wilson ta có ( p 1)!  1  p 1 (mod p) . Do gcd( p 1, p)  1 nên giản ước p 1 ở cả hai vế ta thu được ( p  2)!  1 (mod p) (1) . (b) Kiểm tra trực tiếp ta thấy nếu p  2 hoặc p  3 thì ( p  2)! chia p( p 1) dư 1 . Xét p  5 . Trước hết ta có nhận xét rằng ( p  2)!  0 (mod p 1) (2) . Thật vậy, hiển nhiên (2) đúng với p  5 . p 1 Với p  5 , dễ thấy 2   p  2 nên 2  p 1   p 1   p 1 . ( p  2)!  1 2     ( p  2)  2      2     2    Tóm lại từ (1) và (2) ta có ( p  2)!  1 p (mod p)    . ( p  2)!  1 p (mod p)   Do đó ( p  2)! (1 p) chia hết cho p( p 1) . Vậy nếu p  5 thì dư trong phép chia ( p  2)! cho p( p 1) là 1 p  p( p 1)  ( p 1)2 . Ví dụ 4.2. Cho p là một số nguyên tố, p  2 . Giả sử ai i1 và bi i1 là các hệ thặng dư đầy đủ p p modulo p . Chứng minh ai bi i1 không là một hệ thặng dư đầy đủ modulo p . p Hướng dẫn giải Giả sử ai bi i1 là một hệ đầy đủ mod p . p Do ai i1 là một hệ đầy đủ mod p nên phải tồn tại một phần tử trong hệ  0 (mod p) . p Không mất tính tổng quát ta giả sử a1  0 (mod p) . Dễ thấy b1  0 (mod p) vì nếu trái lại thì tồn tại k  1 sao cho bk  0 (mod p) . Khi đó a1b1  ak bk  0 (mod p) , mâu thuẫn với giả sử ai bi i1 là một hệ đầy đủ mod p . p Vì a1  b1  0 (mod p) nên a2 , a3 ,..., a p  , b2 , b3 ,..., bp  và a2b2 , a3b3 ,..., a p bp  là các hệ thu gọn mod p . Khi đó a2 a3 ...a p  b2b3 ...bp  ( a2b2 )( a3b3 )...( a p bp )  1.2...( p 1) (mod p ) . Điều này mâu thuẫn với định lí Wilson cho rằng ( p 1)!  1 (mod p) . Trang 13
Ví dụ 4.3. Cho p là một số nguyên tố lẻ. Chứng minh rằng  p 1  p 1 2   2  (a) 1 .2 ...   (1) 2 2 2 (mod p ) .   (b) Nếu p là số nguyên tố dạng 4k  1 thì tồn tại x   sao cho x 2  1 chia hết cho p . Hướng dẫn giải (a) Theo định lí Wilson thì ( p 1)!  1 (mod p) (1) .   p 1  Các số từ 1 đến p 1 có thể chia thành các cặp (k , p  k ) với k  1, 2,...,  , do đó    2    p1 p1 ( p 1)!  1.2...( p 1)   k ( p  k ) 2 2 k 1 k 1 p1 p1 p1 p1 2  k  (k )  (1)  k 2 2 2 2 (mod p) (2) . k 1 k 1 k 1 Từ (1) và (2) ta suy ra p1 p1 2 (1) 2 k k 1 2  1 (mod p ) . p1 Chia cả hai vế của đồng dư thức cho (1) 2 ta được điều phải chứng minh. p1 (b) Đặt x   k ta có điều phải chứng minh. 2 k 1 Nhận xét 4.2. Từ kết quả Ví dụ 4.3 (b) và Bài 3.10 (a) (§1) ta có kết luận sau “Cho p là một số nguyên tố lẻ. Khi đó p là số nguyên tố dạng 4k  1 khi và chỉ khi tồn tại số nguyên x sao cho x 2  1 chia hết cho p ”. BÀI TẬP ĐỀ XUẤT Bài 4.1. [Estonia MO 2000] Chứng minh rằng không thể chia một tập hợp X gồm 18 số nguyên dương liên tiếp thành hai tập con rời nhau A và B sao cho tích các phần tử của tập hợp A bằng tích các phần tử của tập hợp B . Bài 4.2. [IMO 1970] Tìm tất cả các số nguyên dương n sao cho tập hợp n, n  1, n  2, n  3, n  4, n  5 có thể chia thành hai tập con rời nhau sao cho tích các phần tử của mỗi tập hợp bằng nhau. Bài 4.3. Cho p là một số nguyên tố lẻ. Chứng minh rằng (a)  ijk  0 (mod p ) . 1i j k  p1 p 1 (b)  1i p1 i 2 i  (1) 2 (mod p ) . Trang 14
Bài 4.4. Chứng minh rằng (a) Nếu p là một số nguyên tố và p  5 thì số ( p  2)!1 chia hết cho p nhưng không thể là một lũy thừa của p . (b) Tồn tại vô hạn n   sao cho số n !1 có ít nhất hai ước nguyên tố. Bài 4.5. [Olympic Trại hè Hùng Vương 2019] Tìm tất cả các số nguyên dương x, y thỏa mãn y x 1  ( y 1)! . Bài 4.6. Chứng minh rằng tồn tại vô hạn n   sao cho số n ! 1 có ít nhất hai ước nguyên tố. 5. Quan hệ đồng dư trên  Định nghĩa. Cho số nguyên dương n . Một số hữu tỉ x được gọi là đồng dư với 0 mod n nếu nó a được viết dưới dạng phân số tối giản với a, b   , a chia hết cho n và gcd(b, n)  1 . b Nói cách khác, ta định nghĩa a  0 (mod n)  a  0 (mod n), gcd(b, n)  1 . b Với x, y   , ta nói x và y đồng dư với nhau mod n nếu x  y đồng dư với 0 mod n x  y (mod n)  x  y  0 (mod n) . Ví dụ 5.1. Ta có 2 1 1 1  0 (mod 2) ,  (mod 5) ,  7 (mod 25) . 7 7 2 7 Nhận xét 5.1. x (a) Vì mỗi số nguyên x có thể được coi là một số hữu tỉ nên ta thấy quan hệ đồng dư trên  1 là một mở rộng của quan hệ đồng dư trên  , tức là   x, y  , x  y (mod n)  x  y (mod n) . (b) Do quan hệ đồng dư trên  cũng chỉ tập trung vào tử số của phân số tối giản nên quan hệ đồng dư trên  bảo toàn các tính chất của quan hệ đồng dư trên  . Với mọi a, b, c, d   , nếu a  c (mod n) và b  d (mod n) thì a  b  c  d (mod n) , ab  cd (mod n) . (c) Cho số nguyên dương n và số nguyên a nguyên tố cùng nhau với n . Do (a, n)  1 nên tồn tại nghịch đảo của a mod n , kí hiệu nghịch đảo này là a1 (chú ý a1   ). Khi đó ta có 1 a 1  (mod n) (1) . a 1 aa1 1 Thật vậy, xét hiệu a1   . a a Do (aa1 1, a)  (1, a)  1 và aa1 1  0 (mod n) nên theo định nghĩa ta có (1) . 1 Từ (1) ta thấy có thể coi là nghịch đảo của a mod n . a Trang 15
Ví dụ 5.2. Cho p là một số nguyên tố, p  3 . Chứng minh rằng nếu 1 1 1 a  2    , 12 2 ( p 1) 2 b với a, b   , (a, b)  1 thì a chia hết cho p . Hướng dẫn giải Thực chất ta cần chứng minh 1 1 1  2    0 (mod p ) . 12 2 ( p 1)2 Theo Nhận xét 5.1 (c) ta có 1 1 1  2    (11 ) 2  (21 ) 2  ...  (( p 1)1 )2 (mod p) . 12 2 ( p 1) 2 Mặt khác do 1, 2,..., p 1 là một hệ thu gọn mod p nên 11 , 21 ,..., ( p 1)1  cũng là một hệ thu gọn mod p . Do đó (11 ) 2  (21 ) 2  ...  (( p 1)1 )2  12  22  ...  ( p 1) 2 p ( p 1)(2 p 1)   0 (mod p ) . 6 Lưu ý. Trong bài toán trên ta cần giả thiết p  3 ở lập luận nào? Định lí 5.1. [Định lí Wolstenholme] Cho p là một số nguyên tố, p  3 . Khi đó 1 1 1    0 (mod p 2 ) . 1 2 p 1 Chứng minh Đặt p1  . 1 1 1 1 S :   1 2 p 1 k 1 k Khi đó 1 1  1  1    1 1 2S             .  1 p 1  2 p  2         p 1 1    1 p1  p1 2S    k p  k   k( p  k)   1   p . k 1   k 1  Để chứng minh S  0 (mod p 2 ) rõ ràng ta chỉ cần chứng minh p1 T :  2 1  0 (mod p ) . k 1 k( p  k) Thật vậy ta có p1 p1 T    2 (mod p) . 1 1 k 1 k (k ) k 1 k Theo kết quả của Ví dụ 5.2 ta có điều phải chứng minh. Trang 16
BÀI TẬP ĐỀ XUẤT Bài 5.1. [IMO 2005] Cho dãy số (an ) , trong đó an  2n  3n  6 n 1 với mọi n  * . Chứng minh rằng với mọi số nguyên tố p , tồn tại số nguyên dương n sao cho an chia hết cho p . Bài 5.2. [Iran MO 2017] Cho x, y là các số nguyên và p là một số nguyên tố. Giả sử tồn tại các số nguyên dương m, n nguyên tố cùng nhau thỏa mãn x m  y n (mod p) . Chứng minh rằng tồn tại duy nhất một số nguyên z mod p sao cho x  z n (mod p) và y  z m (mod p) . Bài 5.3.* [Singapore Open MO 2016] Cho n là một số nguyên tố. Chứng minh tồn tại một hoán vị (a1 , a2 ,..., an ) của (1, 2,..., n) sao cho a1 , a1a2 ,..., a1a2 ...an  là một hệ đầy đủ mod n . Bài 5.4. Cho số nguyên tố p  2 và các số nguyên 1  b  a  p 1 . Chứng minh rằng tồn tại các số i, j phân biệt thuộc tập hợp 1, 2,..., p 1 sao cho ai  bi  a j  b j (mod p) . Bài 5.5. Cho p là một số nguyên tố. Chứng minh 1 1 1 1 p 1     (mod p) . 1 1 1  2 2 2 1 32 1  ( p 1) 2 2 Bài 5.6. Cho n  1 là một số nguyên dương lẻ. Giả sử S là tập hợp các số nguyên dương x thỏa mãn x  n và gcd( x, n)  gcd( x 1, n)  1 . Chứng minh  x  1 (mod n) . x S Trang 17
II. Hướng dẫn giải các bài tập đề xuất 1. Lớp thặng dư và hệ thặng dư Bài 1.1. Cho p là một số nguyên tố lẻ. Chứng minh   p 1 (a) 0, 1, 2,...,   là một hệ thặng dư đầy đủ mod p .    2     2 2  p 12   (b) 1 , 2 ,...,      là một hệ gồm các thặng dư phân biệt mod p .     2       (c) 12 , 2 2 ,..., ( p 1) 2 , p 2  không là một hệ thặng dư đầy đủ mod p . Hướng dẫn giải   p 1  (a) Giả sử tồn tại x, y  0, 1, 2,...,   sao cho x  y (mod p) (1) .    2    p 1 p 1 Do   x, y  nên x  y  p 1  p , thành thử từ (1) ta phải có x  y , mâu thuẫn. 2 2 p 1 (b) Ta cần chứng minh với mọi 1  x  y  thì x 2  y 2 (mod p) .  2 p 1 Thật vậy, do 1  x  y  nên 0  x  y  x  y  p . 2 Khi đó x  y  0 (mod p) và x  y  0 (mod p) , kéo theo x 2  y 2 (mod p) .    p 1 (c) Do k 2  ( p  k )2 1  k  nên 12 , 2 2 ,..., ( p 1) 2 , p 2  không là hệ đầy đủ mod p . 2 Bài 1.2. [May Olympiad 2021] Theo quan niệm của nhiều người, Thứ Sáu ngày 13 được cho là ngày xui xẻo và thường đem lại tai họa bất ngờ cho họ. (a) Chứng minh rằng trong một năm dương lịch có ít nhất một ngày là Thứ Sáu ngày 13 . (b) Trong một năm có thể có bao nhiêu ngày là Thứ Sáu ngày 13 ? Hướng dẫn giải Ta có thể coi các ngày Chủ nhật, Thứ Hai, Thứ Ba, …, Thứ Bảy là các lớp thặng dư 0,1, 2,...,6 modulo 7 . Trường hợp 1: Năm dương lịch đang xét là năm thường (tức là năm có 365 ngày). Giả sử ngày 13 tháng 1 thuộc lớp thặng dư k . Khi đó ngày 13 của các tháng còn lại thuộc các lớp thặng dư được cho trong bảng sau Jan 13 : k Feb 13 : k  3 Mar 13 : k  3 Apr 13 : k  6 May 13 : k  1 Jun 13 : k  4 July 13 : k  6 Aug 13 : k  2 Sep 13 : k  5 Oct 13 : k Nov 13 : k  3 Dec 13 : k  6 Do k , k  1, k  2, k  3, k  4, k  5, k  6 là hệ thặng dư đầy đủ mod 7 nên tồn tại ngày 13 của một tháng nào đó rơi vào lớp thặng dư 6 mod 7 , nói cách khác ngày 13 của tháng đó là ngày Thứ Sáu. Từ bảng trên ta cũng thấy rằng trong một năm chỉ có thể có 1 , 2 hoặc 3 ngày 13 rơi vào Thứ Sáu. Trường hợp 2: Năm dương lịch đang xét là năm nhuận (tức là năm có 366 ngày). Trang 18
Lập luận tương tự ta thấy một năm nhuận chỉ có thể có 1 , 2 hoặc 3 ngày 13 rơi vào Thứ Sáu. Bài 1.3. Cho p là một số nguyên tố lẻ và a1 , a2 ,..., a p là các số nguyên. Chứng minh nếu ai i1 p là một hệ đầy đủ mod p thì (a) a1  a2  ...  a p  0 (mod p) . (b) a12  a2  ...  a 2  0 (mod p ) , với p  3 . 2 p Hướng dẫn giải (a) Do ai i1 là hệ thặng dư đầy đủ mod p nên p p ( p  1) a1  a2  ...  a p  1  2  ...  p   0 (mod p ) . 2 (b) Tương tự ta cũng có p ( p  1)(2 p  1) a12  a2  ...  a 2  12  22  ...  p 2  2 p  0 (mod p ) . 6 Lưu ý. Hãy giải thích kĩ vì sao trong bài toán trên, chứng minh (a) cần giả thiết p lẻ và chứng minh (b) cần giả thiết p  3 ? Bài 1.4. Tìm tất cả các số nguyên dương n sao cho số 36n  6 là tích của các số nguyên dương liên tiếp. Hướng dẫn giải Trước hết ta thấy 36n  6 không thể là tích của nhiều hơn ba số nguyên liên tiếp vì 36n  6  4  trong khi tích của bốn số nguyên liên tiếp luôn chia hết cho 4 (vì bốn số nguyên liên tiếp luôn tạo thành một hệ đầy đủ mod 4 ). Do đó ta chỉ có hai trường hợp dưới đây. Trường hợp 1: 36n  6  k (k 1) với k   . Ta có 4.62 n  23  (2k 1) 2  (2.6n  2k 1)(2.6n  2k 1)  23 . Khi đó 2.6n  2k 1  1 và 2.6n  2k  1  23 . Từ đó tìm được n  1 . Thử lại ta thấy n  1 thỏa mãn yêu cầu bài toán. Trường hợp 2: 36n  6  k (k 1)(k  2) . Ta có 36n  k (k 1)(k  2)  6 62 n  k 3  3k 2  2k  6  62 n  (k  3)(k 2  2) (1) . Ta chứng minh gcd(k  3, k 2  2)  1 . Thật vậy, giả sử k  3 và k 2  2 có ước nguyên tố chung là p , khi đó k  3 (mod p) nên 0  k 2  2  (3) 2  2  11 (mod p) , chứng tỏ p  11 . Tuy nhiên điều này mâu thuẫn với (1) vì 6 2 n không chia hết cho 11 . Vậy gcd(k  3, k 2  2)  1 . Do chỉ có duy nhất một cách phân tích 6 2 n thành tích của hai số lớn k  3  2 2 n  hơn 1 và nguyên tố cùng nhau là 62 n  22 n.32 n nên từ (1) ta suy ra  2  . k  2  32 n (2)   Trang 19
Nhưng lấy mod 4 hai vế của (2) ta lại thu được k 2  3 (mod 4) , vô lí. Bài 1.5. Cho x, y là các số nguyên và p là một số nguyên tố. Giả sử tồn tại các số nguyên dương m, n nguyên tố cùng nhau thỏa mãn mx  ny (mod p) . Chứng minh rằng tồn tại một số nguyên z sao cho x  nz (mod p ) và y  mz (mod p) . Hướng dẫn giải Do gcd(m, n)  1 nên một trong hai số m và n không chia hết cho p . Giả sử gcd(m, p)  1 . Khi đó tồn tại nghịch đảo m1 của m mod p . Từ giả thiết mx  ny (mod p) ta có x  m1ny  n(m1 y ) (mod p) (1) . Khi đó nếu đặt z  m1 y thì y  mz (mod p) . Hơn nữa từ (1) ta suy ra x  nz (mod p ) . Bài 1.6. [Putnam MC 2017] Giả sử S là tập con nhỏ nhất của  thỏa mãn các điều kiện (i) 2  S . (ii) Với mọi n   , nếu n 2  S thì n  S . (iii) Với mọi n   , nếu n  S thì (n  5) 2  S . (a) Chứng minh rằng 3, 4, 6  S . (b) Tìm tập hợp S . Hướng dẫn giải (a) Từ (ii) và (iii) ta suy ra “Với mọi n   , nếu n  S thì n  5  S ”. Bằng phép quy nạp ta nhận được (iv): Với mọi n   , nếu n  S thì n  5k  S với k   tùy ý. Do đó ta có ( iii ) ( iii ) 2  S  49  (2  5) 2  S  542  (49  5) 2  S ( iv ) ( ii ) ( iv )  562  542  5.44  S  56  S  121  56  5.13  S ( ii ) ( iv ) ( ii )  11  S  16  11  5  S  4  S Từ đây ta có ( iv ) ( ii ) 4  S  9  4  5.1  S  3  S ( iv ) ( ii ) 16  S  36  16  5.4  S  6  S . (b) Từ (iv) và kết quả câu (a) và (iv) ta suy ra tất cả các số có dạng 5k  1 (trừ 1 ), 5k  2 , 5k  3 và 5k  4 (với k   ) đều thuộc S (1) . Xét tập hợp S  : n  * : n  1, n  0 (mod 5) .  Do nhận xét (1) nên S   S (2) . Mặt khác dễ thấy tập hợp S  thỏa mãn tất cả các điều kiện (i), (ii) và (iii) nên theo tính nhỏ nhất của S ta suy ra S  S  (3) . Từ (2) và (3) ta suy ra Trang 20