bài này dùng toán ko mệt mỏi lắm 
đầu tiên rút gọn a^b \equiv \alpha^b\mod n với \alpha = a \mod n
kế đến muốn áp dụng định lý Euler a^{\phi(n)} \equiv 1 \mod n cũng chưa được vì ở đây \alpha và n ko bảo đảm là số nguyên tố cùng nhau. Phải tách \alpha ra thành \alpha = 7^x * 191^y * \delta trong đó \delta và n nguyên tố cùng nhau. Tách ra vậy rồi thì ta có
\begin{aligned}
\alpha^b &\equiv (7^x * 191^y * \delta)^b \mod n \\
&\equiv (7^{xb} \mod n) * (191^{yb} \mod n) * (\delta^b \mod n) \mod n \\
&= p_1 * p_2 * p_3 \mod n
\end{aligned}
để tính p_1 = 7^{xb} \mod n thì nếu x = 0 hay \alpha ko chia hết cho 7 thì p_1 = 1, còn x > 0 thì vì n chia hết cho 7 nên 7^k \mod n sẽ có chu kì :V, ở đây là chu kì có độ dài = 10:
7^0 mod 1337 = 1
7^1 mod 1337 = 7
7^2 mod 1337 = 49
7^3 mod 1337 = 343
7^4 mod 1337 = 1064
7^5 mod 1337 = 763
7^6 mod 1337 = 1330
7^7 mod 1337 = 1288
7^8 mod 1337 = 994
7^9 mod 1337 = 273
7^10 mod 1337 = 574
7^11 mod 1337 = 7 <-- lập lại 7^1 mod 1337
vậy có thể tính 7^{xb} \equiv 7^{xb \mod 10} \mod n, là 1 trong 10 số 7, 49, 343, …, 574 trên. Tính xb \mod 10 thì ở đây khá dễ, chỉ cần lấy phần tử cuối cùng trong mảng b là xong, vì xb \equiv x(b \mod 10) \mod 10.
để tính p_2 = 191^{yb} \mod n thì cũng tương tự như trên, y = 0 thì p_2 = 1, y > 0 thì vì n chia hết cho 191 nên 191^k \mod n sẽ có chu kì, ở đây là chu kì có độ dài = 3:
191^0 mod 1337 = 1
191^1 mod 1337 = 191
191^2 mod 1337 = 382
191^3 mod 1337 = 764
191^4 mod 1337 = 191 <-- lập lại 191^1 mod 1337
vậy có thể tính 191^{yb} \equiv 191^{yb \mod 3} \mod n, là 1 trong 3 số 191, 382, 764. Tính yb \equiv y(b \mod 3) \mod 3 thì ở đây cũng tương đối dễ :V, vì 10^i \equiv 1 \mod 3 nên chỉ cần lấy tổng các phần tử trong mảng b là rồi % 3 là được.
để tính p_3 = \delta^b \mod n thì áp dụng định lý Euler là được :V \delta^b \equiv \delta^{b \mod \phi(n)}\mod n với \phi(n) = \phi(1337) = \phi(7*191) = (7-1)(191-1) = 1140.
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?