| 3 Comments | Trần Xuân Đáng
Căn nguyên thủy là một lí thuyết rất mạnh, có tính ứng dụng cao trong việc giải các bài toán số học. Trong bài viết này, tác giả xin trình bày định lỉ vể sự tồn tại căn nguyên thủy mô đun nguyên tố và một số bài toán ứng dụng của định lí đó.
Cho số nguyên \(n>1\) và số nguyên \(x\). Nếu \((x, n)=1\) thì theo định lí Euler ta có:
\[ x^{\varphi(n)} \equiv 1(\bmod n) \]
trong đó hàm Euler \(\varphi(n)\) là số các số nguyên dương nhỏ hơn \(n\), nguyên tố cùng nhau với \(n\). Nếu d là số nguyên dương nhỏ nhất sao cho \(x^{d} \equiv 1(\bmod n)\) thì ta nói \(d\) là cấp của \(x(\bmod n)\) và kí hiệu là \(d=\operatorname{or} d_{n}(x)\).
Một câu hỏi được đặt ra một cách tự nhiên là với số nguyên tố \(p\), hỏi có tồn tại hay không số nguyên \(x\) sao cho ord \(p(x)=p-1\) ? Số nguyên \(x\) như thế được gọi là căn nguyên thủy \((\bmod p)\).
Định lí Lagrange. Cho số nguyên tố p và đa thức \(f(x)\) với các hệ số nguyên, có bậc bằng \(n\left(n \in \mathbb{N}^{*}\right)\), hệ số của \(x^{n}\) không chia hết cho p. Khi đó phwơng trình \(f(x) \equiv 0(\bmod p)\) có không quá \(n\) nghiẹm \((\bmod p)\).
Định lí này được chứng minh bằng quy nạp theo n.
Hệ quả. Cho số nguyên tố p và số nguyên duơng d sao cho p-1 chia hết cho d. Khi đó phuơng trình \(x^{d}-1 \equiv 0(\bmod p)\) có đúng d nghiệm \((\bmod p)\).\\
Thật vậy, đặt \(n=\frac{p-1}{d}\) ta có \(n \in \mathbb{N}^{*}\) và \(p-1=n d\). Lại có:
\[x^{p-1}-1=\left(x^{d}-1\right)\left(x^{(n-1) d}+x^{(n-2) d}+\ldots+1\right)\]
Phương trình \(x^{p-1}-1 \equiv 0(\bmod p)\) có đúng \(p-1\) nghiệm \((\bmod p)\) (theo định lí nhỏ Fermat). Giả sử phương trình \(x^{d}-1 \equiv 0(\bmod p)\) có ít hơn \(d\) nghiệm \((\bmod p)\). Khi đó phương trình
\[\left(x^{d}-1\right)\left(x^{(n-1) d}+x^{(n-2) d}+\ldots+1\right) \equiv 0(\bmod p)\]
có it hơn \(d+(n-1) d=n d=p-1 \quad\) nghiệm \((\bmod p)\). Đó là điều vô lí.
Định lí 1. Với mỗi số nguyên tố p, tồn tại căn nguyên thủ \((\bmod p)\).
Bổ đề. Cho số nguyên tố \(p\) và các số nguyên \(a, b\) nguyên tố cùng nhau với \(p\). Giả sủ \(r_{1}\) là cáp của \(a(\bmod p), r_{2}\) là cấp của \(b(\bmod p) v a ̀ ~\left(r_{1}, r_{2}\right)=1\). Khi đó \(r_{1} r_{2}\) là cấp của ab \((\bmod p)\).
Chúng minh. Gọi \(r\) là cấp của \(a b(\bmod p)\). Ta có: \(b^{r_{1}} \equiv\left(a^{r_{1}}\right)^{r} b^{r_{1}} \equiv(a b)^{r_{1}} \equiv 1(\bmod p)\).
Suy ra \(r_{1} r_{2}\) chia hết cho \(r_{2}\). Vì \(r_{1}, r_{2}\) nguyên tố cùng nhau nên \(r\) chia hết cho \(r_{2}\).
Tương tự \(r\) chia hết cho \(r_{1}\). Vì \(r_{1}, r_{2}\) nguyên tố cùng nhau nên \(r\) chia hết cho \(r_{1} r_{2}\).
Mặt khác vì \((a b)^{m_{i}} \equiv 1(\bmod p)\) nên \(r_{1} r_{2}\) chia hết cho \(r\). Vậy \(r=r_{1} r_{2}\).
\section*{Sau đây là chúng minh định lí 1:}
Giả sử \(p\) là số nguyên tố lẻ. Khi đó \(p-1>1\). Suy ra tồn tại số nguyên dương \(k\) và \(k\) số nguyên tố \(p_{1}, p_{2}, \ldots, p_{k}\) khác nhau sao cho:
\[p-1=p_{1}^{\alpha_{1}} \cdot p_{2}^{\alpha_{2}} \ldots p_{k}^{\alpha_{k}}\]
trong đó \(\alpha_{1}, \alpha_{2}, \ldots, \alpha_{k}\) là các số nguyên dương.\\
Đặt \(m_{i}=p_{i}^{\alpha_{i}}(1 \leq i \leq k)\). Ta có \(m_{i}-\frac{m_{i}}{p_{i}} \geq 1\) và tồn tại \(m_{i}-\frac{m_{i}}{p_{i}}\) nghiệm \(\quad x_{i}\) của phương trình \(x^{m_{i}} \equiv 1(\bmod p)\) mà không là nghiệm của phương trình \(x^{\frac{m_{i}}{p_{i}}} \equiv 1(\bmod p)\). Suy ra số nguyên dương \(d\) nhỏ nhất sao cho \(x_{i}^{d}-1 \equiv 0(\bmod p)\) là \(m_{i}=p_{i}^{\alpha_{i}}\). Suy ra \(x_{i}\) có cấp là \(m_{i}=p_{i}^{\alpha_{i}}(\bmod p)\). Theo bổ đề trên thì cấp của \(x=x_{1} x_{2} \ldots x_{k}(\bmod p)\) là
\[p_{1}^{\alpha_{1}} \cdot p_{2}^{\alpha_{2}} \cdots p_{k}^{\alpha_{k}}=p-1\]
Suy ra \(x\) là căn nguyên thủy \((\bmod p)\).
Hệ quả. Cho số nguyên tố \(p\) và số nguyên \(x\) sao cho \(x\) là căn nguyên thủy \((\bmod p)\).Khi đó \(\left\{1, x, \ldots, x^{p-2}\right\}\) là hệ thặng du thu \(\operatorname{gon}(\bmod p)\).
Bài toán 1. Cho số nguyên tố \(p>2\). Tìm tất cả các số nguyên duơng \(k\) sao cho
\[S_{k}=1^{k}+2^{k}+\ldots+(p-1)^{k}\]
chia hết cho \(p\).\\
Lời giải. Giả sử \(x\) căn nguyên thủy \((\bmod p)\). Khi đó: \(S_{k} \equiv x^{k}+x^{k}+\ldots+x^{(p-2) k}(\bmod p)\).
Nếu \(k\) chia hết cho \(p-1\) thì khi đó
\[S_{k} \equiv 1+1+\ldots+1 \equiv p-1(\bmod p)\]
Nếu \(k\) không chia hết cho \(p-1\) thì \(x^{k}-1\) không chia hết cho \(p\).
Ta có \(\quad\left(x^{k}-1\right) S_{k}=x^{(p-1) k}-1 \equiv 0(\bmod p) \quad\) và \(x^{k}-1\) không chia hết cho \(p\) nên
\[S_{k} \equiv 0(\bmod p)\]
Suy ra \(\quad S_{k}\) chia hết cho \(p\). Vì vậy tất cả các số nguyên dương \(k\) thỏa mãn yêu cầu bài toán là tất cả các số nguyên dương \(k\) không chia hết cho \(p-1\).
Bài toán 2. Cho đa thúc \(P(x)\) có các hệ số nguyên, có bậc 10 và hệ số của \(x^{10}\) là 1 . Hỏi các số \(P(0), P(1), \ldots, P(100)\) có cho các số du khác nhau tùng đôi một khi chia cho 101 hay không?
Lời giải. Để giải bài toán này ta cần bổ đề sau\\
Bổ đề. Cho số nguyên tố \(p>2\) và số nguyên duơng \(k\) không chia hết cho \(p-1\). Khi đó \(1^{k}+2^{k}+\ldots+(p-1)^{k}\) chia hét cho \(p\).
Bổ đề này đã được chứng minh trong lời giải của bài toán 1. Quay trở lại bài toán 2.\\
Giả sử \(P(0), P(1), \ldots, P(100)\) cho các số dư khác nhau từng đôi một khi chia cho 101. Ta thấy rằng\\
đa thức \(P(P(x))\) có bậc 100 và \(P(P(0)), P(P(1)), \ldots, P(P(100))\) cho các số dư khác nhau từng đôi một khi chia cho 101 . Thật vậy với \(i \in\{0 ; 1 ; 2 ; \ldots ; 100\}\), tồn tại \(x_{i} \in\{0 ; 1 ; 2 ; \ldots ; 100\}\) sao cho
\[P\left(x_{i}\right) \equiv i(\bmod 101) .\]
Suy ra: \(P\left(P\left(x_{x_{i}}\right)\right) \equiv P\left(x_{i}\right) \equiv i(\bmod 101)\). Khi đó:
\[\begin{aligned}& P(P(0))+P(P(1))+\ldots+P(P(100)) \\& \quad \equiv 0+1+\ldots+100 \equiv 0(\bmod 101)\end{aligned}\]
Mặt khác ta có:
\[P(P(x))=x^{100}+a_{99} x^{99}+\ldots+a_{1} x+a_{0}\]
trong đó \(a_{0}, a_{1}, \ldots, a_{99}\) là các số nguyên.\\
Suy ra: \(P(P(0))+P(P(1))+\ldots+(P(P(100))\)
\[\begin{aligned}\equiv\left(0^{100}+1^{100}\right. & \left.+\ldots+100^{100}\right) \\& +a_{99}\left(0^{99}+1^{99}+\ldots+100^{99}\right)+\ldots \\& +a_{1}\left(0^{1}+1^{1}+\ldots+100^{1}\right)+101 a_{0}\end{aligned}\]
\(\equiv 100(\bmod 101)\)\\
(theo bổ đề và định lí nhỏ Fermat).\\
Hiển nhiên \(100 \neq 0(\bmod 101)\). Vậy
\[P(0), P(1), \ldots, P(100)\]
không thể cho các số dư khác nhau từng đôi một khi chia cho 101.
Bài toán 3 (Định lí Wilson). Chúng minh rằng nếu plà số nguyên tố thi \((p-1)!\equiv-1(\bmod p)\).
\section*{Lời giải.}
Trường hợp \(p=2\), định lí hiển nhiên đúng.\\
Giả sử \(p>2\) và \(x\) là căn nguyên thủy \((\bmod p)\).\\
Khi đó: \((p-1)!\equiv x \cdot x^{2} \ldots x^{p-1} \equiv x^{\frac{p(p-1)}{2}}(\bmod p)\).
Đặt \(w=x^{\frac{p-1}{2}}\). Khi đó \(w-1\) không chia hết cho \(p ; w^{2} \equiv 1(\bmod p)\). Suy ra \(w \equiv-1(\bmod p)\).
Suy ra \((p-1)!\equiv x^{\frac{p(p-1)}{2}} \equiv-1(\bmod p)\).\\
Bài toán 4. Cho các số nguyên không âm \(a, b\) sao cho \(2^{a} \equiv 2^{b}(\bmod 101)\). Chúng minh rằng
\[a \equiv b(\bmod 100)\]
Lời giải. Ta chứng minh rằng 2 là căn nguyên thủy \((\bmod 101)\). Thật vậy giả sử \(d\) là số nguyên dương nhỏ nhất sao \(\quad\) cho \(2^{d} \equiv 1(\bmod 101)\). Khi đó 100 chia hết cho \(d\). Ta có:
\[2^{10} \equiv 1024 \equiv 14(\bmod 101)\]
Suy ra: \(2^{20} \equiv 14^{2} \equiv-6(\bmod 101)\)
\[\Rightarrow 2^{50} \equiv 14(-6)^{2} \equiv-1(\bmod 101)\]
Giả sử \(d<100\). Khi đó 50 chia hết cho \(d\) hoặc 20 chia hết cho \(d\). Suy ra:
\[2^{50} \equiv 1(\bmod 101) \text { hoặc } 2^{20} \equiv 1(\bmod 101)\]
Đó là điều vô lí. Vậy \(d=100\).\\
Suy ra 2 là căn nguyên thủy (mod101).\\
Giả sử \(a \geq b\). Vì \(\left(2^{b}, 101\right)=1\) nên \(2^{a-b} \equiv 1(\bmod 101)\). Suy ra \(a-b\) chia hết cho 100 . Suy ra:
\[a \equiv b(\bmod 100)\]
Bài toán 5. Với mỗi số nguyên duơng \(n\), đặt \(n_{a}=101 a-100.2^{a}\). Cho các số nguyên \(a, b, c, d\) thỏa mãn \(0 \leq a, b, c, d \leq 9(a \neq b, c \neq d) \quad v a ̀ ~\) \(n_{a}+n_{b} \equiv n_{c}+n_{d}(\bmod 10100)\). Chíng minh rằng \(\{a ; b\}=\{c ; d\}\).
Lòi giải. Vì \(n_{a}+n_{b} \equiv n_{c}+n_{d}(\bmod 10100)\) nên
\[n_{a}+n_{b} \equiv n_{c}+n_{d}(\bmod 100)\]
và \(n_{a}+n_{b} \equiv n_{c}+n_{d}(\bmod 101)\).\\
Vì \(n_{a} \equiv a(\bmod 100)\) và \(n_{a} \equiv 2^{a}(\bmod 101)\)\\
nên \(a+b \equiv c+d(\bmod 100)(*)\)\\
và \(2^{a}+2^{b} \equiv 2^{c}+2^{d}(\bmod 101)\).\\
Vì \(2^{100} \equiv 1(\bmod 101)\) và \((*)\) nên
\[2^{a} 2^{b} \equiv 2^{a+b} \equiv 2^{c+d} \equiv 2^{c} 2^{d}(\bmod 101)\]
Vì \(2^{b} \equiv 2^{c}+2^{d}-2^{a}(\bmod 101)\) nên
\[2^{a}\left(2^{c}+2^{d}-2^{a}\right) \equiv 2^{c} 2^{d}(\bmod 101)\]
Suy ra: \(\left(2^{a}-2^{c}\right)\left(2^{a}-2^{d}\right) \equiv 0(\bmod 101)\). Suy ra: \(2^{a} \equiv 2^{c}(\bmod 101)\) hoặc \(\quad 2^{a} \equiv 2^{d}(\bmod 101)\). Theo bài toán 4 ta có:
\[a \equiv c(\bmod 100) \text { hoặc } a \equiv d(\bmod 100) .\]
Vì \(a+b \equiv c+d(\bmod 100)\) nên
\[\{a ; b\}=\{c ; d\} .\]
Bài toán 6. Tìm tất cả các số nguyên dương \(n>1\) sao cho \(a^{25}\)-a chia hết cho \(n\) với mọi số nguyên \(a\).
Lời giải. Giả sử \(n\) là số nguyên dương lớn hơn 1 sao cho \(a^{25}-a\) chia hết cho \(n\) với mọi số nguyên a. Giả sử \(p\) là một ước nguyên tố của \(n ; x\) là căn nguyên thủy \((\bmod p)\). Suy ra \(p-1=\operatorname{ord} p(x)\) và \((x, p)=1\). Suy ra \(x^{24}-1\) chia hết cho \(p\). Suy ra 24 chia hết cho \(p-1\). Suy ra \(p \in\{2 ; 3 ; 5 ; 7 ; 13\}\).
Với \(p \in\{2 ; 3 ; 5 ; 7 ; 13\}\), chọn \(a=p\) thì \(a^{25}-a\) không chia hết cho \(p^{2}\).
Đặt \(k=2 \cdot 3 \cdot 5 \cdot 7 \cdot 13\) ta có \(n\) là ước của \(k\). Ngược lại nếu \(n\) là ước của \(k\) thì \(a^{25}-a\) chia hết cho \(n\) với mọi số nguyên \(a\).
Bài toán 7. Với mỗi số nguyên tố lẻ p, đặt \(F(p)=\sum_{k=1}^{\frac{p-1}{2}} k^{120} v a ̀ \quad f(p)=\frac{1}{2}-\left\{\frac{F(p)}{p}\right\}\). Tìm giá trị của \(f(p)\).
Lời giải. Giả sử \(x\) là căn nguyên thủy \((\bmod p)\). Nếu 120 không chia hết cho \(p-1\) thì \(x^{120}-1\) không chia hết cho \(p\) và \(x^{120(p-1)} \equiv 1(\bmod p)\).
Ta có: \(F(p)=\frac{1}{2} \sum_{i=1}^{p-1} x^{120 i}\) và\\
\(\left(x^{120}-1\right) \sum_{i=1}^{p-1} x^{120 i}=x^{120}\left(x^{120(p-1)}-1\right) \equiv 0(\bmod p)\). Vì \(2\left(x^{120}-1\right)\) không chia hết cho \(p\) nên \(\frac{1}{2} \sum_{i=1}^{p-1} x^{120 i}\) chia hết cho \(p\). Suy ra \(F(p)\) chia hết cho \(p\). Suy ra \(f(p)=\frac{1}{2}\).\\
Nếu 120 chia hết cho \(p-1\). Khi đó:
\[p \in\{3 ; 5 ; 7 ; 11 ; 13 ; 31 ; 41 ; 61\}\]
và \(\quad x^{120} \equiv 1(\bmod p)\).\\
Suy ra: \(F(p)=\frac{1}{2} \sum_{i=1}^{p-1} x^{120 i} \equiv \frac{p-1}{2}(\bmod p)\).\\
Suy ra: \(f(p)=\frac{1}{2}-\frac{p-1}{2 p}=\frac{1}{2 p}\).\\
Bài toán 8. Tìm tất cả các cặp số nguyên tố \((p, q)\) sao cho \(a^{3 p q} \equiv a(\bmod 3 p q), \forall a \in \mathbb{Z}\).\\
Lời giải. Giả sử tồn tại các số nguyên tố \(p, q\) sao cho \(a^{3 p q} \equiv a(\bmod 3 p q), \forall a \in \mathbb{Z}\).
Giả sử \(g\) là căn nguyên thủy \((\bmod p)\). Suy ra \(g\) không chia hết cho \(p\).
Suy ra: \(g^{3 p q-1}-1 \equiv 0(\bmod p)\). Suy ra \(3 p q-1\) chia hết cho \(p-1\). Suy ra \(3(p-1) q+3 q-1\) chia hết cho \(p-1\). Suy ra \(3 q-1\) chia hết cho \(p-1\).
Tương tự: \(3 p-1\) chia hết cho \(q-1\).\\
Giả sử \(p \leq q\). Suy ra: \(3 p-1 \leq 3 q-1\).\\
Nếu \(p=2\) thì \(q=2\). Nếu \(p=3\) thì \(q=3\) hoặc \(q=5\). Giả sử \(p>3\). Khi đó \(q \geq 5\).
Suy ra: \(4(q-1)>3 q-1\). Suy ra \(3 p-1=q-1\) hoặc \(3 p-1=2(q-1)\) hoặc \(3 p-1=3(q-1)\). Các trường hợp \(3 p-1=q-1\) và \(3 p-1=3(q-1)\) không xảy ra vì \(p, q\) là các số nguyên tố.\\
Vậy \(3 p-1=2(q-1)\). Suy ra \(2 q=3 p+1\). Suy ra \(6 q-2=9 p+1\). Mặt khác \(3 q-1\) chia hết cho \(p-1\) nên \(9 p+1\) chia hết cho \(p-1\). Suy ra 10 chia hết cho \(p-1\). Suy ra \(p=11\). Suy ra \(q=17\).
Thử lại ta thấy chỉ có \((p, q)=(11,17)\) và \((p, q)=(17,11)\) thỏa mãn đề bài.
Bài toán 9 (Đề thi chọn đội tuyển Việt Nam dự thi IMO 2010).\\
Với mỗi số nguyên duơng n, xét tập hợp sau:
\[T_{n}=\left\{11(k+h)+10\left(n^{k}+n^{h} \mid 1 \leq k, h \leq 10 ; k, h \in \mathbb{N}\right\}\right.\]
Tìm tất cả các giá trị của n sao cho không tồn tai \(a, b \in T_{n}, a \neq b\) mà \(a-b\) chia hết cho 110 .
Lời giải. Giả sử \(g \in\{1 ; 2 ; \ldots ; 10\}\) sao cho \(g\) là căn nguyên thủy \((\bmod 11)\).
Giả sử \(n \in \mathbb{N}^{*}\) sao cho \(n \equiv g(\bmod 11)\). Giả sử \(a, b \in T_{n}\) sao cho \(a-b\) chia hết cho 110 . Khi đó tồn tai \(h_{1}, h_{2}, k_{1}, k_{2} \in\{1 ; 2 ; \ldots ; 10\}\) sao cho
\[a=11\left(h_{1}+k_{1}\right)+10\left(n^{h_{1}}+n^{k_{1}}\right)\]
\(b=11\left(h_{2}+k_{2}\right)+10\left(n^{k_{2}}+n^{k_{2}}\right)\) và \(a-b\) chia hết cho 110. Chúng ta chứng minh \(a=b\). Thật vậy, không mất tính tổng quát, giả sử \(h_{1} \leq h_{2}\). Ta có:
\[a \equiv b(\bmod 10) \text { và } a \equiv b(\bmod 11)\]
Suy ra: \(h_{1}+k_{1} \equiv h_{2}+k_{2}(\bmod 10)\)
\[\text { và } g^{k_{1}}+g^{k_{1}} \equiv g^{k_{2}}+g^{k_{2}}(\bmod 11)\]
Tồn tại các số tự nhiên \(p_{1}, p_{2}, r\) sao cho
\[0 \leq p_{1}, p_{2} \leq 2 ; 0 \leq r \leq 9\]
và \(\quad h_{1}+k_{1}=10 p_{1}+r, h_{2}+k_{2}=10 p_{2}+r\).\\
Ta có:
\[g^{h_{1}}+g^{10 p_{1}+r-h_{1}} \equiv g^{h_{2}}+g^{10 p_{2}+r-h_{2}}(\bmod 11)\]
Suy ra:
\[g^{h_{1}}+g^{20+r-h_{1}} \equiv g^{h_{2}}+g^{20+r-h_{2}}(\bmod 11)\]
Suy ra:
\[\left(g^{h_{2}-h_{1}}-1\right)\left(1-g^{20+r-h_{2}-h_{1}}\right) \equiv 0(\bmod 11)\]
Suy ra: \(g^{h_{2}-h_{1}} \equiv 1(\bmod 11)\)\\
hoặc \(g^{20+r-h_{1}-h_{2}} \equiv 1(\bmod 11)\).\\
Suy ra \(h_{2}-h_{1}\) chia hết cho 10 hoặc \(r-h_{2}-h_{1}\) chia hết cho 10 .
Nếu \(h_{2}-h_{1}\) chia hết cho 10 thì \(h_{1}=h_{2}\). Suy ra \(k_{1}=k_{2}\). Suy ra \(a=b\).\\
Nếu \(r-h_{2}-h_{1}\) chia hết cho 10 thì \(k_{2}-h_{1}\) chia hết cho 10 . Suy ra \(h_{1}=k_{2}\). Suy ra \(k_{1}=h_{2}\). Suy ra \(a=b\).
Nếu \(n \in \mathbb{N}^{*}\) sao cho \(n \equiv 0(\bmod 11)\). Khi đó \(n\) không thỏa mãn điều kiện đề bài.
Nếu \(n \in \mathbb{N}^{*}\) sao cho \(n \equiv 1(\bmod 11)\). Khi đó \(n\) không thỏa mãn điều kiện đề bài.
Giả sử \(c \in\{3,4,5,9\}\). Khi đó \(c^{5} \equiv 1(\bmod 11)\).\\
Chọn \(h_{1}, k_{1}, h_{2}, k_{2} \in\{1 ; 2 ; \ldots ; 10\}\) sao cho
\[h_{1}, k_{1} \in\{1 ; 2 ; 3 ; 4 ; 5\} ; h_{2} \equiv 5+h_{1} ; k_{2}=k_{1}+5 .\]
Khi đó \(h_{1}+k_{1} \equiv h_{2}+k_{2}(\bmod 10)\)\\
và \(\quad c^{h_{1}}+c^{k_{1}} \equiv c^{h_{2}}+c^{k_{2}}(\bmod 11)\).\\
Vậy nếu \(n \in \mathbb{N}^{*}\) và \(n \equiv c(\bmod 11)\) thì \(n\) không thỏa mãn điều kiện đề bài.
Nếu \(n \in \mathbb{N}^{*}\) sao cho \(n \equiv 10(\bmod 11)\). Khi đó:
\[n^{2} \equiv 1(\bmod 11) \text { và } n^{8} \equiv 1(\bmod 11)\]
Chọn \(h_{1}=1, k_{1}=2, h_{2}=3, k_{2}=10\). Khi đó:
\[h_{1}+k_{1} \equiv h_{2}+k_{2}(\bmod 10)\]
và \(10^{h_{1}}+10^{k_{1}} \equiv 10^{h_{2}}+10^{k_{2}}(\bmod 11)\).\\
Vậy nếu \(n \in \mathbb{N}^{*}\) và \(n \equiv 10(\bmod 11)\) thì \(n\) không thỏa mãn đề bài. Dễ dàng chứng minh được \(2,6,7,8\) là các căn nguyên thủy \((\bmod 11)\). Vậy số tự nhiên \(n\) thỏa mãn đề bài khi và chỉ khi \(n \equiv g(\bmod 11)\) trong đó \(g \in\{2 ; 6 ; 7 ; 8\}\).
Bài toán 10. Chúng minh rằng tồn tại một phân hoạch của tập hợp \(\{1.2, \ldots, 2010\}\) thành các tập con rời nhau sao cho mỗi tập con có 5 phà̀n tú và tổng các phần tử trong mỗi tập con chia hết cho 2011.
Lời giải. Vì 2011 là số nguyên tố nên tồn tại căn nguyên thủy \((\bmod 2011)\), tức là tồn tại số nguyên \(g\) sao cho \(g\) không chia hết cho 2011 và cấp của \(g(\bmod 2011)\) là 2010 . Khi đó \(g-1\) không chia\\
hết cho 2011 và \(1, g, \ldots, g^{2009}\) là hệ thặng dư thu gọn \((\bmod 2011)\).
Xét các tập hợp
\[\begin{aligned}& A_{1}=\left\{1, g^{402}, g^{402.2}, g^{402.3}, g^{402.4}\right\}, \\& A_{2}=\left\{g, g^{402+1}, g^{402.2+1}, g^{402.3+1}, g^{402.4+1}\right\},\end{aligned}\]
\(A_{402}=\left\{g^{401}, g^{402+401}, g^{402.2+401}, g^{402.3+401}, g^{402.4+401}\right\}\). Ta có:
\[\left(1+g^{402}+g^{402.2}+g^{402.3}+g^{402.4}\right)(g-1)=g^{2010}-1\]
Vì \(g^{2010} \equiv 1(\bmod 2011)\) và \(g-1\) không chia hết cho 2011 nên
\[1+g^{402}+g^{402.2}+g^{402.3}+g^{402.4} \equiv 0(\bmod 2011)\]
Vì \(1, g, \ldots, g^{2009}\) là hệ thặng dư thu \(\operatorname{gọn}(\bmod 2011)\) nên với mỗi số nguyên \(k\) thỏa mãn \(0 \leq k \leq 2009\) tồn tại \(a_{k} \in\{1 ; 2 ; \ldots ; 2010\}\) sao cho
\[g^{k} \equiv a_{k}(\bmod 2011)\]
Ta có \(a_{i} \neq a_{j}\) với \(i, j \in\{1 ; 2 ; \ldots ; 402\}\) và \(i \neq j\).\\
Xét các tập hợp
\[\begin{aligned}& B_{1}=\left\{1, a_{402}, a_{402.2}, a_{402.3}, a_{402.4}\right\} \\& B_{2}=\left\{a_{1}, a_{402+1}, a_{402.2+1}, a_{402.3+1}, a_{402.4+1}\right\} \\& \ldots \ldots \\& B_{402}=\left\{a_{401}, a_{402+401}, a_{402.2+401}, a_{402.3+401}, a_{402.4+401}\right\} .\end{aligned}\]
Khi đó \(\quad B_{i} \cap B_{j}=\varnothing\) với \(i, j \in\{1 ; 2 ; \ldots ; 402\}\) và\\
\(i \neq j\) đồng thời \(\bigcup_{i=1}^{402} B_{i}=\{1 ; 2 ; \ldots ; 2010\}\).\\
Vậy tồn tại một phân hoạch của tập hợp \(\{1 ; 2 ; \ldots ; 2010\}\) thành các tập con rời nhau sao cho\\
mỗi tập con có 5 phần tử và tổng các phần tử trong mỗi tập con chia hết cho 2011.
\begin{itemize} \item Cho số nguyên \(n>1\) và số nguyên \(x\) nguyên tố cùng nhau với \(n\). Một cách tương tự, chúng ta định nghĩa \(x\) là căn nguyên thủ \((\bmod n)\) khi và chỉ khi số nguyên dương \(d\) nhỏ nhất thỏa mãn\end{itemize}
\[x^{d} \equiv 1(\bmod n) \text { là } \varphi(n) \text {. }\]
Một câu hỏi được đặt ra một cách tự nhiên là với những số nguyên dương \(n\) nào thì tồn tại căn nguyên thủy \((\bmod n)\). Người ta đã chứng minh được rằng nếu số nguyên dương \(n\) có dạng \(p^{k}\) hoặc \(2 p^{k}\), trong đó \(p\) là số nguyên tố lẻ và \(k\) là số nguyên dương hoặc \(n \in\{2,4\}\) thì \(n\) có căn nguyên thủy.\\
Cuối cùng là một số bài tập dành để luyện tập.
\section*{BÀI TẬP}
Bài 1. Cho số nguyên dương \(n>1\) sao cho \(p=2^{n}+1\) là số nguyên tố. Chứng minh rằng 3 là căn nguyên thủy \((\bmod p)\).\\
Bài 2. Cho số tự nhiên \(k\) sao cho \(p=4 k+3\) là số nguyên tố. Giả sử \(g\) là một căn nguyên thủy \((\bmod p)\) thỏa mãn \(g^{2} \equiv g+1(\bmod p)\). Chứng minh rằng \(g-2\) cũng là một căn nguyên thủy \((\bmod p)\).
Bài 3. Tìm tất cả các số tự nhiên \(n\) có hai chữ số (nghĩa là \(n=10 a+b\), trong đó \(a, b \in\{0 ; 1, \ldots, 9\}\) và \(a \neq 0)\) sao cho với mọi số nguyên \(k(k \neq 0)\) ta có \(k^{a}-k^{b}\) chia hết cho \(n\).
Bài 4. Cho số nguyên tố lẻ \(p\). Tìm tất cả các hàm số \(f: \mathbb{Z} \rightarrow \mathbb{Z}\) thỏa mãn đồng thời các điều kiện sau:\\
i) nếu \(m, n \in \mathbb{Z}\) và \(m \equiv n(\bmod p)\) thì
\[f(m)=f(n)\]
ii) \(f(m n)=f(m) f(n)\) với mọi \(m, n \in \mathbb{Z}\).
Bài 5. Cho số nguyên tố lẻ \(p\) và tập hợp \(S=\left\{n_{1} ; n_{2} ; \ldots ; n_{k}\right\}\) gồm các số chính phương nguyên tố cùng nhau với \(p\). Tìm số \(k\) nhỏ nhất sao cho tồn tại một tập con \(A\) của tập hợp \(S\) mà tích các phần tử của \(A\) đồng dư với \(1(\bmod p)\).
Bài 6. Chứng minh rằng tồn tại một phân hoạch của tập hợp \(S=\left\{1^{3} ; 2^{3} ; \ldots ; 2000^{3}\right\}\) thành 25 tập hợp con sao cho tổng tất cả các phần tử của mỗi tập con chia hết cho \(2001^{2}\).
Bài 7. Cho số nguyên tố \(p>3\). Với tập con \(S\) khác rỗng bất kì của \(\mathbb{Z}\) và \(a \in \mathbb{Z}\), đặt \(S_{a}=\{x \in\{0,1,,,, p-1\} \mid \exists s \in S: x \equiv a s(\bmod p)\}\).\\
a) Tìm tất cả các giá trị của \(k \in \mathbb{N}^{*}(k \geq 2)\) sao cho tồn tại tập con \(S\) khác rỗng của tập hợp \(\{1,2, \ldots, p-1\}\) mà trong số các tập hợp \(S_{1}, S_{2}, \ldots, S_{p-1}\) có đúng \(k\) tập hợp khác nhau từng đôi một.\\
b) Hỏi có bao nhiêu tập con \(S\) khác rỗng của tập hợp \(\{1,2, \ldots, p-1\}\) mà trong số các tập hợp \(S_{1}, S_{2}, \ldots, S_{p-1}\) có đúng hai tập hợp khác nhau?\\
(Đề thi chọn đội tuyển Serbia dụ thi IMO 2013)
