Tìm dư của phép chia một số cực lớn cho một số nguyên tố

Nếu ta lấy tổng thì kết quả quá lớn, máy tính không thể ghi kết quả này vào bộ nhớ của nó được.

Ta sẽ lấy tổng ít số hạng hơn và tìm dư của tổng này khi chia nó cho $19$
 

Sau đó xét các số hạng còn lại của tổng: $16^{17}, 17^{18}, 18^{19}, 19^{20}, 20^{21}$.

$19$ là số nguyên tố nên $\varphi(19)=18$. theo định lý Euler nếu $a$ và $m$ nguyên tố cùng nhau thì $$a^{\varphi(m)} \equiv 1 \ (\text{mod}\ m).$$

Vì vậy $17^{18} \equiv 1\ (\text{mod}\ 19)$ và $18^{19}=18\times 18^{18} \equiv 18 \ (\text{mod}\ 19 )$. Ngoài ra $19^{20} \equiv 0 \ (\text{mod}\ 19)$, $20^{21} \equiv 1 \ (\text{mod}\ 19 )$ vì $20 \equiv 1\ (\text{mod}\ 19 )$.
 

$16^{17}=(4^{17})^2$ . Vậy $16^{17} \equiv 6 \ (\text{mod}\ 19)$.
 

Tóm lại $S\equiv \underbrace{2+6+1+18+0+1}_{=28 \equiv 9 \ (\text{mod}\ 19) } \ (\text{mod}\ 19 )$. Do đó $S \equiv 9\ (\text{mod}\ 19)$.

About TS. Nguyễn Thái Sơn

Nguyên trưởng Khoa Toán-Tin học ĐHSP TP HCM (1999-2009). Nguyên Giám đốc- Tổng biên tập NXB ĐHSP TP HCM (2009-2011). Nguyên Tổng thư ký Hội Toán học TP HCM (2008-2013).