Đến nội dung

c0ngtushark

c0ngtushark

Đăng ký: 11-11-2013
Offline Đăng nhập: 15-11-2013 - 22:21
-----

#463721 Hàm nhân tính

Gửi bởi c0ngtushark trong 11-11-2013 - 21:41

Chứng minh rằng hàm  ϕ(n) là hàm nhân tính

 

Hàm số học f được gọi là nhân tính nếu với mọi cặp số nguyên m, n mà (m, n) nguyên tố cùng nhau thì f(mn) = f(m)f(n).

 

ϕ(n)  là số các số nguyên dương < n và nguyên tố cùng nhau với n. 




#463654 Định lý Fermat nhỏ-Định lý Euler

Gửi bởi c0ngtushark trong 11-11-2013 - 19:56

:luoi:  Thực ra bài này mà nói ý tưởng thì ra hết mình làm luôn cho bạn

Xét định lý $Euler$ với $gcd(a,m)=1$ ta sẽ chứng minh $a^{\phi (m)}\equiv 1(modm)$

Xét hệ thặng dư thu gọn $module$ của $m$ là $A={a_{1},a_{2},...........a_{\phi (m)}}$ 

Hiển nhiên do $gcd(a,m)=1$ nên hệ $B={aa_{1},.....aa_{\phi (m)}}$ cũng là một hệ thặng dư thu gọn $mod m$

Do đó nhân hai vế ta có đpcm

Với định lý $Fermat$ vì $m$ nguyên tố nên $\phi (m)=m-1$ ta có đpcm

Ở cái câu "Do đó nhân hai vế ta có đpcm" mình không hiểu lắm bạn nói rõ được không :(