BITEXEDU Chuyên trang chia sẻ tài liệu, kinh nghiệm ứng dụng giải toán trên máy tính cầm tay
Tìm dư của phép chia bằng định lý Euler
- 27/01/2026
- 173 lượt xem
| Định lý. Nếu $a$ và $m$ nguyên tố cùng nhau (nghĩa là $\text{GCD}(a,m)=1$) thì $$a^{\varphi(m)} \equiv 1 \ (\text{mod}\ m).$$ |
$\varphi$ gọi là “hàm phi Euler”. $\varphi(m)$ được xác định như sau:
$$\left\lbrace\begin{array}{ll}\varphi (m)=m-1 &\text{nếu}\ m \ \text{là số nguyên tố} \\
\varphi(m)=m\left[\dfrac{a_1-1}{a_1}\cdot \dfrac{a_2-1}{a_2}\cdots \dfrac{a_k-1}{a_k}\right] & \text{nếu $a=a_1^{n_1}\cdot a_2^{n_2}\cdot \cdots \cdot a_k^{n_k}$} \cdot\end{array} \right. $$
các $a_k$ là thừa số nguyên tố của $m$ khi phân tích $m$ ra thừa số nguyên tố.
Ví dụ: $28=2^2\times 7$ nên $\varphi(28)=28\left[\dfrac{1}{2}\times \dfrac{6}{7}\right]=12$.
Bài tập áp dụng:
 |
Vì $28$ là chu kỳ của số thập phân tuần hoàn $\dfrac{325348721}{29}$ nên ta sẽ tìm dư của phép chia số $2025^{20252027}$ cho $28$.
Vì 
nên ta chỉ cần tìm dư của phép chia $9^{20252027}$ cho $28$.
$\text{GCD}(9,28)=1 $ nên $9^{\varphi(28)} \equiv 1 \ (\text{mod}\ 28)$.
hay $9^{12}\equiv 1 \ (\text{mod}\ 28)$.
$9^{20252027} =\underbrace{(9^{12})^{1687668}}_{\equiv 1\ \text{mod}\ 28}.9^{11}$ 
$\equiv 9^{11}\ (\text{mod}\ 28)$. 
.
Vậy $2025^{20252027} \equiv 25\ (\text{mod}\ 28)$ nên chữ số thập phân thứ $2025^{20252027}$ của số thập phân tuần hoàn chính là chữ số thứ 25 của phần tuần hoàn, cũng là chữ số 4 đêm từ tay phải của phần tuần hoàn $(931034482758620689655172$$4$$137)$. Đó là số $\fbox{$4$}$.
| Nếu $a$ là một số tự nhiên có từ $11$ đến $20$ chữ số thì công thức sau tìm dư của phép chia $a$ cho $b$: $$\fbox{$\rm a-b \text{Int}\dfrac{a}{b}$} $$ |
About TS. Nguyễn Thái Sơn
