tailieunhanh - 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! | 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 gt 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 gt 1 nên ak n gt 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 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 lt k thì ah ak q ar ar mod n nên ar 1 mod n mà 1 r lt k mâu thuẫn với định nghĩa số k. . Vậy r 0 hay . 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ì 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 do h k 1 nên . Tương tự có ab tk 1 mod n nên btk 1 mod n do ak t 1 mod n nên mà . k h 1 nên . . Từ và suy ra 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 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 . 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 mdx m N . Suy ra ky mx hay x ky mà x y 1 nên x k 1