Trong bài viết hôm nay, ta tiếp tục tìm hiểu thêm một số kết
quả quan trọng có ảnh hưởng đến kết quả đạt được về các số Carmichael.
Định lý 1. Cho $n\in
{{Z}_{>0}}$. Khi đó $\sum\limits_{d|n}{\varphi
\left( d \right)}=n$, trong đó $d$ chạy trên mọi ước dương của $n$.
Chứng minh
Đặt ${{A}_{d}}=\left\{ 1\le a\le n:\left( a,n \right)=d
\right\}$, trong đó $d$chạy trên mọi ước dương của $n$, ta thấy các tập ${{A}_{d}}$
rời nhau từng đôi một và $\bigcup\limits_{d|n}{{{A}_{d}}}=\left\{
1,2,\ldots ,n \right\}$.
Lấy $a\in {{A}_{d}}$, theo cách xây dựng trên ta được $\left(
a,n \right)=d$ hay $\left( \frac{a}{d},\frac{n}{d} \right)=1$. Vậy, số phần tử
thuộc tập ${{A}_{d}}$ bằng số các số nguyên dương nguyên tố cùng nhau với $\frac{n}{d}$
và không vượt quá $\frac{n}{d}$, tức bằng $\varphi \left( \frac{n}{d} \right)$.
Ta suy ra $n=\sum\limits_{d|n}{\left| {{A}_{d}}
\right|}=\sum\limits_{d|n}{\varphi \left( \frac{n}{d}
\right)}=\sum\limits_{d|n}{\varphi \left( d \right)}$.
Định nghĩa 1. Giả sử $a,b\in {{Z}_{>0}}$ và $\left( a,b
\right)=1$. Khi đó, số nguyên dương $x$ nhỏ nhất thỏa mãn ${{a}^{x}}\equiv
1\left( \bmod \,b \right)$ được gọi là bậc của $a$ theo modulo $b$. Ký hiệu: $x=or{{d}_{b}}a$.
Ví dụ 1. Từ định
nghĩa được $or{{d}_{5}}4=2,or{{d}_{10}}3=4$.
Định lý 2. Giả sử $a,b\in {{Z}_{>0}}$ và $\left( a,b
\right)=1$. Nếu $x\in {{Z}_{>0}}$ là nghiệm của phương trình ${{a}^{x}}\equiv
1\left( \bmod \,b \right)$ thì $d=or{{d}_{b}}a|x$.
Chứng minh
Ta viết $x=du+r$ với
${{a}^{d}}\equiv 1\left( \bmod \,b \right)\Rightarrow {{a}^{x}}\equiv
{{a}^{ud+r}}\equiv {{a}^{r}}\left( \bmod \,b \right)$
Mặt khác, ${{a}^{x}}\equiv 1\left( \bmod \,b \right)$ nên ${{a}^{r}}\equiv 1\left( \bmod \,b
\right)$. Theo giả thiết $d$ là bậc của $a$ theo modulo $b$ nên $r=0$. Vậy $d=or{{d}_{b}}a|x$.
Từ Định lý 2, ta được một số hệ quả quan trọng sau (chứng
minh xin dành cho bạn đọc):
Hệ quả 1. Nếu $a,b\in {{Z}_{>0}}$ và $\left( a,b
\right)=1$ thì $or{{d}_{b}}a|\varphi \left( b \right)$.
Hệ quả 2. Nếu $a,b\in {{Z}_{>0}}$ và $\left( a,b
\right)=1$ thì ${{a}^{i}}\equiv {{a}^{j}}\left( \bmod \,b
\right)\Leftrightarrow i\equiv j\left( \bmod \,or{{d}_{b}}a \right)$.
Định lý 3. Giả sử
$a,b\in {{Z}_{>0}}$ và $\left( a,b \right)=1$. Khi đó, với mọi $k\in
{{Z}_{>0}}$ ta có $or{{d}_{b}}{{a}^{k}}=\frac{d}{\left( d,k \right)}$, trong
đó $d=or{{d}_{b}}a$.
Chứng minh
Đặt $m=\frac{d}{\left( d,k \right)}$, trước hết ta chứng tỏ ${{a}^{km}}\equiv
1\left( \bmod \,b \right)$. Vì $\left( d,k \right)|k$ nên $d=m\left( d,k \right)|mk$, suy ra
Gọi $n$ là số nguyên dương nhỏ nhất sao cho ${{a}^{kn}}\equiv
1\left( \bmod \,b \right)$, cũng theo Định lý 2 ta được $d|kn$. Từ đây ta suy
ra $\frac{d}{\left( d,k \right)}|\frac{k}{\left( d,k \right)}n$. Hiển nhiên $\left(
\frac{d}{\left( d,k \right)},\frac{k}{\left( d,k \right)} \right)=1$ nên $\frac{d}{\left(
d,k \right)}|n$. Vậy $n=m$. Định lý đã được chứng minh.
Hệ quả 3. Giả sử $k,a,b\in
{{Z}_{>0}}$ và $\left( a,b \right)=1,\left( k,or{{d}_{b}}a \right)=1$. Khi
đó, $or{{d}_{b}}{{a}^{k}}=or{{d}_{b}}a$.
Định nghĩa 2. Giả sử $a,b\in {{Z}_{>0}}$ và $\left( a,b
\right)=1$. Nếu $or{{d}_{b}}a=\varphi \left( b \right)$ thì $a$được gọi là căn
nguyên thủy theo modulo $b$.
Ví dụ 1. Số 2 và
3 là hai căn nguyên thủy theo modulo 5. Số 4 không phải là căn nguyên thủy theo
modulo 5 vì $or{{d}_{5}}4=2\ne 4=\varphi \left( 5 \right)$.
Số 3 là căn nguyên thủy theo modulo 2 cũng như theo modulo 4.
Định lý 4. Với mọi $k\in {{Z}_{>2}}$. Số ${{2}^{k}}$
không có căn nguyên thủy.
Chứng minh
Ta sẽ chứng minh bằng qui nạp rằng ${{a}^{{{2}^{k-2}}}}\equiv
1\left( \bmod \,{{2}^{k}} \right)$ với mọi $a\in {{Z}_{>0}}$ thỏa $\left(
a,2 \right)=1$ và $k\in {{Z}_{>2}}$.
Với $k=3$, vì $\left( a,2 \right)=1$ nên $a=2m+1$ với $m\in
{{Z}_{>0}}$. Khi đó
${{a}^{2}}={{\left(
2m+1 \right)}^{2}}=4m\left( m+1 \right)+1\equiv 1\left( \bmod \,{{2}^{3}}
\right)$
Vậy công thức trên đúng với $k=3$.
Giả sử ${{a}^{{{2}^{n-2}}}}\equiv 1\left( \bmod \,{{2}^{n}}
\right)$, ta cần chứng minh ${{a}^{{{2}^{n-1}}}}\equiv 1\left( \bmod
\,{{2}^{n+1}} \right)$.
Thật vậy, vì ${{a}^{{{2}^{n-2}}}}\equiv 1\left( \bmod
\,{{2}^{n}} \right)$ nên ${{a}^{{{2}^{n-2}}}}={{2}^{n}}m+1$ với $m\in
{{Z}_{>0}}$. Khi đó
${{a}^{{{2}^{n-1}}}}={{\left( {{2}^{n}}m+1
\right)}^{2}}={{2}^{2n}}{{m}^{2}}+{{2}^{n+1}}m+1\equiv 1\left( \bmod
\,{{2}^{n+1}} \right)$
Do đó, ta đã chứng tỏ
được ${{a}^{{{2}^{k-2}}}}\equiv 1\left( \bmod \,{{2}^{k}} \right)$ với mọi $a\in
{{Z}_{>0}}$ thỏa $\left( a,2 \right)=1$ và $k\in {{Z}_{>2}}$.
Hơn nữa, $\varphi \left( {{2}^{k}}
\right)={{2}^{k-1}}>{{2}^{k-2}}$, ta suy ra ${{2}^{k}}$ không có căn nguyên
thủy.
Định lý 5. Giả sử a là căn nguyên thủy theo modulo b,
trong đó $b>1$. Khi đó ${{a}^{k}}$ là căn nguyên thủy theo modulo b khi và
chỉ khi $\left( k,\varphi \left( b \right) \right)=1.$
Định lý 5 được suy ra trực tiếp từ Định lý 3 và Định nghĩa
2.
Định lý 6. Nếu a
là căn nguyên thủy theo modulo b, trong đó $b>1$ thì dãy các số $a,{{a}^{2}},\ldots
,{{a}^{\varphi \left( b \right)}}$ lập thành hệ thặng dư thu gọn theo modulo $b$.
Chứng minh
Vì $\left( a,b \right)=1$ nên $\left( {{a}^{k}},b
\right)=1,k=\overline{1,\varphi \left( b \right)}$. Tiếp theo ta chứng tỏ không
có hai giá trị nào trong dãy đồng như với nhau theo modulo $b$.
Giả sử tồn tại $i,j\in \left\{ 1,2,\ldots ,\varphi \left( b
\right) \right\};i\ne j$ sao cho ${{a}^{i}}\equiv {{a}^{j}}\left( \bmod \,b
\right)$. Sử dụng Hệ quả 2 ta được $i\equiv j\left( \bmod \,\varphi \left( b
\right) \right)$ (vô lý). Vậy dãy các số
$a,{{a}^{2}},\ldots ,{{a}^{\varphi \left( b \right)}}$ lập thành hệ thặng dư
thu gọn theo modulo $b$.
Không có nhận xét nào:
Đăng nhận xét