zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Khoa Học Tự Nhiên

Cấp của một số nguyên và ứng dụng giải một số bài toán số học

Chia sẻ: AndromedaShun _AndromedaShun | Ngày: | Loại File: PDF | Số trang:9

Báo xấu

29
lượt xem 2
download

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

Bài viết "Cấp của một số nguyên và ứng dụng giải một số bài toán số học" trình bày một số định nghĩa, định lí, tính chất quan trọng về cấp của một số nguyên và ứng dụng vào giải một số bài toán số học. Mời các bạn cùng tham khảo!

Chủ đề:

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

Lưu

Nội dung Text: Cấp của một số nguyên và ứng dụng giải một số bài toán số học

Hội thảo khoa học, Hưng Yên 25-26/02/2017 CẤP CỦA MỘT SỐ NGUYÊN VÀ ỨNG DỤNG GIẢI MỘT SỐ BÀI TOÁN SỐ HỌC Đặng Thị Mến THPT Chuyên Hưng Yên 1 Cơ sở lý thuyết Định nghĩa 1. Số nguyên dương k bé nhất thỏa mãn ak ≡ 1 (mod n) được gọi là cấp của a theo mod n, ký hiệu ordn ( a) = k. Nhận xét 1. Cho n ∈ N∗ . Nếu a ∈ Z và ( a, n) > 1 thì không tồn tại số k ∈ N∗ để ak ≡ 1 (mod n), vì nếu ak ≡ 1 (mod n) thì ( ak , n) = (1, n) = 1, mà ( a, n) > 1 nên ( ak , n) > 1 (vô lý). Nếu a ∈ Z và ( a, n) = 1 thì luôn tồn tại số k ∈ N∗ để ak ≡ 1 (mod n), chẳng hạn k = ϕ ( n ). Từ định nghĩa trên ta có các kết quả sau • ordn ( a) = 1 ⇔ a ≡ 1 (mod n) • 1, a, a2 , . . . , aordn (a)−1 là đôi một phân biệt theo mod n. (Chúng lập thành các số đôi một phân biệt chia cho n có ordn ( a) số dư khác nhau) Định lý 1. a) Giả sử cấp của a theo mod n là k, khi đó ah ≡ 1 (mod n) ⇔ k |h. b) Nếu ordn ( a) = k; ordn (b) = h mà (h, k ) = 1 thì ordn ( ab) = hk. c) Cho các số n1 , n2 , . . . , nk đôi một nguyên tố cùng nhau và n = n1 n2 . . . nk và ordni ( a) = hi . Khi đó ordn ( a) = [h1 , h2 , . . . , hk ]. h d) Nếu ordn ( a) = h và u ∈ N∗ thì ordn ( au ) = . (h, u) . Chứng minh. a) Nếu h..k thì h = kq (q ∈ N∗ ) vì ordn ( a) = k ⇔ ak ≡ 1 (mod n) nên akq ≡ 1 (mod n). Nếu ah ≡ 1 (mod n) và h = kq + r với 1 ≤ r < k thì ah = ( ak )q ar ≡ ar (mod n) nên ar ≡ 1 (mod n) mà 1 ≤ r < k, mâu thuẫn với định nghĩa số k. . Vậy r = 0 hay h..k. b) ordn ( a) = k ⇔ ak ≡ 1 (mod n) nên ahk ≡ 1 (mod n) ordn (b) = h ⇔ bh ≡ 1 (mod n) nên bhk ≡ 1 (mod n) suy ra ( ab)hk ≡ 1 (mod n). . Gọi t = ordn ( ab) thì hk..t (1) Lại có ( ab)t ≡ 1 (mod n) nên ( ab)th ≡ 1 (mod n) và ath .(bh )t ≡ 1 (mod n). 184
Hội thảo khoa học, Hưng Yên 25-26/02/2017 . . Mặt khác (bh )t ≡ 1 (mod n) nên ath ≡ 1 (mod n) suy ra th..k do (h, k) = 1 nên t..k (*) . Tương tự có ( ab)tk ≡ 1 (mod n) nên btk ≡ 1 (mod n) do ( ak )t ≡ 1 (mod n) nên tk..h mà . (k, h) = 1 nên t..h (**). . Từ (*) và (**) suy ra t..hk (2) Từ (1) và (2) suy ra hk = t (đpcm). . c) Tương tự có h = ordn ( a) ⇔ ah ≡ 1 (mod n) nên ah ≡ 1 (mod n ) suy ra h..h , ∀i = 1, ..., k i i Suy ra h là một bội chung của hi , ∀i = 1, . . . , k. . Gọi k là một bội chung của hi thì ak ≡ 1 (mod ni ) nên ak ≡ 1 (mod n) suy ra k..h. Vậy h = [n1 , n2 , . . . , nk ]. d) Gọi k = ordn ( au ), d = (h, u) thì h = dx, u = dy với ( x, y) = 1, x, y ∈ N∗ . +) ( au )k = aku ≡ 1 (mod n) nên h|ku nên h|dky suy ra dky = m.h = mdx, m ∈ N∗ . Suy ra ky = mx hay x |ky mà ( x, y) = 1 nên x |k (1). +) aux = adxy = ( adx )y = ( ah )y ≡ 1 (mod n) nên ( au ) x ≡ 1 (mod n) do đó k| x. (2) h h Từ (1) và (2) suy ra k = x = = . d (h, u) Nhận xét 2. • Nếu n = p1α1 p2α2 . . . pαk k là phân tích tiêu chuẩn của n. Để tìm ordn ( a) thì ta tìm ord pαi ( a), i với i ∈ {1, . . . , k }. • a ϕ(n) ≡ 1 (mod n); ∀( a, n) = 1 nên ordn ( a)| ϕ(n) (rộng ra, ordn ( a) ≤ ϕ(n)), hay ordn ( a) ≤ ( n − 1). • Nếu p nguyên tố thì ord p ( a)| p − 1; ∀( a, p) = 1 • a x ≡ ay (mod n) ⇔ ordn ( a)|( x − y). • m|n thì ordm ( a)| ordn ( a), ordn ( a) = h nên ah ≡ 1 (mod n) . m|n thì ah ≡ 1 (mod m) nên h.. ordm ( a) Định nghĩa 2. Số nguyên g được gọi là căn nguyên thủy của n, nếu cấp của nó theo mod n bằng ϕ ( n ). Ví dụ 1. Hãy xác định ord101 (2) và ord125 (12). Lời giải. · Gọi d = ord101 (2), có 101 là số nguyên tố nên ϕ(101) = 100. 2d ≡ 1 (mod 101) suy ra d|100, ta chứng minh d 6= 50, d 6= 20. 210 = 1024 ≡ 14 (mod 101) nên 250 ≡ 145 ≡ 1962 .14 ≡ (−6)2 .14 ≡ −1 (mod 101) suy ra d 6= 50 220 = 10242 ≡ 142 ≡ −6 (mod 101) nên d6= 20 và d = 100 nên ord101 (2) = 100. 1 · Gọi d = ord125 (12); ϕ(125) = 53 . 1 − = 100 nên d|100 5 ord5 (12)|d, mà 12 ≡ 2 (mod 5), 122 ≡ 4 (mod 5) nên 123 ≡ 3 (mod 5); 124 ≡ 1 (mod 5) do đó ord5 (12) = 4 nên 4|d. Mà d|100 nên d ∈ {4; 20; 100}. 124 ≡ 1442 ≡ 192 ≡ 361 ≡ −14 (mod 125) 1220 = (124 )5 ≡ (−14)5 ≡ 71.71.(−14) ≡ 41.14 ≡ 74 (mod 125) suy ra d = 100, vậy ord125 (12) = 100. 185
Hội thảo khoa học, Hưng Yên 25-26/02/2017 Định lý 2. Cho a là số lẻ và n = 2s , ( a, n) = 1. ( 2 .c với u, v ∈ N ; b, c lẻ. Giả sử a − 1 = 2u .b; a2 − 1 = v ∗ 1, u ≥ s Khi đó h = ordn ( a) thì h = 2max{1;s+1;v} , u < s Chứng minh. Nhận xét rằng a2 − 1 = ( a − 1)( a + 1) = 2u .b( a + 1) = 2u .b.(2u .b + 2) = 2u+1 .b(2u−1 .b + 1) nên v > u s s (1− 1 ) s −1 · ( a, n) = 1 nên a ϕ(n) ≡ 1 (mod n) mà a ϕ(n) = a ϕ(2 ) = a2 2 = a2 suy ra h|2s−1 nên h = 2t với t ≤ s − 1 (1) . · Nếu u ≥ s thì a − 1 = 2u .b .. 2s nên n| a − 1 suy ra a ≡ 1 (mod n) nên h = 1. · Nếu u < s thì h ≥ 2 nên t ≥ 1 t t −1 t −2 ( ah − 1) = ( a2 − 1) = ( a2 + 1)( a2 + 1) . . . ( a2 + 1)( a2 − 1) (*) i a ≡ 1 (mod 2) (a lẻ) nên a2 ≡ 1 (mod 2) . Nếu v ≥ s thì a2 − 1 .. n nên a2 ≡ 1 (mod n) suy ra h = 2 Nếu v < s thì s ≥ 2. i i Vì a là số lẻ thì a2 ≡ 1 (mod 4) nên a2 ≡ 1 (mod 4) và a2 + 1 ≡ 2 (mod 4) (*) nên ah − 1 = 2t−1 .a.2v .c với a, c là số lẻ, nên . ah − 1..2s ⇔ t − 1 + v ≥ s ⇔ t ≥ s − v + 1 ≥ 2 s − v +1 . t nhỏ nhất (do h nhỏ nhất) nên t = s − v + 1 hay h = 2 1; u ≥ s  Vậy h = 2; u < s ≤ v  1+ s − v  2 ; u
Hội thảo khoa học, Hưng Yên 25-26/02/2017 Nếu k > 1 t t t t a ≡ 1 (mod p); ah − 1 = ( a p − 1)( a p .(k−1) + a p .(k−2) + · · · + a p + 1) ≡ k (mod p) t thì ah − 1 = ( a p − 1).b; b ≡ k (mod p) ⇒ (b, p) = 1. . . Mà ah − 1..p nên a p − 1..p và a p ≡ 1 (mod p). t t Suy ra pt |h nên pt < h, vô lý với cách chọn h, nên k = 1, do đó h = pt k; t > 0. Áp dụng bổ đề nâng lũy thừa, ta có p lẻ, p > 1 v p ( a h − 1) = v p ( a − 1) + v p ( h ) = u + t hay ah − 1 = pu+t .A; ( p, A) = 1 . Mà ah − 1..ps nên u + t ≥ s suy ra t ≥ s − u ≥ 1. Vậy t bé nhất là t = s − u nên h = ps−u . Trường hợp 2: r > 1 . ah ≡ 1 (mod n) nên ah ≡ 1 (mod p) suy ra h..n. Giả sử h = r.k; ah = ( ar )k = bk (với b = ar ) nên b − 1 = pu q; b ≡ 1 (mod p); (b, n) = 1. Có bk ≡ ah ≡ 1 (mod n), suy ra k là cấp của b theo mod n. Áp dụng trường hợp 1 cho b (r = 1) ta có ( ( 1; u≥s r; u≥s k= s − u ⇒ h = rk = s − u p ; u 1) 2 p − 1 ≡ 0 (mod q) nên 2 p ≡ 1 (mod q) suy ra ordq (2)| p. 187
Hội thảo khoa học, Hưng Yên 25-26/02/2017 ( ordq (2) = 1 Mà p nguyên tố nên (*) ordq (2) = p . Nếu ordq (2) = 1 thì 2 ≡ 1 (mod q) nên 1 .. q và q = 1, vô lý. Nếu ordq (2) = p thì ordq (2)| ϕ(q) nên p|q − 1 vậy nên q = kp + 1 (k ≥ 1). Bài toán 2. Nếu p là ước nguyên tố lẻ của n2 + 1 thì p ≡ 1 (mod 4); ∀n ∈ N∗ . Lời giải. Ta có p|n2 + 1 nên p|(n4 − 1) vậy nên ord p (n)|4. Nếu ord p (n) = 1 thì n ≡ 1 (mod p) nên p|n − 1. Suy ra p|n2 − 1 mà p|n2 + 1 nên p|2, vô lý vì p nguyên tố lẻ. Nếu ord p (n) = 2 thì n2 ≡ 1 (mod p) nên p|n2 − 1 mà p|n2 + 1 do đó p|2, vô lý. nên ord p (n) = 4 mà ord p (n)| ϕ( p) = p − 1 nên 4| p − 1 do đó p = 4k + 1 hay p ≡ 1 (mod 4). Bài toán 3. Chứng minh rằng a) Nếu p là ước nguyên tố lẻ của n4 + 1 thì p ≡ 1 (mod 8) n b) Nếu p là ước nguyên tố lẻ của a2 + 1 ( a ∈ Z, n ∈ N∗ ) thì p ≡ 1 (mod 2n ), hay p có dạng p = 2n+1 .k + 1, k ∈ N∗ . Lời giải. a) p là ước nguyên tố lẻ của n4 + 1 nên p|n4 + 1 suy ra p|n8 − 1 và ord p (n)|8 nên ord p (n) = 2t ; t ∈ N; t ≤ 3. Nếu(t < 3 thi t ≤ 2 nên 2t |22 = 4 do đó ord p (n)|4 nên n4 ≡ 1 (mod p). p | n4 − 1 Mà suy ra p|2 mâu thuẫn với p nguyên tố lẻ. p | n4 + 1 nên t = 3 suy ra ord p (n) = 8| ϕ( p) = p − 1 và p ≡ 1 (mod 8) hay p = 8k + 1 (k ∈ N∗ ). b) Chứng minh tương tự có ord p (n) = h ah ≡ 1 (mod p) n +1 n +1 p| a2n + 1 và p|( a2n + 1)( a2n − 1) = a2 − 1 do đó a2 ≡ 1 (mod p) nên h|2n+1 suy ra h = 2t (t ≤ n + 1). n Nếu(t ≤ n thì 2t |2n nên a2 ≡ 1 (mod p). n p | a2 − 1 Mà n nên p|2, mâu thuẫn với p nguyên tố lẻ nên t = n + 1. p | a2 + 1 nên h = 2n+1 | ϕ( p) = p − 1 do đó p ≡ 1 (mod 2n+1 ) hay p = 2n+1 .k + 1. n Nhận xét 4. Mọi ước lẻ của a2 + 1 đều có dạng 2n+1 .k + 1; k ∈ N. n Khi a = 2, số Fecma thứ n là Fn = 22 + 1 có tính chất: p là ước nguyên tố lẻ của Fn (n > 1) thì p ≡ 1 (mod 2n+2 ). Bài toán 4. Cho p nguyên tố, n ∈ N∗ và q là ước nguyên tố lẻ của n p + 1 thì q|n2 − 1 hoặc 2p|(q − 1). Lời giải. Giả sử q|n p + 1 thì n p ≡ −1 (mod q) nên n2p ≡ 1 (mod q) h = ordq (n) nên h|2p, mà h không là ước của p và p nguyên tố nên h = 2 hoặc h = 2p. Nếu h = 2 thì n2 ≡ 1 (mod q) nên q|n2 − 1 (đpcm). Nếu h = 2p thì h| ϕ(q) = q − 1 nên 2p|(q − 1) (đpcm). Bài toán 5. Chứng minh rằng: ∀n > 2 đều không là ước của 2n − 1. 188
Hội thảo khoa học, Hưng Yên 25-26/02/2017 Lời giải. Giả sử có n ≥ 2 và n|2n − 1 mà 2n − 1 là số lẻ, suy ra n lẻ. Gọi p là ước nguyên tố nhỏ nhất của n thì p lẻ, p ≥ 3. 2n − 1 ≡ 0 (mod p) ord p (2)|n và ord p (2)| p − 1 = ϕ( p). 1 < ord p (2)|( p − 1, n), vô lý vì p là ước nguyên tố nhỏ nhất của n. Suy ra ( p − 1, n) = 1. Vậy n không thể là ước của 2n − 1. Bài toán 6. Tìm các số nguyên dương a 6= b với a + b nhỏ nhất sao cho 2012a và 2012b có ba chữ số tận cùng giống nhau. Lời giải. Giả sử a > b. 2012a ≡ 2012b (mod 1000) ⇔ 12a ≡ 12b (mod 1000) nên 12b (12a−b − 1) ≡ 0 (mod 1000) Mà 1000 = 23 .53 , mà 12b là số chẵn, 12a−b − 1 là số lẻ nên 23 |12b do đó b ≥ 2. Mà (5; 12) = 1 nên 53 |(12a−b − 1) . Tìm ord 3 (12), theo ví dụ 1 ta có ord 3 (12) = 100 nên a − b .. 100 5 5 vậy a − b ≥ 100 mà b ≥ 2 nên 2b ≥ 4 suy ra a − b + 2b ≥ 104; a + b ≥ 104. Dấu "=" khi b = 2, a = 102. Mà a 6= b; a + b nhỏ nhất suy ra a = 102, b = 2. Kết luận: a = 102, b = 2 hoặc a = 2, b = 102. ( n | 2m −1 + 1 Bài toán 7. Tìm tất cả các số nguyên dương (m, n) thỏa mãn . m | 2n −1 + 1 ( n | 20 + 1 ⇒ n | 2 n=1 Lời giải. · Nếu m = 1 thì n − 1 nên m |2 +1 n=2 ( n | 2m −1 + 1 m=1 · Nếu n = 1 thì 0 nên m |2 + 1 m=2 ( n | 2m −1 + 1 · Nếu m > 1, n > 1 có suy ra m, n lẻ. m | 2n −1 + 1 Giả sử m − 1 = 2a .x ( a ∈ N∗ , x lẻ ) và n − 1 = 2b .y (b ∈ N∗ , y lẻ ) a Gọi p là ước nguyên tố bất kỳ của n thì p|2m−1 + 1 nên p|(2x )2 + 1 theo bài tập 3. nên p ≡ 1 (mod 2a+1 ) do đó p = α a+1 k + 1. Như vậy mọi ước của n đều có dạng 2a+1 k + 1. Do tích của các số có dạng 2a+1 k + 1 cũng là số có dạng 2a+1 k + 1 nên n ≡ 1 (mod 2a+1 ). n − 1 = 2a+1 .y1 (y1 ∈ N∗ ) mà n − 1 = 2b .y (y lẻ) nên b ≥ a + 1 (1) Gọi q là ước nguyên tố bất kỳ của m. b q|m thì a|2n−1 + 1 nên q|(2x )2 + 1 theo bài tập 3 nên q ≡ 1 (mod 2b+1 ) ⇒ q = 2b+1 .t + 1 nên m = 2b+1 .x1 + 1 ( x1 ∈ N∗ ) ⇒ m − 1 = 2b+1 .x1 ( x1 ∈ N∗ ), mà m − 1 = 2a .x (x lẻ) nên a ≥ b + 1 (2) Từ (1) và (2) vô lý. Vậy không có m > 1, n > 1 thỏa mãn đề bài. Kết luận: m = 1, n = 1; m = 1, n = 2; m = 2, n = 1. n Bài toán 8. Cho số Fecma Fn = 22 + 1 (có thể là hợp số, cũng có thể là số nguyên tố). a) Chứng minh rằng, nếu Fn là hợp số thì Fn có ít nhất 2 ước nguyên tố phân biệt. 189
Hội thảo khoa học, Hưng Yên 25-26/02/2017 b) Chứng minh rằng, nếu p| Fn , q| Fn (p, q là số nguyên tố, p 6= q) thì ( ( p | 2q −1 − 1 2q−1 ≡ 1 (mod p) hay q | 2 p −1 − 1 2 p−1 ≡ 1 (mod q) Lời giải. a) Giả sử Fn là hợp số và Fn có đúng một ước nguyên tố phân biệt. nên Fn = pk (k ≥ 2) vì nếu k = 1 thì Fn = p là số nguyên tố, vô lý. Nếu k chẵn: k = 2t (t ≥ 1). n n n −1 n −1 Fn = pk thì 22 + 1 = p2t ⇔ 1 = p2t − 22 = ( pt − 22 )( pt + 22 ), vô lý (vì n ≥ 5, Fn mới là hợp số). Nếu k lẻ: k = 2t + 1 (t ≥ 1) n n 22 + 1 = p2t+1 nên 22 = p2t+1 − 1 = ( p − 1)( p2t + p2t−1 + · · · + p + 1) n suy ra 22 có ước lẻ lớn hơn 1, vô lý. Vậy Fn là hợp số thì phải có 2 ước nguyên tố phân biệt trở lên. b) Gọi p, q là hai ước nguyên tố phân biệt của Fn thì p, q lẻ vì Fn lẻ. Ta chứng minh: ord p (2)|q − 1 và ordq (2)| p − 1. n Giả sử ord p (2) = h thì 2h ≡ 1 (mod p), có p| Fn nên 22 ≡ −1 (mod p) n +1 ⇒ 22 ≡ 1 (mod p) nên h|2n+1 suy ra h = 2t với t ≤ n + 1. n n n Nếu t ≤ n thì 2t |2n thì 22 ≡ 1 (mod p); p|22 − 1; p|22 + 1 nên p|2 mâu thuẫn p nguyên tố lẻ. nên t = n + 1 hay h = 2n+1 , chứng minh tương tự có ordq (2) = 2n+1 . Mà ord p (2)| ϕ( p) = p − 1 nên 2n+1 | p − 1; 2n+1 = ordq (2) do đó 2 p−1 ≡ 1 (mod q). Mà ordq (2)| ϕ(q) = q − 1 nên 2n+1 |q − 1 mà 2n+1 = ord p (2) suy ra 2q−1 ≡ 1 (mod p) (đpcm). Bài toán 9. Cho n > 1, a ∈ N∗ ; n| an + 1. Chứng minh rằng ( a + 1, n) = 1. Lời giải. Do n > 1 nên n có ước nguyên tố. Gọi p là ước nguyên tố nhỏ nhất của n nên ( p − 1, n) = 1. . ord p ( a) = h nên ah ≡ 1 (mod p) suy ra ah − 1 .. p p|n mà n| an + 1 nên p| an + 1 an ≡ −1 (mod p) do đó p| a2n − 1 nên a2n ≡ 1 (mod p) suy ra h|2n. Mà h| ϕ( p) = p − 1 nên h|(2n, p − 1); (2n, p − 1) = (2, p − 1) suy ra h|(2, p − 1). Do (n, p − 1) = 1 nên h|(2, p − 1); (2, p) = 2 . Nếu h = 1 thì a − 1 .. p nên an ≡ 1 (mod p) nên an + 1 ≡ 2 (mod p). . . . Mà an + 1 .. p thì 2 .. p mà p nguyên tố nên p = 2, có ( a − 1) .. 2 nên a lẻ, p| a nên ( a + 1; n) ≥ 2 > 1. . Nếu h = 2 thì a2 − 1 .. p; 2|( p − 1) nên p lẻ mà a − 1 không chia hết cho p nên p| a + 1; p|n suy ra p|( a + 1, n) do đó ( a + 1, n) > 1 (đpcm) Bài toán 10. Giả sử a, b là các số nguyên dương, sao cho 2a − 1; 2b − 1; 2c − 1 đều là các số nguyên tố. Chứng minh rằng a a + bb và ab + b a đều không chia hết cho a + b. Lời giải. Có 2a − 1; 2b − 1 là số nguyên tố nên a > 1, b > 1 và a + b > 2 mà a + b nguyên tố, do đó a + b là số lẻ, ϕ( a + b) = a + b − 1. 190
Hội thảo khoa học, Hưng Yên 25-26/02/2017 . Giả sử a chẵn, b lẻ. Vì b lẻ nên ab + bb ..( a + b) (1) . · Nếu a a + bb ..( a + b) (2) . . Từ (1), (2) suy ra ( ab − a a )..( a + b) và a a ( ab−a − 1)..( a + b), nếu a < b (*) . hoặc ab (1 − a a−b )..( a + b) nếu a > b. . . Nếu a a ..( a + b) thì a..( a + b) do ( a + b) nguyên tố, vô lý vì a < a + b. . . Nếu ab ..( a + b) thì a..( a + b) do ( a + b) nguyên tố, vô lý vì a < a + b. Từ (*) có a|b−a| ≡ 1 (mod ( a + b)). Gọi( h = orda+b ( a) thì h|(|b − a|) h|2a − 1 Mà h| ϕ( a + b) nên h| a + b − 1 suy ra h|2b − 1 . Do (2a − 1), (2b − 1) là số nguyên tố nên h = 1 do đó a ≡ 1 (mod ( a + b)) nên ( a − 1)..( a + b), vô lý vì 0 < a − 1 < a + b. . . . · Tương tự, nếu ab + b a ..( a + b) mà ( ab + bb )..( a + b) nên (b a − bb )..( a + b) . . b a (1 − bb−a )..( a + b) nếu a < b hoặc bb (b a−b − 1)..( a + b) nếu a > b (**) . . Nếu b a ..( a + b) thì b..( a + b) do ( a + b) nguyên tố, vô lý vì b < a + b . . Nếu bb ..( a + b) thì b..( a + b) do ( a + b) nguyên tố, vô lý vì b < a + b . Từ (**) có (b|a−b| − 1)..( a + b) nên b|a−b| ≡ 1 (mod ( a + b)) Gọi k = orda+b (b) thì k|(| a − b|)(. k |2a − 1 Mà k | a + b − 1 = ϕ( a + b) nên k |2b − 1 Do 2a − 1; 2b − 1 là số nguyên tố nên k = 1 do đó b ≡ 1 (mod ( a + b)) . suy ra b − 1..( a + b), vô lý vì 0 < b − 1 < a + b. Vậy a a + bb ; ab + b a đều không chia hết cho 2a − 1; 2b − 1. Bài toán 11. Cho p, q là hai số nguyên tố lẻ thỏa mãn p = 2q + 1. Chứng minh − a2 luôn là căn nguyên thủy mod p với mọi số nguyên a thỏa mãn 1 < a ≤ q. Lời giải. Giả sử q = 2k + 1, suy ra p = 4k + 3 nên −1 không là số chính phương mod p. Gọi g là một căn nguyên thủy mod p, khi đó tồn tại các số nguyên dương s, t thỏa mãn 1 ≤ s, t ≤ p − 1 sao cho −1 ≡ gs (mod p), a ≡ gt (mod p). Do −1 không là số chính phương mod p nên s lẻ, suy ra (s + 2t)q là số lẻ và không chia hết cho p − 1. Ta có: (− a2 )q ≡ ( gs .g2t )q ≡ g(s+2t)q 6= 1 (mod p) (1) Mặt khác, vì 1 < a ≤ q nên a2 6= 1 (mod p) Do đó (− a2 )2 ≡ a4 6= 1 (mod p) (2) Gọi ord p (− a2 ) = h thì h| p − 1 nên h chỉ có thể nhận giá trị 2, q, 2q. Từ (1) và (2) suy ra h = 2q = p − 1. Vậy − a2 là căn nguyên thủy mod p. 191
Hội thảo khoa học, Hưng Yên 25-26/02/2017 3 Một số bài tập tương tự . Bài 1. Cho số nguyên dương n thỏa mãn 3n − 1..n. Chứng minh rằng n chẵn. Bài 2. Tìm số nguyên dương n nhỏ nhất sao cho 17n − 1 chia hết cho 22011 . Bài 3. a) Có bao nhiêu số nguyên dương n là bội số của 1001 và biểu diễn được dưới dạng n = 10 j − 10i (i, j ∈ N, 0 ≤ i < j ≤ 99). b) Có bao nhiêu số nguyên dương n là bội số của 2011 và biểu diễn được dưới dạng n = 10 j − 10i (i, j ∈ N, 0 ≤ i < j ≤ 99). Bài 4. Chứng minh rằng với mỗi số nguyên dương n thì 3n − 2n không chia hết cho n. Bài 5 (Bulgari OM 1995). Tìm tất cả các số nguyên tố p, q sao cho (5 p − 2 p )(5q − 2q ) chia hết cho pq. Đáp số: ( p; q) ∈ {(3; 3); (3; 13); (13; 3)}. n n Bài 6. Cho hai số nguyên dương m và n (n > 1), sao cho 1 + m3 + m2.3 chia hết cho n. Chứng minh rằng n = 3. Bài 7. Tìm tất cả các số nguyên tố p, q phân biệt sao cho 3 pq ≡ a (mod 3pq), với mọi số nguyên dương a. Đáp số: ( p; q) ∈ {(17; 11); (11; 17)}. Bài 8 (Russia OM 2000). Có tồn tại hay không các số nguyên dương a, b, c thỏa mãn    ( a, b) = (b, c) = (c, a) = 1 2a + 1 ... b    .    2b + 1 .. c 2c + 1 ... a   ( a + 1) n − a n Bài 9 (China TST 2006). Tìm tất cả các cặp số nguyên dương ( a, n) sao cho ∈ Z. n Bài 10 (Turkey TST 2013). Tìm tất cả các cặp số nguyên dương (m, n) thỏa mãn 2n + (n − ϕ(n) − 1)! = nm + 1. Tài liệu [1] Nguyễn Vũ Thanh, Số học, NXB Tổng hợp Tiền Giang - 1992. [2] Đặng Hùng Thắng, Nguyễn Văn Ngọc, Vũ Kim Thủy, Bài giảng số học, NXBGD - 1997. [3] Hà Huy Khoái, Số học, NXBGD - 2004. [4] Bộ Giáo dục và đào tạo, Tạp chí Toán học và tuổi trẻ, NXBGD 192

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.