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
Hàm Phi Euler và áp dụng
- 27/11/2024
- 679 lượt xem
| Định nghĩa: Cho $n$ là một số nguyên dương, ký hiệu $\varphi(n)$ là số các số nguyên dương $a$ không vượt quá $n$ sao cho $a$ và $n$ nguyên tố cùng nhau, nghĩa là $\text{GCD}(a,n)=1$. |
Ví dụ: $\varphi(10)=4$ vì số 10 có 4 số nguyên dương không vượt quá 10 và nguyên tố cùng nhau với 10, đó là 1, 3, 7, 9.
| Công thức: $$\varphi(n)=\displaystyle n. \prod_{p|n, p\ \text{nguyên tố}}\left(1-\dfrac{1}{p}\right)$$ |
Ví dụ: Tính $\varphi(100)$ 
: $100$ có hai ước nguyên tố là $2$ và $5$.
Vậy $\varphi (100)=100.\left(1-\dfrac12\right)\left(1-\dfrac15\right)=40$.
| Áp dụng 1:Định lý Euler(tổng quát hóa của định lý Fermat nhỏ). Cho $a$ và $n$ là hai số nguyên dương nguyên tố cùng nhau. Khi đó: $$a^{\varphi (n)}\equiv 1 \ \text{mod}\ n. $$ |
| Ví dụ: Tìm hai chữ số tận cùng của số $19^{2013}\qquad $ (kỳ thi HSG MTCT THCS TP HCM năm 2013). |
Ta có: $19^{2013}=\left(19^{40}\right)^{50}.19^{13}$
Vì 
nên theo định lý Fermat nhỏ ta có: $19^{\varphi(100)} \equiv 1 \ \text{mod}\ 100 $. Suy ra $\left(19^{40}\right)^{50} \equiv 1 \ \text{mod}\ 100 $.
nên $19^{13}\equiv 59 \ \text{mod}\ 100$.
Tóm lại 2 chữ số tận cùng của số $19^{2013}$ là $59$.
| Áp dụng 2: Đếm số các phân số tối giản trên một khoảng rộng, mẫu số cho trước. |
Ví dụ: Có bao nhiêu phân số tối giản trên khoảng $(1;210)$ sao cho mẫu số là $210$.
Bài này rất khó nếu không nắm bắt thuật toán.
$$1<\dfrac{a}{210}<210 ⇔ 210<a<210^2\quad (*)$$
Thuật toán:
| 1. Đếm số các số nguyên thoả điều kiện (*), gọi số này là $A$.
2. Tính tỉ lệ $\dfrac{\varphi(n)}{n}$ các số nguyên $a$ thoả mãn $\text{GCD}(a,n)=1$, gọi tỉ số này là $B$. Ý nghĩa của tỉ lệ này là: trong $n$ số nguyên trên một khoảng thì có $\varphi(n)$ số nguyên nguyên tố cùng nhau với $a$. Vậy trên một khoảng có bao nhiêu số nguyên thì nhân số đó với tỉ lệ ta sẽ được số các số nguyên nguyên tố cùng nhau với $a$. 3. Thực hiện phép tính lấy phần nguyên của $A.B$. |
Thực hiện: $A=210^2-210-1=$ 
.
$\dfrac{\varphi(210)}{210}=\dfrac{48}{210}$ (bạn đọc tự tính $\varphi(210)=48$) 
.
Vậy số các phân số tối giản trên khoảng $(1;210)$ mà mẫu số $210$ là 
.
| Lưu ý: Điều đặc biệt của “luỹ thừa 2025”. |
| Bài toán: Tìm 3 chữ số cuối cùng của số $2024^{2025}$. |
Ta có: $\varphi(1000)=400$ nên $2024^{2025}=\left(2024^{400}\right)^5.\left(2024^{5}\right)^2$.
$2024^{\varphi(1000)} \equiv 1\ \text{mod}\ 1000 ⇔ 2024^{400} \equiv 1\ \text{mod}\ 1000$
Vậy $\left(2024^{400}\right)^5 \equiv 1\ \text{mod}\ 1000$.
Đặt phép tính: 
Nhận OK 2 lần kết quả giống nhau là 
.
Vậy 3 chữ số tận cùng của số $2024^{2025}$ là $624$.
Nhắc lại cách làm khác không dùng định lý Fermat nhỏ.
$2024^{2025} \equiv 24^{2025} \ \text{mod}\ 100 $ ; $24^{2025}=24^{3^4.5^2}$.
Đặt phép tính: 
nhấn OK 4 lần ra kết quả: 
.
Điều chỉnh phép tính rồi nhấn OK 2 lần: 
Đáp số: $624$.
| Với hai cách làm biệt lập như vậy, “luỹ thừa 2025” là một luỹ thừa đặc biệt. |
Luyện tập 1:  |
Ta có: 
$\varphi(2019)=$ 
$23^{2020}=23^{1344+676}$, $676=$ 
Vậy $23^{2020}=23^{1344}.23^{2^2}.23^{2^5}.23^{2^7}.23^{2^9}$ trong đó $23^{1344}=23^{\varphi(2019)} \equiv 1 \ \text{mod}\ 2019 $ nên:
$$23^{2020}\equiv 23^{2^2}.23^{2^5}.23^{2^7}.23^{2^9}\ \text{mod}\ 2019 $$
Luyện tập 2:  |
About TS. Nguyễn Thái Sơn
