I
idid231
[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!
ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.
Mình có mấy ví dụ sau
2^2013 mod 31
6^2013 mod 31
5^^2013 mod 31
11^2013 mod 31
Cách giải chung là đưa về x^phi(31) = x^30 mod 31 sẽ bằng 1. Từ đó ta hạ bậc của số mũ xuống.
Tuy nhiên trong trường hợp số mũ nhỏ hơn phi(31) = 30 thì mình chỉ có cách tính tay, k có cách nào nhanh hơn:
vd
2^22 mod 31 =?
2^2 mod 31 = 4
2^4 mod 31 = 16
...
Do cơ số 2 ta thấy nhanh đc 2^5 = 32 mod 31 = 1 nên số mũ 22 lại đc rút ngắn xuống còn 2.
Tuy nhiên vs những cơ số như ở ví dụ mình đưa: 6,5,11 thì việc đoán đc số mũ nào mod 31 = 1 sẽ rất khó khăn (11 phải mũ 15 mới = 30 = -1 mod 31)
Vậy có cách nào giúp ta tìm được một số nhỏ hơn phi và tính chất giống phi không? (như 5 trong 2^5 mod 31, 6 trong 6^6 mod 31, 3 trong 5^3 mod 31, 15 trong 11^15 mod 31)
2^2013 mod 31
6^2013 mod 31
5^^2013 mod 31
11^2013 mod 31
Cách giải chung là đưa về x^phi(31) = x^30 mod 31 sẽ bằng 1. Từ đó ta hạ bậc của số mũ xuống.
Tuy nhiên trong trường hợp số mũ nhỏ hơn phi(31) = 30 thì mình chỉ có cách tính tay, k có cách nào nhanh hơn:
vd
2^22 mod 31 =?
2^2 mod 31 = 4
2^4 mod 31 = 16
...
Do cơ số 2 ta thấy nhanh đc 2^5 = 32 mod 31 = 1 nên số mũ 22 lại đc rút ngắn xuống còn 2.
Tuy nhiên vs những cơ số như ở ví dụ mình đưa: 6,5,11 thì việc đoán đc số mũ nào mod 31 = 1 sẽ rất khó khăn (11 phải mũ 15 mới = 30 = -1 mod 31)
Vậy có cách nào giúp ta tìm được một số nhỏ hơn phi và tính chất giống phi không? (như 5 trong 2^5 mod 31, 6 trong 6^6 mod 31, 3 trong 5^3 mod 31, 15 trong 11^15 mod 31)