Phi Hàm Euler - The Numbers Of 2H

Trước tiên, ta có được định lý sau.

Định lý. Với $\gcd\left( m,\,m’\right)=1$, và để $x$ chạy khắp một hệ thặng dư đầy đủ mod $m$, và $x’$ chạy khắp hệ thặng dư đầy đủ mod $m’$. Lúc đó $mx’+xm’$ chạy khắp hệ thặng dư đầy đủ mod $mm’$.

Chứng minh. Xét $mm’$ số $mx’+xm’$. Nếu \[mx’+m’x\equiv my’+m’y\pmod{mm’},\] lúc đó \[mx’\equiv my’\pmod{m’},\] \[m’x\equiv m’y\pmod m.\]Từ $\gcd\left( m,\,m’\right)$ ta có \[x’\equiv y’\pmod{m’},\] \[x\equiv y\pmod m.\] Định lý được chứng minh.

$\square$

Định lý. Với $\gcd\left( m,\,m’\right)=1$, và để $x$ chạy khắp một hệ thặng dư thu gọn mod $m$, và $x’$ chạy khắp hệ thặng dư thu gọn mod $m’$. Lúc đó $mx’+xm’$ chạy khắp hệ thặng dư thu gọn mod $mm’$.

Chứng minh. Đầu tiên ta chứng minh rằng $mx’+m’x$ nguyên tố cùng nhau với $mm’$. Giả sử điều ngược lại đó là tồn tại $p$ là số nguyên tố sao cho $p\mid\gcd\left( mm’,\,mx’+m’x\right)$. Nếu $p\mid m$, lúc đó $p\mid m’x$. Từ $\gcd\left( m,\,m’\right)=1$ sẽ dẫn đến $p\nmid m’$ và vì thế mà $p\mid x$. Nên $p\mid\gcd\left( x,\,m\right)$. Vô lý.

Tiếp theo ta chứng minh rằng mọi số nguyên $a$ nguyên tố cùng nhau với $mm’$ phải đồng dư mod $m$ với một số nguyên có dạng $$mx’+m’x,\, \gcd\left( x,\,m\right)=\gcd\left( x’,\,m’\right)=1.$$Từ Định lý 5.1 sẽ tồn tại hai số nguyên $x,\,x’$ thoả $$a\equiv mx’+m’x\pmod{mm’} .$$ Giờ ta chứng minh $\gcd\left( x,\,m\right)=\gcd\left( x’,\,m’\right)=1$.Nếu $\gcd(x,\,m)=d\ne 1$, lúc đó $\gcd(a,\,m)=\gcd\left( mm’,\,mx’+m’x\right)=\gcd\left( m’x,\,m\right)=\gcd(x,\,m)=d\ne 1$, trái với giả thiết. Tương tự ta cũng có $\gcd\left(x’,\,m’\right)=1$.

Chúng ta đã chứng minh ở định lý 5.1 rằng những số là không đồng dư. Từ đó định lý được chứng minh.

$\square$

Những lý lẽ trên cũng đồng thời chỉ ra $\varphi(m)$ là một hàm nhân tính, cụ thể như sau:

Định lý. Nếu $\gcd\left(m,\,m’\right)=1$, lúc đó\[\varphi \left( {mm’} \right) = \varphi \left( m \right)\varphi \left( {m’} \right).\] Một hàm nhân đầy đủ được xác định nhờ giá trị lấy ở các bậc nguyên tố do đó nếu phân tích chuẩn của $m$ được cho bởi \[m=p_1^{l_1}p_2^{l_2}\ldots p_s^{l_s},\,\quad p_1<p_2<\ldots<p_s\] lúc đó, từ Định lý 5.3 ta có \[\varphi \left( m \right) = \varphi \left( {p_1^{{l_1}}} \right)\varphi \left( {p_2^{{l_2}}} \right) \ldots \varphi \left( {p_s^{{l_s}}} \right).\]

Định lý. Với $p$ là số nguyên tố và số nguyên dương $l$ ta có \[\varphi \left( {p^l}\right) = p^l\left( 1 – \dfrac{1}{p}\right),\] và vì thế sẽ dẫn đến \[\varphi (m) = m\prod\limits_{p\mid m} \left( 1 – \dfrac{1}{p}\right),\] trong đó $p$ là những ước nguyên tố khác nhau của $m$.

Chứng minh. Xét những số nguyên trong khoảng từ $1\le n\le p^l$. Có duy nhất các số nguyên có dạng $p^{l-1}$ là bội của $p$ còn những số khác thì nguyên tố cùng nhau với $p$ vì thế \[\varphi ({p^l}) = {p^l} – {p^{l – 1}} = {p^l}\left(1 – \dfrac{1}{p}\right).\] Biểu thức thứ hai được chứng minh theo biểu thức này và tính chất nhân của hàm.

$\square$

Ví dụ. $\varphi \left( {300} \right) = \varphi \left( {{2^2}{{.3.5}^2}} \right) = {2^2}{.3.5^2}.\left( {1 – \dfrac{1}{2}} \right)\left( {1 – \dfrac{1}{3}} \right)\left( {1 – \dfrac{1}{5}} \right) = 80$.

Bài tập 1. Chứng minh rằng $\sum\limits_{d\mid m} {\varphi (d)} = m$, trong đó $d$ chạy khắp những ước nguyên dương của $m$.

Bài tập 2. Với $P$ là tích của những ước nguyên tố phân biệt của $\gcd(m,\,n)$. Chứng minh rằng \[\dfrac{{\varphi (mn)}}{{\varphi (m)\varphi (n)}} = \dfrac{P}{{\varphi (P)}}.\]

Bài tập 3. Dùng Định lý 1.7.1 để chứng minh Định lý 5.4.