Căn nguyên thủy và ứng dụng

Giới thiệu

Chúng ta đã thấy rằng với bất kỳ số nguyên dương \( n \) và bất kỳ số nguyên \( a \) nguyên tố cùng nhau với \( n \), cấp modulo \( n \) của \( a \) là ước của \( \varphi(n) \) và đặc biệt nó không thể vượt quá \( \varphi(n) \). Trong phần này, chúng ta quan tâm đến việc đặc trưng hóa những số \( n \) mà đạt được giới hạn này, tức là những số \( n \) mà tồn tại \( a \) sao cho \( \gcd(a,n) = 1 \) và \( \text{ord}_n(a) = \varphi(n) \). Hãy đặt tên cho những số \( a \) như vậy.

Định nghĩa

Cho \( n \) là một số nguyên dương. Một số nguyên \( a \) được gọi là căn nguyên thủy modulo \( n \) nếu \(\gcd(a, n) = 1\) và \(\operatorname{ord}_n(a) = \varphi(n)\).

Ví dụ

\(1\) là căn nguyên thủy mod \(2\), \(2\) là căn nguyên thủy mod \(3\), \(3\) là căn nguyên thủy mod \(4\), \(2\) và \(3\) là căn nguyên thủy mod \(5\), \(5\) là căn nguyên thủy mod \(6\), ...

Tính chất

Tính chất 1

Nếu \( a \) là một căn nguyên thủy modulo \( n \) và nếu \( b \equiv a \pmod{n} \), thì \( b \) cũng là một căn nguyên thủy modulo \( n \).

Tính chất 2

Nếu \( a \) là một căn nguyên thủy modulo \( n \) thì \( \{1, a, a^2, ..., a^{\varphi(n)-1} \}\) là một hệ thặng dư thu gọn modulo \( n \).

Hệ quả

Nếu \( a \) là một căn nguyên thủy modulo \( n \) thì với mọi số nguyên \( x \) nguyên tố cùng nhau với \( n \), tồn tại một số nguyên dương \( k \) sao cho \( x \equiv a^k \pmod{n} \).

Tính chất 3

Nếu \(a\) là căn nguyên thủy mod \(n\) thì \(b\) là căn nguyên thủy mod \(n\) khi và chỉ khi \(b \equiv a^k\) với \(\gcd(k, \varphi(n)) = 1\).

Tính chất 4

Cho \(p\) là số nguyên tố lẻ và \(a\) là căn nguyên thủy mod \(p\). Khi đó nếu \(a\) là căn nguyên thủy mod \(p^2\) thì \(a\) là căn nguyên thủy mod \(p^n\) với mọi \(n\).

Tính chất 5

Mọi số nguyên tố \(p\) đều có căn nguyên thủy.

Bổ đề

Cho \( p \) là một số nguyên tố lẻ. Khi đó, với mọi ước số dương \( d \) của \( \varphi(p) = p - 1 \), có đúng \( \varphi(d) \) số \( n \in \{1, 2, ..., p - 1\} \) sao cho \( \operatorname{ord}_p(n) = d \).

Hệ quả

Có đúng \( \varphi(p - 1) \geq 1 \) căn nguyên thủy modulo \( p \).

Tính chất 6

(Định lý Gauss) Một số nguyên dương \(n\) có căn nguyên thủy khi và chỉ khi \(n = 1, 2, 4, p^k, 2p^k\) với \(p\) là số nguyên tố lẻ và \(k\) nguyên dương.

Ứng dụng

Bài toán 1

Cho số nguyên tố \( p \). Tìm tất cả các số nguyên dương \( k \) sao cho \[S_k = 1^k + 2^k + \ldots + (p-1)^k\] chia hết cho \( p \).

Chứng minh

Do \( p \) nguyên tố nên tồn tại \( x \) là căn nguyên thủy mod \( p \). Khi đó \[S_k \equiv 1 + x^k + \ldots + x^{(p-2)k} \pmod{p} \] Nếu \( (p-1) \mid k \) thì \[S_k \equiv 1 + 1 + \ldots + 1 \equiv p - 1 \pmod{p}\] Nếu \( (p-1) \nmid k \) thì từ \[x^k \not \equiv 1 \pmod{p}\] và \[x^{(p-1)k} \equiv 1 \pmod{p}\] ta suy ra \[S_k \equiv \frac{x^{(p-1)k} - 1}{x^k - 1} \equiv 0 \pmod{p}\] Vậy các số \( k \) cần tìm là tất cả các số không chia hết cho \( p-1 \).

Bài toán 2

Cho \(p > 10\) là một số nguyên tố. Chứng minh rằng tồn tại các số nguyên dương \(m, n\) với \(p>m+n\) sao cho \(p\) là ước của \(5^m7^n - 1\).

Chứng minh

Gọi \(g\) là một căn nguyên thủy modulo \(p\). Giả sử \(5 \equiv g^a \pmod{p}\) và \(7 \equiv g^b \pmod{p}\), trong đó \(p-1>a,b\) (lưu ý rằng \((5, p) = (7, p) = 1\) và \(a, b \neq p-1\)). Khi đó, ta có: \[ 5^b \equiv 7^a \pmod{p}. \] Nếu \(b>a\), chọn \((m, n) = (p-1-b, a)\). Ngược lại, nếu \(a > b\), chọn \((m, n) = (b, p-1-a)\). Dễ dàng kiểm tra rằng các giá trị này thỏa mãn bài toán.

Bài toán 3

Tìm tất cả các số nguyên tố \( p, q \) sao cho: \[ \alpha^{3pq} - \alpha \equiv 0 \pmod{3pq} \] với mọi số nguyên \( \alpha \).

Chứng minh

Đầu tiên, ta nhận thấy rằng \( 3, p, q \) là các số nguyên tố phân biệt. Thật vậy, giả sử \( p = q \). Khi đó: \[ n^{3p^2} \equiv n \pmod{p^2}, \forall n \in \mathbb{Z^+} \] Tuy nhiên, nếu \( n = p \), ta có: \[ p^{3p^2} \equiv p \pmod{p^2} \implies p^{3p^2 - 1} \equiv 1 \pmod{p} \implies 0 \equiv 1 \pmod{p} \] điều này vô lý.

Bây giờ, gọi \( g_1, g_2 \) lần lượt là các căn nguyên thủy modulo \( p \) và \( q \). Khi đó: \[ g_1^{3qp} \equiv g_1 \pmod{p} \implies p - 1 \mid 3pq - 1 \] Tương tự: \[ q - 1 \mid 3pq - 1 \] Do đó, ta có: \[ p - 1 \mid 3q - 1 \] và \[ q - 1 \mid 3p - 1 \]

Đặt \( 3q - 1 = x(p - 1) \) và \( 3p - 1 = y(q - 1) \) với \( x, y \in \mathbb{N} \). Giả sử \(p > q\). Ta nhận thấy rằng \( 1 \leq x \leq 3 \).

Nếu \( x = 1 \), ta có: \[ 3q - 1 = p - 1 \implies 3q = p \] điều này vô lý.

Nếu \( x = 3 \), ta có: \[ 3q - 1 = 3p - 3 \] Xét modulo 3, ta được: \[ 2 \equiv 0 \pmod{3} \] điều này cũng vô lý.

Do đó, \( x = 2 \). Khi đó: \[ 3q - 1 = 2p - 2 \] và \[ 3p - 1 = y(q - 1) \] Giải hệ phương trình này để tìm \( q \), ta được: \[ q = \frac{2y + 1}{2y - 9} \] Ta có: \[ \frac{2y + 1}{2y - 9} = 1 + \frac{10}{2y - 9} \] Do đó, \( y = 5 \) hoặc \( y = 7 \).

Nếu \( y = 5 \), thì \( q = 11 \) và \( p = 17 \).

Nếu \( y = 7 \), thì \( q = 3 \) và \( p = 5 \).

Tuy nhiên, \( 3, p, q \) phải là các số nguyên tố phân biệt, nên chỉ có thể có: \[ \boxed{(p, q) = (11, 17)} \] là nghiệm duy nhất.

Bài toán 4

Giả sử rằng \(p > 3\) là một số nguyên tố. Chứng minh rằng tích các căn nguyên thủy của \(p\) nằm trong khoảng từ \(1\) đến \(p\) là đồng dư với \(1\) theo modulo \(p\).

Chứng minh

Gọi \(g\) là một căn nguyên thủy của \(p\). Khi đó, các căn nguyên thủy của \(p\) là các số \(g^k\) với \(k\) nguyên dương thỏa mãn \(\gcd(k, \phi(p)) = 1\), trong đó \(\phi(p) = p-1\) là hàm Euler.

Tổng quát, số lượng các căn nguyên thủy của \(p\) là \(\phi(\phi(p)) = \phi(p-1)\).

Các căn nguyên thủy tạo thành một tập con trong nhóm nhân modulo \(p\). Ta có thể nhóm các căn nguyên thủy thành các cặp đối xứng \((g^k, g^{p-1-k})\), vì \(g^{p-1-k}\) cũng là một căn nguyên thủy.

Tích của mỗi cặp đối xứng là: \[ g^k \cdot g^{p-1-k} = g^{p-1}. \] Vì \(g^{p-1} \equiv 1 \pmod{p}\) theo Định lý Fermat nhỏ, nên tích của mỗi cặp là đồng dư với \(1\) modulo \(p\).

Cuối cùng, tích của tất cả các căn nguyên thủy của \(p\) là tích của các tích trong các cặp, tức là: \[ \prod_{\text{các căn nguyên thủy}} g^k \equiv 1 \pmod{p}. \]

Do đó, ta đã chứng minh được rằng tích các căn nguyên thủy của \(p\) nằm trong khoảng từ \(1\) đến \(p\) là đồng dư với \(1\) theo modulo \(p\), đpcm. \(\blacksquare\)

Bài toán 5

(Bulgaria 2017) Cho \( p \) và \( q \) là các số nguyên tố lẻ sao cho \( q > p \). Đặt \( A_k = k^{p-1} + k^{p-2} + \cdots + k + 1 \) với \( k \in \{1, 2, \ldots, q-1\} \). Xác định tất cả các số dư có thể có khi tích \( A_1A_2\cdots A_{q-1} \) được chia cho \( q \).

Chứng minh

Gọi \( g \) là một căn nguyên thủy modulo \( q \). Khi đó, tích \( A_1 \cdots A_{q-1} \) có thể được viết lại như sau: \[ A_1 \cdots A_{q-1} = p \prod_{k=1}^{q-2} \frac{g^{pk} - 1}{g^k - 1} = p \frac{\prod_{k=1}^{q-2} (g^{pk} - 1)}{\prod_{k=1}^{q-2} (g^k - 1)} \]

- Nếu \( \gcd(p, q-1) = 1 \), thì hai tích \( \prod_{k=1}^{q-2} (g^{pk} - 1) \) và \( \prod_{k=1}^{q-2} (g^k - 1) \) bằng nhau và khác \(0\) theo mod \(q\). Do đó, kết quả cuối cùng là \( p \).

- Nếu \( p \mid q-1 \), thì \( g^{p \cdot \frac{q-1}{p}} - 1 \equiv 0 \pmod{q} \), dẫn đến tích bằng \(0\) theo mod \(q\).

Vậy, kết quả cuối cùng là:

• \( p \) nếu \( p \nmid q-1 \),
• \( 0 \) nếu \( p \mid q-1 \).

Bài toán 6

Cho \( m, n \) là các số nguyên dương. Chứng minh rằng tồn tại một số nguyên dương \( k \) sao cho: \[ 2^k \equiv 1999 \pmod{3^m}\quad \text{và}\quad 2^k \equiv 2009 \pmod{5^n} \]

Chứng minh

Sử dụng tính chất 4, ta dễ dàng suy ra rằng 2 là một căn nguyên thủy modulo \( 3^m \) và modulo \( 5^n \). Do đó, tồn tại các số nguyên dương \( k_1, k_2 \) sao cho: \[ 2^{k_1} \equiv 1999 \pmod{3^m} \] và \[ 2^{k_2} \equiv 2009 \pmod{5^n} \] Xét các đồng dư này theo modulo 3 và 5, ta suy ra rằng \( k_1 \) và \( k_2 \) đều là số chẵn. Định lý số dư Trung Hoa đảm bảo sự tồn tại của một số nguyên dương \( a \) sao cho: \[ a \equiv \frac{k_1}{2} \pmod{3^{m-1}} \] và \[ a \equiv \frac{k_2}{2} \pmod{2 \cdot 5^{n-1}} \] Đặt \( k = 2a \) và sử dụng định lý Euler, ta thu được: \[ 2^k \equiv 1999 \pmod{3^m} \] và \[ 2^k \equiv 2009 \pmod{5^n} \] như mong muốn.

Bài toán 7

(Iran 2012) Cho \( p \) là một số nguyên tố lẻ. Chứng minh rằng tồn tại một số nguyên dương \( x \) sao cho \( x \) và \( 4x \) đều là các căn nguyên thủy modulo \( p \).

Chứng minh

Chọn một căn nguyên thủy \( g \) modulo \( p \) và viết \( 2 \equiv g^k \pmod{p} \) với một số nguyên dương \( k \) nào đó. Nếu chúng ta có thể tìm được một số nguyên dương \( a \) sao cho \( a \) và \( a + 2k \) đều nguyên tố cùng nhau với \( p - 1 \), thì \( x = g^a \) và \( 4x \equiv g^{a+2k} \pmod{p} \) sẽ là các căn nguyên thủy modulo \( p \) và chúng ta đã hoàn thành. Gọi \( q_1, ..., q_s \) là các ước nguyên tố của \( p - 1 \), với \( q_1 = 2 \). Nếu \( i > 1 \) thì \( q_i > 2 \), do đó tồn tại \( a_i \in \{0, 1, ..., q_i - 1\} \) khác 0 và \(-2k \pmod{q_i} \). Đặt \( a_1 = 1 \). Theo định lý số dư Trung Hoa, chúng ta có thể chọn một số nguyên \( a \) sao cho \( a \equiv a_i \pmod{q_i} \) với mọi \( 1 \leq i \leq s \). Khi đó, theo cách xây dựng, \( a \) và \( a + 2k \) không chia hết cho \( q_i \) với bất kỳ \( i \) nào, do đó chúng nguyên tố cùng nhau với \( p - 1 \). Kết quả được suy ra.

Bài toán 8

Cho \( a \) là một số nguyên dương lẻ và \( b \) là một số nguyên dương chẵn. Biết rằng \( \gcd(a, 2^b - 1) = 1 \). Chứng minh rằng:

\[ a \mid 1^b + 2^b + \ldots + a^b \]

Chứng minh

Bước 1. Nếu \( a = p^k \) với \( p \) là một số nguyên tố lẻ và \( k \) là một số nguyên dương, thì kết luận đúng.

Chứng minh. Quy nạp theo \( k \).

• Trường hợp \( k = 1 \):

Gọi \( g \) là căn nguyên thủy modulo \( p \). Khi đó:

\[ 1^b + 2^b + \cdots + (p-1)^b + p^b \equiv g^b + g^{2b} + \cdots + g^{(p-1)b} \]

\[ = \frac{g^b(g^{(p-1)b} - 1)}{g^b - 1} \]

Tử số là bội của \( p \). Nếu \( p \) chia hết mẫu số, thì:

\[ p \mid g^b - 1 \Rightarrow p-1 \mid b \Rightarrow p \mid 2^b - 1 \]

Điều này mâu thuẫn, do đó:

\[ \frac{g^b(g^{(p-1)b} - 1)}{g^b - 1} \equiv 0 \pmod{p} \]

• Giả sử kết luận đúng với \( k-1 \):

Tổng \( 1^b + 2^b + \cdots + (p^k)^b \) chia thành hai phần: các số là bội của \( p \) và các số khác.

Gọi \( g \) là căn nguyên thủy modulo \( p^k \). Khi đó, tổng phần thứ hai:

\[ \equiv g^b + g^{2b} + \cdots + g^{\phi(p^k)b} \equiv \frac{g^b(g^{\phi(p^k)b} - 1)}{g^b - 1} \]

Theo logic tương tự, biểu thức này bằng \( 0 \) modulo \( p^k \).

Phần thứ nhất:

\[ p^b(1^b + 2^b + \cdots + p^{(k-1)b}) \]

Theo trường hợp \( k-1 \), phần này là bội của \( p^b \times p^{k-1} \), nên tổng là bội của \( p^k \).

Bước 2. Kết luận đúng với mọi số lẻ \( a \).

Chứng minh.

• \( a = 1 \): Hiển nhiên.
• \( a > 1 \): Giả sử \( a = p_1^{e_1} p_2^{e_2} \cdots p_t^{e_t} \).

Với mọi \( i \), ta có:

\[ p_i^{e_i} \mid 1^b + 2^b + \cdots + p_i^{e_i b} \Rightarrow p_i^{e_i} \mid 1^b + 2^b + \cdots + a^b \]

(vì \( p_i^{e_i} \mid a \)).

Do các \( p_i^{e_i} \) nguyên tố cùng nhau, ta có:

\[ a \mid 1^b + 2^b + \cdots + a^b \]

Và chúng ta đã hoàn thành chứng minh.

Bài toán

Tìm tất cả số nguyên tố \(p\) sao cho tồn tại \(a,b,c\) phân biệt thỏa mãn \(a,b,c\) là căn nguyên thủy mod \(p\) nhưng \(abc\) không là căn nguyên thủy mod \(p\).

Chứng minh

Mệnh đề chỉ đúng nếu \(p\) không phải là số nguyên tố Fermat, nghĩa là \(p \neq 2^{2^n} + 1\) với bất kỳ số nguyên dương \(n\).

Đặt \(a \equiv g^x, b \equiv g^y, c \equiv g^z \pmod{p}\) với một căn nguyên thủy \(g\) và các số nguyên \(x, y, z\), ta thấy rằng mệnh đề tương đương với điều sau: Có tồn tại các số nguyên \(x, y, z\) sao cho \(\gcd(x, p-1) = \gcd(y, p-1) = \gcd(z, p-1) = 1\) và \(\gcd(x+y+z, p-1) > 1\)? Tôi khẳng định rằng điều này đúng khi và chỉ khi \(p\) không phải là số nguyên tố Fermat.

Đầu tiên, giả sử \(p\) không phải là số nguyên tố Fermat. Khi đó, tồn tại một số nguyên tố lẻ \(q\) là ước của \(p-1\). Chọn \(x \equiv 1 \pmod{q}, y \equiv 1 \pmod{q}, z \equiv -2 \pmod{q}\), và \(x, y, z \equiv 1 \pmod{\frac{p-1}{q^{\nu_q(p-1)}}}\) (chúng ta có thể làm được điều này nhờ Định lý Thặng dư Trung Hoa - CRT).

Khi đó, điều kiện về \(\gcd\) được thỏa mãn, nhưng \(x+y+z \equiv 0 \pmod{q}\), nên \(q \mid \gcd(x+y+z, p-1)\), dẫn đến \(\gcd(x+y+z, p-1) > 1\). Do đó, điều này khả thi khi \(p\) không phải là số nguyên tố Fermat.

Ngược lại, nếu \(p\) là số nguyên tố Fermat, thì \(p-1 = 2^{2^n}\), và điều kiện \(\gcd\) tương đương với \(x, y, z\) là các số lẻ. Khi đó, \(x+y+z\) cũng là số lẻ, nên ta có \(\gcd(x+y+z, p-1) = 1\). Do đó, điều này không khả thi khi \(p\) là số nguyên tố Fermat.

Vì vậy, chúng ta đã đặc trưng hóa tất cả các giá trị \(p\) thỏa mãn đề bài, đpcm. \(\blacksquare\)

Định lý

Nếu \(p\) là một số nguyên tố lớn hơn \(3\) và \(\Phi(p-1)/(p-1) > 1/3\), trong đó \(\Phi\) là hàm phi Euler, thì \(p\) có các căn nguyên thủy liên tiếp.

Bổ đề

Nếu \(p\) là một số nguyên tố lớn hơn \(3\), thì có đúng một nửa số căn nguyên thủy theo modulo \(p\) sao cho số liền sau không là thặng dư toàn phương.

Chứng minh bổ đề

Gọi \(\xi\) là một căn nguyên thủy theo modulo \(p\). Khi đó, \(p-1\) và \(p-2\) là hai số nguyên tố cùng nhau, do đó \(\xi^{p-2}\) cũng là một căn nguyên thủy theo modulo \(p\).

Hơn nữa, \(\xi \not\equiv \xi^{p-2} \pmod{p}\) vì \(p > 3\). Vì \(\xi\) không là một thặng dư toàn phương nên từ đồng dư thức: \[ \xi (\xi^{p-2} + 1) = \xi^{p-1} + \xi \equiv \xi + 1 \pmod{p}, \] ta suy ra rằng \(\xi + 1\) không là một thặng dư toàn phương nếu và chỉ nếu \(\xi^{p-2} + 1\) là một thặng dư toàn phương.

Do đó, đúng một trong hai số \(\xi\) và \(\xi^{p-2}\) là căn nguyên thủy sao cho số đứng liền sau không là thặng dư toàn phương. Kết luận của bổ đề được suy ra bằng cách xét tất cả các cặp căn nguyên thủy \((\xi, \xi^{p-2})\).

Chứng minh định lý

Gọi \(p\) là một số nguyên tố lớn hơn \(3\) thỏa mãn \(\Phi(p-1)/(p-1) > 1/3\). Giả sử rằng không có hai căn nguyên thủy liên tiếp theo modulo \(p\). Khi đó, theo bổ đề, một nửa trong số \(\Phi(p-1)\) căn nguyên thủy có số đứng liền sau là các thặng dư không toàn phương, và không căn nguyên thủy nào là thặng dư toàn phương.

Do mỗi căn nguyên thủy không là một thặng dư toàn phương, suy ra tồn tại ít nhất \((3/2)\Phi(p-1)\) thặng dư không toàn phương, vượt quá tổng số thặng dư không toàn phương là \((p-1)/2\) (do \(\Phi(p-1)/(p-1) > 1/3\)). Đây là một mâu thuẫn.

Do đó, định lý được chứng minh. \(\blacksquare\)