solution

Lũy thừa với số mũ khổng lồ — định lý Euler tổng quát

Khi số mũ $b$ cực lớn và $a,n$ không cần nguyên tố cùng nhau, ta dùng định lý Euler tổng quát (generalized Euler / lifting):

$a^{b} \equiv a^{\,b \bmod \varphi(n) \,+\, \varphi(n)} \pmod n \quad\text{khi } b \ge \varphi(n)$

Cho $a$, $b$, $n$. In $a^{b}\bmod n$ áp dụng quy tắc trên (kết quả vẫn đúng kể cả $b$ rất lớn).

Ví dụ

$a=2$, $b=100$, $n=12$: $\varphi(12)=4$, $100\ge4$ nên dùng $e=100\bmod4+4=4$, $2^4=16\equiv4\pmod{12}$.