Bài 3: 
. hmmmm em nghĩ đến $d=p_{1}^{b_{1}}.p_{2}^{b_{2}}...p_{k}^{b_{k}}$
với $0\leq b_{i}\leq a_{i}$ cho nên là kiểu gì $\varphi(d)=\varphi(?).\varphi(?)....$
sau một hồi liệt kệ đầy đủ các ước thì sẽ nhóm thành nhân tử như vậy 
*** chứng minh hàm phi Euler là hàm nhân tính:
ta sẽ chứng minh: $\varphi(mn)=\varphi(m).\varphi(n)$ với $(m,n)=1$
+) để ý $\varphi(mn)$ là số các số không vượt quá $mn$ và nguyên tố cùng nhau với $mn$
Ta viết các số nguyên dương không vượt quá $mn$ thành các hàng (từ trái sang phải) và cột (từ trên xuống) sau:
Screenshot (737).png 13.96K
0 Số lần tải
$\star $: Gọi $r$ là $1$ số nguyên dương không vượt quá $m$ sao cho $(m,r)=d>1$
Khi đó: không có số nào trong cột thứ $r(1\leq r \leq m)$ nguyên tố cùng nhau với $m$ thì cũng sẽ không nguyên tố cùng nhau với $mn$
Vì: một phần tử của cột $r$ đó đều có dạng $km+r(0<k<n)$. Do đó: theo thuật toán Euclid thì $(km+r,m)=(r,m)=d>1$
$\star$: Như vậy để tìm các số trong bảng mà nguyên tố cùng nhau với $m$ thì ta xét các cột $r$ sao cho $(m,r)=1$. Khi này có $\varphi(m)$ cột như vậy.
$\star$: tiếp theo ta đếm xem trong mỗi cột như vậy có bao nhiêu số nguyên tố cùng nhau với $m$
để ý: mỗi cột như vậy gồm các số $r,m+r,2m+r,...,(n-1)m+r$
và ta thấy $\{0;1;2;...;n-1\}$ là hệ thặng dư đầy đủ modulo $n$
mà $(m,n)=1$ nên $\{0.m+r;1.m+r;2m+r;...;(n-1)m+r\}$ cũng là 1 hệ thặng dư đầy đủ theo modulo $n$
tương ứng có $1$ hệ thặng dư thu gọn theo modulo $n$
do đó mỗi cột như vậy có $\varphi(n)$ số nguyên tố cùng nhau với $n$
lai do $(m,r)=1$ nên $\varphi(n)$ số ấy trong cột đó cũng nguyên tố cùng nhau với $m$
khi đó theo bổ đề này: $(a,b)=1$ và $(a,c)=1$ thì $(a,bc)=1$
ta có: $\varphi(n)$ số này cũng nguyên tố cùng nhau với $mn$
và có $\varphi(m)$ cột như vậy
SUY RA: $\varphi(mn)=\varphi(m).\varphi(n)$
Bài viết đã được chỉnh sửa nội dung bởi Hahahahahahahaha: 23-12-2024 - 19:54