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

Đối với những bạn yêu thích Toán chắc đều biết về nhà toán học người Pháp Pierre de Fermat. Những đóng góp của ông thì không thể nào cân đo, đong đếm, chỉ có thể dùng hai từ “vĩ đại” để diễn tả. Các công trình của Fermat ảnh hưởng hầu như đến mọi lĩnh vực của Toán học: Giải tích, Xác suất,  Số học…

Trong bài viết hôm nay ta chỉ chú ý đến lĩnh vực Số học. Đây là ngành mà Fermat có 2 định lý rất nổi tiếng: Định lý nhỏ Fermat và Định lý lớn Fermat. Định lý lớn Fermat là bài toán hóc búa thách thức các nhà toán học trong hơn 300 năm và đã được giải quyết bởi nhà toán học người Anh có tên là Andrew Wiles vào năm 1994. Trong khi đó, Định lý nhỏ Fermat là một kết quả đẹp và có nhiều ứng dụng trong Toán học. Sau đây, ta sẽ tìm hiểu một cách cơ bản nhất về định lý này.

Định lý 1 (Định lý nhỏ Fermat). Cho $p$ là số nguyên tố và $a\in {{Z}_{>0}}$ thỏa $\left( a,p \right)=1$. Khi đó ${{a}^{p-1}}\equiv 1\left( \bmod p \right)$ (ký hiệu $a\equiv b\left( \bmod \,c \right)$ được hiểu là $a-b$ chia hết cho $c$ ).   

Chứng minh

Xét dãy gồm $\left( p-1 \right)$ số nguyên dương $a,2a,3a,\ldots ,\left( p-1 \right)a$. Vì $\left( a,p \right)=1$ nên không tồn tại $i,j\in \left\{ 1,\ldots ,p-1 \right\};i\ne j$ sao cho $ia\equiv ja\left( \bmod p \right)$, suy ra khi lấy $\left( p-1 \right)$ số nguyên dương $a,2a,3a,\ldots ,\left( p-1 \right)a$ chia cho $p$ thì được $p-1$ số dư khác nhau lấy từ tập $\left\{ 1,\ldots ,p-1 \right\}$. Do đó,

$a.2a.3a\ldots \left( p-1 \right)a\equiv \left( p-1 \right)!\left( \bmod p \right)$

$\Leftrightarrow \left( p-1 \right)!{{a}^{p-1}}\equiv \left( p-1 \right)!\left( \bmod p \right)$

$\Leftrightarrow {{a}^{p-1}}\equiv 1\left( \bmod p \right)$ (đpcm).

Định lý nhỏ Fermat có nhiều ứng dụng hay, một trong số đó là xác định số dư khi chia cho một số nguyên tố.

Ví dụ 1. Tìm số dư khi chia ${{2}^{2014}}$ cho $17$.

Giải

Vì $17$ là số nguyên tố nên theo Định lý nhỏ Fermat ta được

${{2}^{16}}\equiv 1\left( \bmod \,17 \right)$       (1)

Lấy $2014$ chia cho $16$ ta được thương là $125$ và số dư là $14$, suy ra

${{2}^{2014}}\equiv {{2}^{125\times 16+14}}\equiv {{1}^{125}}\times {{2}^{14}}\equiv 13\left( \bmod \,17 \right)$.

Vậy $13$ là số dư khi chia ${{2}^{2014}}$ cho $17$.

Từ Định lý nhỏ Fermat ta được một hệ quả là: Cho $n\in {{Z}_{>1}}$,  nếu tồn tại $a\in {{Z}_{>1}}$  sao cho $\left( a,n \right)=1$ và ${{a}^{n-1}}-1$ không chia hết cho $n$ thì $n$ là hợp số.

Một câu hỏi được đặt ra: nếu ${{a}^{n-1}}\equiv 1\left( \bmod \,n \right)$ thì ta có thể suy ra $n$ là số nguyên tố hay không? Câu trả lời, rất tiếc, là không phải, ta xét ví dụ sau:

Ví dụ 2. Số $561$ là hợp số vì $561=3\times 11\times 17$. Ta sẽ chỉ ra rằng ${{2}^{560}}\equiv 1\left( \bmod \,561 \right)$. Áp dụng Định lý Fermat nhỏ ta được

${{2}^{560}}={{\left( {{2}^{2}} \right)}^{280}}\equiv 1\left( \bmod \,3 \right)$

${{2}^{560}}={{\left( {{2}^{10}} \right)}^{56}}\equiv 1\left( \bmod \,11 \right)$

${{2}^{560}}={{\left( {{2}^{16}} \right)}^{45}}\equiv 1\left( \bmod \,17 \right)$

Từ đây ta suy ra ${{2}^{560}}\equiv 1\left( \bmod \,561 \right)$.

Định nghĩa 1. Cho $a\in {{Z}_{>1}}$, nếu $n$ là hợp số và đồng thời ${{a}^{n-1}}\equiv 1\left( \bmod \,n \right)$ thì $n$ là số giả nguyên tố cơ sở $a$.

Từ ví dụ 2 ta suy ra được $561$ là số giả nguyên tố cơ sở 2.

Định lý 2. Tồn tại vô số số giả nguyên tố cơ sở 2.

Chứng minh

Giả sử $n$ là số giả nguyên tố cơ sở 2, ta sẽ chứng tỏ rằng $m={{2}^{n}}-1$ cũng là số giả nguyên tố cơ sở 2.

Vì $n$ là số giả nguyên tố cơ sở 2 nên ${{2}^{n-1}}\equiv 1\left( \bmod \,n \right)$ hay ${{2}^{n-1}}-1=kn$, suy ra $m-1=2kn$. Do đó, ${{2}^{m-1}}-1\equiv {{2}^{2nk}}-1\equiv {{2}^{n}}-1\equiv 0\left( \bmod \,m \right)$.

Hơn nữa, vì $n$ là hợp số nên $m={{2}^{n}}-1$ cũng là hợp số. Vậy $m={{2}^{n}}-1$ là số giả nguyên tố cơ sở 2.

Định nghĩa 2. Hợp số $n$ được gọi là số Carmichael nếu $n$ là số giả nguyên tố với mọi cơ sở a thỏa $\left( a,n \right)=1$.

Ví dụ 3. Số $561$ là số Carmichael. Thật vậy, lấy $a\in {{Z}_{>1}}$ sao cho $\left( a,561 \right)=1$, suy ra $\left( a,3 \right)=\left( a,11 \right)=\left( a,17 \right)=1$. Áp dụng Định lý nhỏ Fermat ta được

${{a}^{560}}={{\left( {{a}^{2}} \right)}^{280}}\equiv 1\left( \bmod \,3 \right)$

${{a}^{560}}={{\left( {{a}^{10}} \right)}^{56}}\equiv 1\left( \bmod \,11 \right)$

${{a}^{560}}={{\left( {{a}^{16}} \right)}^{45}}\equiv 1\left( \bmod \,17 \right)$

Do đó ${{a}^{560}}\equiv 1\left( \bmod \,561 \right)$. Vậy $561$ là số Carmichael.

Định lý 3. Cho $n\in {{Z}_{>1}}$ là hợp số thỏa $n={{p}_{1}}{{p}_{2}}\ldots {{p}_{k}}$ với $k>2$ và ${{p}_{i}},i=\overline{1,k}$ là các số nguyên tố lẻ thỏa mãn $n\equiv 1\left( \bmod \,{{p}_{i}}-1 \right),i=\overline{1,k}$. Khi đó, $n$ là số Carmichael.

Chứng minh

Lấy $a\in {{Z}_{>0}}$ thỏa $\left( a,n \right)=1$, suy ra $\left( a,{{p}_{i}} \right)=1,i=\overline{1,k}$. Áp dụng Định lý nhỏ Fermat ta được

${{a}^{n-1}}\equiv {{\left( {{a}^{{{p}_{i}}-1}} \right)}^{{{k}_{i}}}}\equiv 1\left( \bmod {{p}_{i}} \right),i=\overline{1,k}$

Do đó, ${{a}^{n-1}}\equiv 1\left( \bmod \,n \right)$. Vậy $n$ là số Carmichael.

Giả thuyết 1. Tồn tại vô hạn số Carmichael.