ĐỊNH LÝ NHỎ FERMAT (Phần cuối)

Đã tới lúc ta kết thúc bài viết về Định lý nhỏ Fermat bằng việc chứng minh định lý đã nêu ra ở phần 2:

Định lý 1. Nếu $n$ là số Carmichael thì $n$ luôn có dạng $n={{p}_{1}}{{p}_{2}}\ldots {{p}_{m}}$ trong đó $m\ge 3$ và ${{p}_{i}},i=\overline{1,m}$ là các số nguyên tố lẻ, đồng thời $n-1\equiv 0\left( \bmod {{p}_{i}}-1 \right),i=\overline{1,m}$.

Trước hết ta chứng minh các bổ đề sau:

Bồ đề 1.  Nếu $n={{2}^{s}},s\in {{Z}_{>1}}$  thì $n$ không phải là số Carmichael.

Chứng minh

Giả sử tồn tại  $s\in {{Z}_{>1}}$  để  $n={{2}^{s}}$ là các số Carmichael, tức là

${{a}^{{{2}^{s}}-1}}\equiv 1\left( \bmod \,{{2}^{s}} \right),\forall a\in {{Z}_{>0}},\left( a,2 \right)=1$.

Chọn  $a=3$  ta được  ${{3}^{{{2}^{s}}-1}}\equiv 1\left( \bmod \,{{2}^{s}} \right)$ hay ${{3}^{{{2}^{s}}}}\equiv 3\left( \bmod \,{{2}^{s}} \right)$.

Sử dụng Định lý Euler ta được

${{3}^{\varphi \left( {{2}^{s}} \right)}}\equiv 1\left( \bmod \,{{2}^{s}} \right)\Leftrightarrow {{3}^{{{2}^{s-1}}}}\equiv 1\left( \bmod \,{{2}^{s}} \right)$,

suy ra ${{3}^{{{2}^{s}}}}\equiv 1\left( \bmod \,{{2}^{s}} \right)$. Do đó, $3\equiv 1\left( \bmod {{2}^{s}} \right)$  (vô lý).

Vậy $n$ không phải là số Carmichael.

Bổ đề 1 cho ta một kết luận là:  nếu $n$ là số Carmichael thì $n$ phải có ít nhất một ước nguyên tố lẻ, tức là  $n=r{{p}^{k}}$ với $\left( r,p \right)=1$, $p$ là số nguyên tố lẻ và $k\ge 1$.

Bổ đề 2. Giả sử  $n=r{{p}^{k}}$ với $\left( r,p \right)=1$, $p$ là số nguyên tố lẻ và $k\ge 1$. Nếu $n$ là số Carmichael thì $k=1$ .

Chứng minh

Giả sử $k\ge 2$. Vì  $n$ là số Carmichael nên ${{a}^{n-1}}={{a}^{r{{p}^{k}}-1}}\equiv 1\left( \bmod r{{p}^{k}} \right),\forall a\in {{Z}_{>0}},\left( a,r{{p}^{k}} \right)=1$, suy ra

${{a}^{r{{p}^{k}}-1}}\equiv 1\left( \bmod {{p}^{k}} \right),\forall a\in {{Z}_{>0}},\left( a,r{{p}^{k}} \right)=1$

Gọi $\omega $ là căn nguyên thủy của ${{p}^{k}}$,  hiển nhiên $\left( \omega ,{{p}^{k}} \right)=1$.

Nếu $\left( \omega ,r \right)=1$  thì ta chọn $a=\omega $. Khi đó $\varphi \left( {{p}^{k}} \right)={{p}^{k-1}}\left( p-1 \right)$ là ước của  $r{{p}^{k}}-1$ , suy ra  ${{p}^{k-1}}$  là ước của  $r{{p}^{k}}-1$ (vô lý).

Nếu $\left( \omega ,r \right)=d>1$ thì ta xét dãy các số nguyên $\omega ,\omega +{{p}^{k}},\ldots ,\omega +j{{p}^{k}},\ldots $. Vì  $\omega +j{{p}^{k}}\equiv \omega \left( \bmod {{p}^{k}} \right)$  nên với mọi $j\in {{Z}_{\ge 0}}$ ,  $\omega +j{{p}^{k}}$ là căn nguyên thủy của ${{p}^{k}}$.

Giả sử $r$ có tất cả các ước nguyên tố là ${{q}_{1}},{{q}_{2}},\ldots ,{{q}_{u}}$.  Khi đó, có ít nhất một giá trị ${{q}_{i}}$  là ước của $\omega $. Không giảm tổng quát, giả sử ${{q}_{1}},{{q}_{2}},\ldots ,{{q}_{{{j}_{o}}}}$ là ước của  $\omega $.

Nếu $j_{0}=u$ thì ta cho $j=1$. Khi đó,  $\left( \omega +{{p}^{k}},r \right)=1$ hay  $\left( \omega +{{p}^{k}},r{{p}^{k}} \right)=1$. Ta chọn  $a=\omega +{{p}^{k}}$, suy ra $\varphi \left( {{p}^{k}} \right)={{p}^{k-1}}\left( p-1 \right)$ là ước của  $r{{p}^{k}}-1$. Vì thế  ${{p}^{k-1}}$  là ước của  $r{{p}^{k}}-1$ (vô lý).

Nếu $j_{0} \le u-1$ thì ta cho $j={{q}_{{{j}_{0}}+1}}\ldots {{q}_{u}}$.  Khi đó,  $\left( \omega +j{{p}^{k}},r \right)=1$ hay  $\left( \omega +j{{p}^{k}},r{{p}^{k}} \right)=1$. Ta chọn  $a=\omega +j{{p}^{k}}$, suy ra $\varphi \left( {{p}^{k}} \right)={{p}^{k-1}}\left( p-1 \right)$ là ước của $r{{p}^{k}}-1$. Vì thế ${{p}^{k-1}}$ là ước của $r{{p}^{k}}-1$ (vô lý).

Vậy $k=1$.

Bổ đề 2 cho ta kết luận:  nếu $n$ là số Carmichael thì $n={{p}_{1}}{{p}_{2}}\ldots {{p}_{m}}$  với $m\ge 2$ và ${{p}_{i}},i=\overline{1,m}$  là các số nguyên tố. Hơn nữa,  $\varphi \left( {{p}_{i}} \right)={{p}_{i}}-1$  là ước của $n-1$. Điều này chứng tỏ $n$ là một số lẻ.

Bổ đề 3.  Nếu $n$ là số Carmichael thì số ước nguyên tố của $n$ không bé hơn $3$.

Chứng minh

Giả sử $n$ có số ước nguyên tố bé hơn 3. Vì $n$ là số Carmichael nên theo Bổ đề 2  ta được $n={{p}_{1}}{{p}_{2}}$  với ${{p}_{1}},{{p}_{2}}$ là các số nguyên tố lẻ, ${{p}_{1}}$ bé hơn ${{p}_{2}}$.  

Cũng theo Bổ đề 2 ta có ${{p}_{1}}{{p}_{2}}-1\vdots {{p}_{1}}-1,{{p}_{1}}{{p}_{2}}-1\vdots {{p}_{2}}-1$. Ta suy ra

${{p}_{2}}-1|\left( {{p}_{1}}{{p}_{2}}-1 \right)-\left( {{p}_{2}}-1 \right)={{p}_{2}}\left( {{p}_{1}}-1 \right)$ (1)

Vì  $\left( {{p}_{2}},{{p}_{2}}-1 \right)=1$ nên từ (1) ta suy ra ${{p}_{2}}-1$ là ước của ${{p}_{1}}-1$. Điều này là vô lý vì  ${{p}_{1}}-1$ bé hơn  ${{p}_{2}}-1$.

Vậy $n$ có số ước nguyên tố không bé hơn 3.

Sử dụng Bồ đề 1, 2, 3 ta chứng minh được Định lý 1.