Giới thiệu
Chúng ta đã thấy rằng với bất kỳ số nguyên dương và bất kỳ số nguyên nguyên tố cùng nhau với , cấp modulo của là ước của và đặc biệt nó không thể vượt quá . Trong phần này, chúng ta quan tâm đến việc đặc trưng hóa những số mà đạt được giới hạn này, tức là những số mà tồn tại sao cho và . Hãy đặt tên cho những số như vậy.
Định nghĩa
Cho là một số nguyên dương. Một số nguyên được gọi là căn nguyên thủy modulo nếu và .
Ví dụ
là căn nguyên thủy mod , là căn nguyên thủy mod , là căn nguyên thủy mod , và là căn nguyên thủy mod , là căn nguyên thủy mod , ...
Tính chất
Tính chất 1
Nếu là một căn nguyên thủy modulo và nếu , thì cũng là một căn nguyên thủy modulo .
Tính chất 2
Nếu là một căn nguyên thủy modulo thì là một hệ thặng dư thu gọn modulo .
Hệ quả
Nếu là một căn nguyên thủy modulo thì với mọi số nguyên nguyên tố cùng nhau với , tồn tại một số nguyên dương sao cho .
Tính chất 3
Nếu là căn nguyên thủy mod thì là căn nguyên thủy mod khi và chỉ khi với .
Tính chất 4
Cho là số nguyên tố lẻ và là căn nguyên thủy mod . Khi đó nếu là căn nguyên thủy mod thì là căn nguyên thủy mod với mọi .
Tính chất 5
Mọi số nguyên tố đều có căn nguyên thủy.
Bổ đề
Cho là một số nguyên tố lẻ. Khi đó, với mọi ước số dương của , có đúng số sao cho .
Hệ quả
Có đúng căn nguyên thủy modulo .
Tính chất 6
(Định lý Gauss) Một số nguyên dương có căn nguyên thủy khi và chỉ khi với là số nguyên tố lẻ và nguyên dương.
Ứng dụng
Bài toán 1
Cho số nguyên tố . Tìm tất cả các số nguyên dương sao cho
chia hết cho .
Chứng minh
Do nguyên tố nên tồn tại là căn nguyên thủy mod . Khi đó
Nếu thì
Nếu thì từ
và
ta suy ra
Vậy các số cần tìm là tất cả các số không chia hết cho .
Bài toán 2
Cho là một số nguyên tố. Chứng minh rằng tồn tại các số nguyên dương với sao cho là ước của .
Chứng minh
Gọi là một căn nguyên thủy modulo . Giả sử và , trong đó (lưu ý rằng và ). Khi đó, ta có:
Nếu , chọn . Ngược lại, nếu , chọn . 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ố sao cho:
với mọi số nguyên .
Chứng minh
Đầu tiên, ta nhận thấy rằng là các số nguyên tố phân biệt. Thật vậy, giả sử . Khi đó:
Tuy nhiên, nếu , ta có:
điều này vô lý.
Bây giờ, gọi lần lượt là các căn nguyên thủy modulo và . Khi đó:
Tương tự:
Do đó, ta có:
và
Đặt và với . Giả sử . Ta nhận thấy rằng .
Nếu , ta có:
điều này vô lý.
Nếu , ta có:
Xét modulo 3, ta được:
điều này cũng vô lý.
Do đó, . Khi đó:
và
Giải hệ phương trình này để tìm , ta được:
Ta có:
Do đó, hoặc .
Nếu , thì và .
Nếu , thì và .
Tuy nhiên, phải là các số nguyên tố phân biệt, nên chỉ có thể có:
là nghiệm duy nhất.
Bài toán 4
Giả sử rằng là một số nguyên tố. Chứng minh rằng tích các căn nguyên thủy của nằm trong khoảng từ đến là đồng dư với theo modulo .
Chứng minh
Gọi là một căn nguyên thủy của . Khi đó, các căn nguyên thủy của là các số với nguyên dương thỏa mãn , trong đó là hàm Euler.
Tổng quát, số lượng các căn nguyên thủy của là .
Các căn nguyên thủy tạo thành một tập con trong nhóm nhân modulo . Ta có thể nhóm các căn nguyên thủy thành các cặp đối xứng , vì cũng là một căn nguyên thủy.
Tích của mỗi cặp đối xứng là:
Vì theo Định lý Fermat nhỏ, nên tích của mỗi cặp là đồng dư với modulo .
Cuối cùng, tích của tất cả các căn nguyên thủy của là tích của các tích trong các cặp, tức là:
Do đó, ta đã chứng minh được rằng tích các căn nguyên thủy của nằm trong khoảng từ đến là đồng dư với theo modulo , đpcm.
Bài toán 5
(Bulgaria 2017) Cho và là các số nguyên tố lẻ sao cho . Đặt với . Xác định tất cả các số dư có thể có khi tích được chia cho .
Chứng minh
Gọi là một căn nguyên thủy modulo . Khi đó, tích có thể được viết lại như sau:
- Nếu , thì hai tích và bằng nhau và khác theo mod . Do đó, kết quả cuối cùng là .
- Nếu , thì , dẫn đến tích bằng theo mod .
Vậy, kết quả cuối cùng là:
Bài toán 6
Cho là các số nguyên dương. Chứng minh rằng tồn tại một số nguyên dương sao cho:
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 và modulo . Do đó, tồn tại các số nguyên dương sao cho:
và
Xét các đồng dư này theo modulo 3 và 5, ta suy ra rằng và đề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 sao cho:
và
Đặt và sử dụng định lý Euler, ta thu được:
và
như mong muốn.
Bài toán 7
(Iran 2012) Cho là một số nguyên tố lẻ. Chứng minh rằng tồn tại một số nguyên dương sao cho và đều là các căn nguyên thủy modulo .
Chứng minh
Chọn một căn nguyên thủy modulo và viết với một số nguyên dương nào đó. Nếu chúng ta có thể tìm được một số nguyên dương sao cho và đều nguyên tố cùng nhau với , thì và sẽ là các căn nguyên thủy modulo và chúng ta đã hoàn thành. Gọi là các ước nguyên tố của , với . Nếu thì , do đó tồn tại khác 0 và . Đặt . Theo định lý số dư Trung Hoa, chúng ta có thể chọn một số nguyên sao cho với mọi . Khi đó, theo cách xây dựng, và không chia hết cho với bất kỳ nào, do đó chúng nguyên tố cùng nhau với . Kết quả được suy ra.
Bài toán 8
Cho là một số nguyên dương lẻ và là một số nguyên dương chẵn. Biết rằng . Chứng minh rằng:
Chứng minh
Bước 1. Nếu với là một số nguyên tố lẻ và là một số nguyên dương, thì kết luận đúng.
Chứng minh. Quy nạp theo .
Gọi là căn nguyên thủy modulo . Khi đó:
Tử số là bội của . Nếu chia hết mẫu số, thì:
Điều này mâu thuẫn, do đó:
- Giả sử kết luận đúng với :
Tổng chia thành hai phần: các số là bội của và các số khác.
Gọi là căn nguyên thủy modulo . Khi đó, tổng phần thứ hai:
Theo logic tương tự, biểu thức này bằng modulo .
Phần thứ nhất:
Theo trường hợp , phần này là bội của , nên tổng là bội của .
Bước 2. Kết luận đúng với mọi số lẻ .
Chứng minh.
Với mọi , ta có:
(vì ).
Do các nguyên tố cùng nhau, ta có:
Và chúng ta đã hoàn thành chứng minh.
Bài toán
Tìm tất cả số nguyên tố sao cho tồn tại phân biệt thỏa mãn là căn nguyên thủy mod nhưng không là căn nguyên thủy mod .
Chứng minh
Mệnh đề chỉ đúng nếu không phải là số nguyên tố Fermat, nghĩa là với bất kỳ số nguyên dương .
Đặt với một căn nguyên thủy và các số nguyên , 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 sao cho và ?
Tôi khẳng định rằng điều này đúng khi và chỉ khi không phải là số nguyên tố Fermat.
Đầu tiên, giả sử không phải là số nguyên tố Fermat. Khi đó, tồn tại một số nguyên tố lẻ là ước của . Chọn
, và
(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ề được thỏa mãn, nhưng , nên , dẫn đến
. Do đó, điều này khả thi khi không phải là số nguyên tố Fermat.
Ngược lại, nếu là số nguyên tố Fermat, thì , và điều kiện tương đương với là các số lẻ. Khi đó, cũng là số lẻ, nên ta có
. Do đó, điều này không khả thi khi là số nguyên tố Fermat.
Vì vậy, chúng ta đã đặc trưng hóa tất cả các giá trị thỏa mãn đề bài, đpcm.
Định lý
Nếu là một số nguyên tố lớn hơn và , trong đó là hàm phi Euler, thì có các căn nguyên thủy liên tiếp.
Bổ đề
Nếu là một số nguyên tố lớn hơn , thì có đúng một nửa số căn nguyên thủy theo modulo sao cho số liền sau không là thặng dư toàn phương.
Chứng minh bổ đề
Gọi là một căn nguyên thủy theo modulo . Khi đó, và là hai số nguyên tố cùng nhau, do đó cũng là một căn nguyên thủy theo modulo .
Hơn nữa, vì . Vì không là một thặng dư toàn phương nên từ đồng dư thức:
ta suy ra rằng không là một thặng dư toàn phương nếu và chỉ nếu là một thặng dư toàn phương.
Do đó, đúng một trong hai số và 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 .
Chứng minh định lý
Gọi là một số nguyên tố lớn hơn thỏa mãn . Giả sử rằng không có hai căn nguyên thủy liên tiếp theo modulo . Khi đó, theo bổ đề, một nửa trong số 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 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à (do ). Đây là một mâu thuẫn.
Do đó, định lý được chứng minh.
Nhận xét
Đăng nhận xét