5/8/14

ĐỊNH LÝ NHỎ FERMAT (Phần 2)

Trong bài viết hôm nay, chúng ta sẽ tìm hiểu một số vấn đề quan trọng để hiểu hơn về các số Carmichael. Như đã biết, nếu  $n=\prod\limits_{i=1}^{k}{{{p}_{i}}}$ với $k>2$ và ${{p}_{i}}$ là các số nguyên tố phân biệt khác 2, đồng thời $n-1\equiv 0\left( \bmod \,{{p}_{i}}-1 \right)$ thì $n$ là số Carmichael. Một câu hỏi đặt ra: Mệnh đề đảo có đúng không? Câu trả lời là có, ta có kết quả rất đẹp sau đây:
Định lý 1. Nếu $n$ là số Carmichael thì $n$ luôn có dạng $n=\prod\limits_{i=1}^{k}{{{p}_{i}}}$ với $k>2$ và ${{p}_{i}}$ là các số nguyên tố phân biệt khác 2, đồng thời $n-1\equiv 0\left( \bmod \,{{p}_{i}}-1 \right)$ với $i=\overline{1,k}$.
Chứng minh Định lý 1 là một quá trình khá khó khăn. Đề bạn đọc dễ tiếp cận, tôi xin trình bày một số khái niệm và kết quả quan trọng, nó không chỉ giúp ích cho ta chứng minh Định lý 1 mà còn là công cụ hay để giải những vấn đề khác.
Định nghĩa 1. Cho $n\in {{Z}_{>0}}$, Phi-hàm Euler $\varphi \left( n \right)$ là hàm số số học có giá trị bằng số các số không vượt quá $n$ và nguyên tố cùng nhau với $n$.
Ví dụ 1. Từ định nghĩa ta suy ra được $\varphi \left( 1 \right)=1,\varphi \left( 2 \right)=1,\varphi \left( 4 \right)=2,\varphi \left( 5 \right)=4.$
Mệnh đề 1. Nếu $p$ là số nguyên tố thì $\varphi \left( p \right)=p-1$.
Chứng minh
Vì $p$ là số nguyên tố nên $\left( k,p \right)=1$ với $k=\overline{1,p-1}$. Theo Định nghĩa 1 ta có ngay $\varphi \left( p \right)=p-1$.
Mệnh đề 2. Nếu $p$ là số nguyên tố và $\upsilon \in {{Z}_{>0}}$ thì $\varphi \left( {{p}^{\upsilon }} \right)={{p}^{\upsilon }}-{{p}^{\upsilon -1}}$.
Chứng minh
Gọi $m$ là số nguyên dương không vượt quá ${{p}^{\upsilon }}$ và $\left( m,{{p}^{\upsilon }} \right)>1$. Vì $p$ là số nguyên tố nên $p|m$, hay $m=pu$ với $u\in {{Z}_{>0}}$.
Do $m\le {{p}^{\upsilon }}$ nên $1\le u\le {{p}^{\upsilon -1}}$. Vậy có ${{p}^{\upsilon -1}}$ số nguyên dương không vượt quá ${{p}^{\upsilon }}$ và không nguyên tố cùng nhau với ${{p}^{\upsilon }}$. Ta kết luận $\varphi \left( {{p}^{\upsilon }} \right)={{p}^{\upsilon }}-{{p}^{\upsilon -1}}$.
Mệnh đề 3. Cho $a,b\in {{Z}_{>0}}$ thỏa $\left( a,b \right)=1$. Khi đó $\varphi \left( ab \right)=\varphi \left( a \right)\varphi \left( b \right)$.     (1)
Chứng minh
Nếu $a=1$ hoặc $b=1$ thì (1) hiển nhiên đúng.
Ta xét trường hợp $a,b\in {{Z}_{>1}}$, đặt
            $X=\left\{ 1,2,3,\ldots ,ab \right\}$
            ${{X}_{i}}=\left\{ i,a+i,2a+i,\ldots ,\left( b-1 \right)a+i \right\}$ với $i=\overline{1,a}$.
Ta dễ dàng chứng tỏ được $X=\bigcup\limits_{i=1}^{m}{{{X}_{i}}}$ và ${{X}_{i}}\cap {{X}_{j}}=\varnothing $ với mọi $i\ne j$.
Lấy $k\in \left\{ 1,2,\ldots ,a \right\}$. Nếu $\left( k,a \right)>1$ thì mọi phần tử thuộc tập ${{X}_{k}}$ cũng không nguyên tố cùng nhau với $a$, suy ra không nguyên tố cùng nhau với $ab$.  Còn nếu $\left( k,a \right)=1$ thì mọi phần tử thuộc tập ${{X}_{k}}$ nguyên tố cùng nhau với $a$.
Do đó, để xác định $\varphi \left( ab \right)$, ta chỉ cần quan tâm đến các số thuộc tập ${{X}_{k}}$ thỏa $\left( k,a \right)=1$, có $\varphi \left( a \right)$ tập như thế. Hơn nữa, trong mỗi tập ${{X}_{k}}$ có $b$ phần tử$k,a+k,2a+k,\ldots ,\left( b-1 \right)a+k$ lập thành hệ thặng dư đầy đủ theo modulo b. Vì thế, trong mỗi tập ${{X}_{k}}$ có $\varphi \left( b \right)$ phần tử nguyên tố cùng nhau với $b$. Vậy có tổng cộng $\varphi \left( a \right)\varphi \left( b \right)$ phân tử thuộc tập $X$ nguyên tố cùng nhau với $ab$. Ta kết luận $\varphi \left( ab \right)=\varphi \left( a \right)\varphi \left( b \right)$.
Mệnh đề 4. Nếu $n=p_{1}^{{{\alpha }_{i}}}p_{2}^{{{\alpha }_{2}}}\ldots p_{k}^{{{\alpha }_{k}}}$ là phân tích tiếu chuẩn của $n$ ra thừa số nguyến tố thì
$\varphi \left( n \right)=n\left( 1-\frac{1}{{{p}_{1}}} \right)\left( 1-\frac{1}{{{p}_{2}}} \right)\ldots \left( 1-\frac{1}{{{p}_{k}}} \right)$
Mệnh đề 4 là hệ quả trực tiếp của Mệnh đề 2 và 3.
Sau đây ta sẽ tìm hiểu một trong những kết quả đẹp nhất của môn số học:
Định lý Euler. Cho $a,b\in {{Z}_{>0}}$ thỏa $\left( a,b \right)=1$. Khi đó ${{a}^{\varphi \left( b \right)}}\equiv 1\left( \bmod \,\,b \right)$.
Chứng minh
Giả sử ${{r}_{1}},{{r}_{2}},\ldots ,{{r}_{\varphi \left( b \right)}}$ là tất cả các số không vượt quá $b$ và nguyên tố cùng nhau với $b$. Lấy các giá trị $a{{r}_{1}},a{{r}_{2}},\ldots ,a{{r}_{\varphi \left( a \right)}}$ chia cho $b$ ta được các số dư ${{s}_{1}},{{s}_{2}},\ldots ,{{s}_{\varphi \left( b \right)}}$. Vì \[\left( a{{r}_{i}},b \right)=1,i=\overline{1,\varphi \left( b \right)}\] nên $\left( {{s}_{i}},b \right)=1,i=\overline{1,\varphi \left( b \right)}$. Vậy bộ $\left( {{s}_{1}},{{s}_{2}},\ldots ,{{s}_{\varphi \left( b \right)}} \right)$ là một hoán vị của bộ $\left( {{r}_{1}},{{r}_{2}},\ldots ,{{r}_{\varphi \left( b \right)}} \right)$. Khi đó
$a{{r}_{i}}\equiv {{s}_{i}}\left( \bmod \,b \right),i=\overline{1,\varphi \left( b \right)}$
$\Rightarrow a{{r}_{1}}a{{r}_{2}}\ldots a{{r}_{\varphi \left( b \right)}}\equiv {{s}_{1}}{{s}_{2}}\ldots {{s}_{\varphi \left( b \right)}}\left( \bmod \,b \right)$
$\Leftrightarrow {{a}^{\varphi \left( b \right)}}\equiv 1\left( \bmod \,b \right)$ (đpcm).
Định lý Euler là một công cụ hay để tìm số dư khi chia các số có dạng ${{a}^{k}}$ cho $n$ với $\left( a,n \right)=1$.
Ví dụ 1. Tìm số dư khi chia ${{2}^{2014}}$ cho $15$.
Giải
Vì $\left( 2,15 \right)=1$ nên theo Định lý Euler ta được
${{2}^{\varphi \left( 15 \right)}}\equiv 1\left( \bmod \,15 \right)\Leftrightarrow {{2}^{8}}\equiv 1\left( \bmod 15 \right)$
Lấy 2014 chia 8 ta được số dư là 6 nên
${{2}^{2014}}\equiv {{2}^{6}}\equiv 4\left( \bmod \,15 \right)$
Số dư khi chia ${{2}^{2014}}$ cho $15$ là 4.
Ví dụ 2. Tìm hai chữ số tận cùng của ${{7}^{2042}}$.
Giải
Muốn tìm hai chữ số tận cùng của ${{7}^{2042}}$ ta cần tìm số dư khi chia ${{7}^{2042}}$ cho $100$.
Vì $\left( 7,100 \right)=1$ nên theo Định lý Euler ta được
${{7}^{\varphi \left( 100 \right)}}\equiv 1\left( \bmod 100 \right)\Leftrightarrow {{7}^{40}}\equiv 1\left( \bmod \,100 \right)$
Lấy 2042 chia 40 ta được số dư là 2 nên
${{7}^{2042}}\equiv {{7}^{2}}\equiv 49\left( \bmod \,100 \right)$
Vậy ${{7}^{2042}}$ có hai chữ số tận cùng là 49.

Không có nhận xét nào: