Trong bài viết hôm nay, chúng ta đưa ra cách xác định một số
nguyên dương có dạng như thế nào thì sẽ có căn nguyên thủy (dựa trên quyển Số học thuật toán của tác giả Hà Huy Khoái và Phạm Huy Điển).
Định lý 1. Nếu số nguyên dương b có căn nguyên thủy,
thì nó có tất cả $\varphi \left( \varphi \left( b \right) \right)$ căn nguyên
thủy không đồng dư theo modulo b.
Chứng minh
Trong bài viết trước, ta đã chứng tỏ được nếu $a$ là căn
nguyên thủy của $b$ thì dãy các số $a,{{a}^{2}},\ldots ,{{a}^{\varphi \left( b
\right)}}$ lập thành một hệ thặng dư thu gọn theo modulo $b$. Số căn nguyên thủy
theo modulo $b$ đúng bằng số các số nguyên dương không vượt quá $\varphi \left(
b \right)$ và nguyên tố cùng nhau với $\varphi \left( b \right)$, tức bằng $\varphi
\left( \varphi \left( b \right) \right)$.
Định lý 2 (Định lý
Lagrange). Cho đa thức $P\left( x
\right)=\sum\limits_{i=0}^{n}{{{a}_{i}}{{x}^{i}}};{{a}_{i}}\in
Z,i=\overline{0,n}$ và một số nguyên tố p. Nếu tồn tại $n+1$ số nguyên dương ${{\alpha
}_{i}},i=\overline{0,n}$ không đồng dư từng cặp theo modulo p sao cho $P\left(
{{\alpha }_{i}} \right)\equiv 0\left( \bmod \,p \right);i=\overline{0,n}$ thì ${{a}_{i}}\equiv
0\left( \bmod \,p \right),i=\overline{0,n}$.
Chứng minh
Với $n=1$, ta có $P\left( x \right)={{a}_{0}}+{{a}_{1}}x$.
Giả sử ${{\alpha }_{0}},{{\alpha }_{1}}$ là hai số nguyên không đồng dư theo
modulo $p$ sao cho $P\left( {{\alpha
}_{0}} \right)={{a}_{0}}+{{\alpha }_{0}}{{a}_{1}}\equiv 0\left( \bmod \,p
\right)$ và $P\left( {{\alpha }_{1}} \right)={{a}_{0}}+{{\alpha
}_{1}}{{a}_{1}}\equiv 0\left( \bmod \,p \right)$. Khi đó,
$P\left( {{\alpha }_{1}} \right)-P\left( {{\alpha }_{0}}
\right)={{a}_{1}}\left( {{\alpha }_{1}}-{{\alpha }_{0}} \right)\equiv 0\left(
\bmod \,p \right)\Rightarrow {{a}_{1}}\equiv 0\left( \bmod \,p \right)$
Từ đây ta suy ra ${{a}_{0}}\equiv 0\left( \bmod \,p \right)$, định lý đúng với $n=1$.
Giả sử định lý đúng với $n=k$, ta sẽ chứng minh định lý đúng
với $n=k+1$.
Ta có $P\left( x \right)-P\left( {{\alpha }_{0}}
\right)=\left( x-{{\alpha }_{0}} \right)G\left( x \right)$ với $G\left( x
\right)=\sum\limits_{i=0}^{k}{{{b}_{i}}{{x}^{i}}};{{b}_{i}}\in Z$. Vì $P\left(
{{\alpha }_{i}} \right)\equiv 0\left( \bmod \,p \right),i=\overline{0,k+1}$ nên
$\left( {{\alpha }_{i}}-{{\alpha }_{0}} \right)G\left( {{\alpha }_{i}}
\right)\equiv 0\left( \bmod \,p \right);i=\overline{1,k+1}$, suy ra $G\left(
{{\alpha }_{i}} \right)\equiv 0\left( \bmod \,p \right);i=\overline{1,k+1}$.
Vì $\deg G\left( x \right)=k$ và $G\left( {{\alpha }_{i}}
\right)\equiv 0\left( \bmod \,p \right);i=\overline{1,k+1}$ nên theo giả thiết
qui nạp ta được ${{b}_{i}}\equiv 0\left( \bmod \,p \right);i=\overline{1,k+1}$.
Do đó ${{a}_{i}}\equiv 0\left( \bmod \,p \right);i=\overline{0,k+1}$.
Theo nguyên lý qui nạp, định lý đã được chứng minh.
Hệ quả. Giả sử $P\left( x \right)=\sum\limits_{i=0}^{n}{{{a}_{i}}{{x}^{i}}};{{a}_{i}}\in
Z,i=\overline{0,n-1},{{a}_{n}}=1$ và $p$ là một số nguyên tố. Khi đó, đa thức $P\left(
x \right)$ có nhiều nhất $n$ nghiệm modulo $p$ không đồng dư từng cặp.
Chứng minh
Giả sử $P\left( x \right)$ có nhiều hơn $n$ nghiệm modulo $p$
không đồng dư từng cặp. Khi đó, theo Định lý Lagrange ta có ${{a}_{i}}\equiv
0\left( \bmod \,p \right);i=\overline{0,n}$, suy ra ${{a}_{n}}=1\equiv 0\left(
\bmod p \right)$ (vô lý). Vậy $P\left( x \right)$ có nhiều nhất $n$ nghiệm
modulo $p$ không đồng dư từng cặp.
Định lý 3. Giả sử $p$ là số nguyên tố và $d$ là ước của $p-1$. Khi đó, đa thức ${{x}^{d}}-1$
có đúng $d$ nghiệm modulo $p$ không đồng
dư từng cặp.
Chứng minh
Vì $d|\left( p-1 \right)$ nên ${{x}^{p-1}}-1=\left(
{{x}^{d}}-1 \right)Q\left( x \right)$, trong đó $Q\left( x \right)$ là đa thức
có hệ số nguyên, $\deg Q\left( x \right)=p-1-d$ và hệ số bậc cao nhất là 1.
Áp dụng Định lý Fermat nhỏ, đa thức ${{x}^{p-1}}-1$ có đúng $p-1$
nghiệm modulo $p$ không đồng dư từng cặp. Mặt khác, mỗi nghiệm đó phải là nghiệm
của ${{x}^{d}}-1$ hoặc $Q\left( x \right)$.
Theo Hệ quả, đa thức $Q\left( x \right)$ có không quá $p-1-d$
nghiệm modulo $p$ không đồng dư từng cặp. Ta suy ra đa thức ${{x}^{d}}-1$ có ít
nhất $d$ nghiệm modulo $p$ không đồng dư từng cặp.
Mặt khác, theo Định lý Lagrange, đa thức ${{x}^{d}}-1$ có
nhiều nhất $d$ nghiệm modulo $p$ không đồng dư từng cặp. Vậy, đa thức ${{x}^{d}}-1$
có đúng $d$ nghiệm modulo $p$ không đồng dư từng cặp.
Định lý 4. Giả sử $p$ là số nguyên tố và $d|\left( p-1
\right)$. Khi đó, số các số nguyên dương bậc $d$ , không đồng dư từng cặp theo
modulo $p$ là $\varphi \left( d \right)$.
Chứng minh
Gọi $N\left( d \right)$ là số các số nguyên dương bậc $d$
theo modulo $p$ và không vượt quá $p-1$. Vì $\varphi \left( p \right)=p-1$ nên $d|\left(
p-1 \right)$. Theo Định lý nhỏ Fermat, đa thức ${{x}^{p-1}}-1$ có $p-1$ nghiệm
modulo $p$ và không vượt quá $p-1$. Do đó,
$p-1=\sum\limits_{d|p-1}{N\left(
d \right)}$ (1)
Mặt khác, theo kết quả bài viết trước ta có
$p-1=\sum\limits_{d|p-1}{\varphi
\left( d \right)}$(2)
Tiếp theo ta cần chứng tỏ $N\left(
d \right)\le \varphi \left( d \right);\forall d|\left( p-1 \right)$ từ đó suy ra
$N\left( d \right)=\varphi \left( d \right);\forall d|\left( p-1 \right)$.
Nếu $N\left( d \right)=0$, hiển nhiên $N\left( d \right)\le
\varphi \left( d \right)$.
Nếu $N\left( d \right)\ne 0$, tồn tại số nguyên dương $a\le
p-1$ có bậc $d$ theo modulo $p$. Khi đó, các số nguyên $a,{{a}^{2}},\ldots
,{{a}^{d}}$ không đồng dư từng cặp theo modulo $p$ và là nghiệm của đa thức ${{x}^{d}}-1$
theo modulo $p$.
Theo Định lý 3, đa thức ${{x}^{d}}-1$ có đúng $d$ nghiệm
không đồng dư từng cặp theo modulo $p$ nên mọi phần tử tùy ý bậc $d$ phải đồng
dư với ${{a}^{j}}$ với $j\in \left\{ 1,2,\ldots ,d \right\}$. Hơn nữa, ${{a}^{j}}$
có bậc là $d$ khi và chỉ khi $\left( j,d \right)=1$, số lượng các số $j$ như thế
là $\varphi \left( d \right)$. Như vậy, ta đã xây dựng một đơn ánh từ tập các số
nguyên dương bậc $d$ theo modulo $p$ và không vượt quá $p-1$ đến tập các số $j$
nguyên tố cùng nhau với $d$ và bé hơn $d$. Do đó, $N\left( d \right)\le \varphi
\left( d \right)$.
Từ Định lý 4, cho $d=p-1$ ta được hệ quả:
Hệ quả. Mọi số nguyên tố đều có căn nguyên thủy. Hơn
nữa, số căn nguyên thủy không đồng dư từng cặp theo modulo p là $\varphi \left(
p-1 \right)$.
Định lý 5. Nếu $p$ là một số nguyên tố lẻ với căn
nguyên thủy là $a$, thì hoặc $a$, hoặc $a+p$ là căn nguyên thủy theo modulo ${{p}^{2}}$.
Chứng minh
Vì $a$ là căn
nguyên thủy theo modulo $p$ nên $or{{d}_{p}}a=\varphi
\left( p \right)=p-1$.
Giả sử $or{{d}_{{{p}^{2}}}}a=m$, suy ra
${{a}^{m}}\equiv
1\left( \bmod {{p}^{2}} \right)\Rightarrow {{a}^{m}}\equiv 1\left( \bmod p
\right)$
Do đó $\left( p-1 \right)|m$. Mặt khác, $\varphi \left(
{{p}^{2}} \right)=p\left( p-1 \right)$ nên $m|p\left( p-1 \right)$.
Ta thấy $\left( p-1 \right)$ là ước của $m$ và $m$ là ước của
$p\left( p-1 \right)$ nên $m=p-1$ hoặc $m=p\left( p-1 \right)$.
Nếu $m=p\left( p-1 \right)=\varphi \left( {{p}^{2}} \right)$
thì $a$ là căn nguyên thủy theo modulo ${{p}^{2}}$.
Nếu $m=p-1$, ta sẽ chứng minh $a+p$ là căn nguyên thủy theo
modulo ${{p}^{2}}$.
Đặt $or{{d}_{{{p}^{2}}}}\left( a+p \right)=n$. Ta thấy $a+p$
đồng dư với $a$ theo modulo $p$ nên $a+p$ cũng là căn nguyên thủy theo modulo $p$,
suy ra $n=p-1$ hoặc $n=p\left( p-1 \right)$. Ta sẽ chứng tỏ $n=p-1$ là không thể
xảy ra. Thật vậy, ta có
${{\left( a+p
\right)}^{p-1}}-1=\sum\limits_{k=0}^{p-1}{C_{p-1}^{k}{{a}^{p-1-k}}{{p}^{k}}}-1$
$=\left(
{{a}^{p-1}}-1 \right)+p\left( p-1 \right){{a}^{p-2}}+\upsilon {{p}^{2}}$ (1)
Mặt khác, ${{a}^{p-1}}\equiv 1\left( \bmod {{p}^{2}}
\right)$ nên từ (1) ta suy ra ${{\left( a+p \right)}^{p-1}}-1$ không chia hết
cho ${{p}^{2}}$, suy ra $n=p\left( p-1 \right)=\varphi \left( {{p}^{2}}
\right)$. Vậy $a+p$ là căn nguyên thủy theo modulo ${{p}^{2}}$.
Định lý 6. Nếu $p$ là một số nguyên tố lẻ thì ${{p}^{k}}$
có căn nguyên thủy với mọi $k\in {{Z}_{>0}}$. Hơn nữa, nếu $a$ là căn nguyên
thủy theo modulo ${{p}^{2}}$ thì $a$ là căn nguyên thủy theo modulo ${{p}^{k}}$.
Chứng minh
Theo Định lý 5, $p$ có căn nguyên thủy $a$ sao cho $a$ cũng
là căn nguyên thủy theo modulo ${{p}^{2}}$.
Đặt $or{{d}_{{{p}^{k}}}}a=m$, suy ra
${{a}^{m}}\equiv
1\left( \bmod {{p}^{k}} \right)\Rightarrow {{a}^{m}}\equiv 1\left( \bmod p
\right)$ (2)
Vì $p$ có căn nguyên thủy $a$ nên từ (2) ta suy ra được $\left(
p-1 \right)|m$.
Mặt khác, $\varphi \left( {{p}^{k}}
\right)={{p}^{k-1}}\left( p-1 \right)$ nên $m|{{p}^{k-1}}\left( p-1 \right)$.
Ta thấy $p-1$ là ước của $m$ và $m$ là ước của ${{p}^{k-1}}\left( p-1 \right)$ nên $m={{p}^{h}}\left(
p-1 \right)$ với $0\le h\le k-1$. Ta sẽ
chứng minh $m$ không thể có dạng $m={{p}^{h}}\left( p-1 \right)$ với $0\le h\le
k-2$. Trước hết, ta sẽ chứng minh ${{a}^{{{p}^{k-2}}\left( p-1 \right)}}-1$
không chia chết cho ${{p}^{k}}$ với $k\ge 2$.
Với $k=2$, ta có ${{a}^{p-1}}-1$ không chia hết cho ${{p}^{2}}$
vì $a$ là căn nguyên thủy của ${{p}^{2}}$.
Giả sử khẳng định đúng với
$k=n$, tức ${{a}^{{{p}^{n-2}}\left( p-1 \right)}}-1$ không chia chết cho
${{p}^{n}}$. Ta cần chứng minh ${{a}^{{{p}^{n-1}}\left( p-1 \right)}}-1$ không
chia chết cho ${{p}^{n+1}}$.
Đặt $s={{a}^{{{p}^{n-2}}\left( p-1 \right)}}-1$. Vì $\varphi
\left( {{p}^{n-1}} \right)={{p}^{n-2}}\left( p-1 \right)$ nên ${{a}^{{{p}^{n-2}}\left(
p-1 \right)}}-1$ chia hết cho ${{p}^{n-1}}$. Ta suy ra $s=r{{p}^{n-1}}$ với $\left( r,p \right)=1$. Khi đó,
${{a}^{{{p}^{n-1}}\left(
p-1 \right)}}={{\left( s+1 \right)}^{p}}={{\left( r{{p}^{n-1}}+1
\right)}^{p}}=r{{p}^{n}}+\upsilon {{p}^{n+1}}+1$.
Rõ ràng ${{a}^{{{p}^{n-1}}\left( p-1 \right)}}-1$ không chia
chết cho ${{p}^{n+1}}$.
Vậy, ta đã khẳng định được ${{a}^{{{p}^{k-2}}\left( p-1
\right)}}-1$ không chia chết cho ${{p}^{k}}$ với $k\ge 2$.
Vì ${{a}^{{{p}^{k-2}}\left( p-1 \right)}}-1$ không chia chết
cho ${{p}^{k}}$ nên ${{a}^{{{p}^{h}}\left( p-1 \right)}}-1$ không chia chết cho
${{p}^{k}}$ với $0\le h\le k-2$. Do đó, $m={{p}^{k-1}}\left( p-1 \right)=\varphi
\left( {{p}^{k}} \right)$, suy ra $a$ là căn nguyên thủy theo modulo ${{p}^{k}}$.
Không có nhận xét nào:
Đăng nhận xét