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

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!
Nội dung trích xuất từ tài liệu:
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), ...