Bài viết

5.3: Sự tồn tại của các rễ nguyên thủy - Toán học


Trong phần này, chúng tôi chứng minh những số nguyên nào có gốc nguyên thủy. Chúng ta bắt đầu bằng cách chỉ ra rằng mọi lũy thừa của một số nguyên tố lẻ đều có một gốc nguyên thủy và để làm điều này, chúng ta bắt đầu bằng cách chỉ ra rằng mọi bình phương của một số nguyên tố lẻ đều có một căn nguyên thủy.

Nếu (p ) là một số nguyên tố lẻ có gốc nguyên thủy (r ), thì người ta có thể có (r ) hoặc (r + p ) làm môđun gốc nguyên thủy (p ^ 2 ).

Lưu ý rằng vì (r ) là một modulo gốc nguyên thủy (p ), nên [ord_pr = phi (p) = p-1. ] Let (m = ord_ {p ^ 2} r ) , thì [r ^ m equiv 1 (mod p ^ 2). ] Do đó [r ^ m equiv 1 (mod p). ] Theo Định lý 54, chúng ta có [p-1 mid m. ] Theo Bài tập 7 của phần 6.1, chúng ta cũng có [m mid phi (p ^ 2). ] Ngoài ra, ( phi (p ^ 2) = p (p-1) ) và do đó (m ) chia cho (p ) hoặc (p-1 ). Và vì (p-1 mid m ) nên chúng ta có [m = p-1 mbox {hoặc} m = p (p-1). ] Nếu (m = p (p -1) ) và (ord_ {p ^ 2} r = phi (p ^ 2) ) thì (r ) là một modulo gốc nguyên thủy (p ^ 2 ). Nếu không, chúng ta có (m = p-1 ) và do đó [r ^ {p-1} equiv 1 (mod p ^ 2). ] Cho (s = r + p ). Sau đó, (s ) cũng là một modulo gốc nguyên thủy (p ). Do đó, (ord_ {p ^ 2} s ) bằng (p-1 ) hoặc (p (p-1) ). Chúng ta sẽ chỉ ra rằng (ord_ {p ^ 2} s neq p-1 ) sao cho (ord_ {p ^ 2} s = p (p-1) ). Lưu ý rằng [ begin {align} s ^ {p-1} = (r + p) ^ {p-1} & = & r ^ {p-1} + (p-1) r ^ {p-2} p + ... + p ^ {p-1} & = & r ^ {p-1} + (p-1) pr ^ {p-2} (mod p ^ 2). end {align} ] Do đó [p ^ 2 mid s ^ {p-1} - (1-pr ^ {p-2}. ] Cũng lưu ý rằng if [p ^ 2 mid (s ^ {p-1} -1), ] thì [p ^ 2 mid pr ^ {p-2}. ] Vì vậy, chúng ta có [p mid r ^ {p-2} ] là không thể vì (p nmid r ). Vì (ord_ {p ^ 2} s neq p-1 ), chúng ta có thể kết luận rằng [ord_ ​​{p ^ 2} s = p (p-1) = phi (p ^ 2) . ] Do đó, (s = r + p ) là gốc nguyên thủy của (p ^ 2 ).

Chú ý rằng 7 có 3 là một gốc nguyên thủy. Hoặc (ord_ {49} 3 = 6 ) hoặc (ord_ {49} 3 = 42 ). Nhưng vì (3 ^ 6 not equiv 1 (mod 49) ). Do đó (ord_ {49} 3 = 42 ). Do đó 3 là gốc nguyên thủy của 49.

Bây giờ chúng ta chỉ ra rằng bất kỳ lũy thừa nào của một số nguyên tố lẻ đều có gốc nguyên thủy.

Cho (p ) là một số nguyên tố lẻ. Khi đó, bất kỳ lũy thừa nào của (p ) là một gốc nguyên thủy. Hơn nữa, nếu (r ) là modulo gốc nguyên thủy (p ^ 2 ), thì (r ) là modulo gốc nguyên thủy (p ^ m ) cho tất cả các số nguyên dương (m ).

Theo Định lý 62, chúng ta biết rằng bất kỳ số nguyên tố nào (p ) đều có gốc nguyên thủy (r ) cũng là môđun gốc nguyên thủy (p ^ 2 ), do đó [ label {1} ​​p ^ 2 nmid (r ^ {p-1} -1). ] Chúng tôi sẽ chứng minh bằng quy nạp rằng [ label {2} p ^ m nmid (r ^ {p ^ {m-2} (p-1)} -1) ] cho tất cả các số nguyên (m geq 2 ). Khi chúng ta chứng minh được tính đồng dư ở trên, chúng ta chỉ ra rằng (r ) cũng là một modulo gốc nguyên thủy (p ^ m ). Cho (n = ord_ {p ^ m} r ). Theo Định lý 54, chúng ta biết rằng (n mid phi (p ^ m) ). Ngoài ra, chúng ta biết rằng ( phi (p ^ m) = p ^ m (p-1) ). Do đó (n mid p ^ m (p-1) ). Mặt khác, vì [p ^ m mid (r ^ n- 1), ] chúng tôi cũng biết rằng [p mid (r ^ n-1). ] Vì ( phi (p) = p-1 ), chúng ta thấy rằng theo Định lý 54, chúng ta có (n = l (p-1) ). cũng (n mid p ^ {m-1} (p-1) ), chúng ta có (n = p ^ s (p-1) ), trong đó (0 leq s leq m- 1 ). Nếu (n = p ^ s (p-1) ) với (s leq m-2 ), thì [p ^ k mid r ^ {p ^ {m-2} (p-1) } -1, ] là một mâu thuẫn. Do đó [ord_ ​​{p ^ m} r = phi (p ^ m). ]

Bây giờ chúng ta chứng minh ([2]) bằng quy nạp. Giả sử rằng khẳng định của chúng tôi là đúng với tất cả (m geq 2 ). Sau đó [p ^ m nmid (r ^ {p ^ {m-2} (p-1)} - 1). ] Bởi vì ((r, p) = 1 ), chúng ta thấy rằng (( r, p ^ {m-1}) = 1 ). Chúng ta cũng biết từ định lý Euler rằng [p ^ {m-1} mid (r ^ {p ^ {m-2} (p-1)} - 1). ] Do đó tồn tại một số nguyên (k ) sao cho [r ^ {p ^ {m-2} (p-1)} = 1 + kp ^ {m-1}. ] trong đó (p nmid k ) bởi vì (r ^ {p ^ {m-2} (p-1)} not equiv 1 (mod p ^ m) ). Vì vậy, bây giờ chúng ta có [ begin {align} r ^ {p ^ {m-1} (p-1)} & = & (1 + kp ^ {m-1}) ^ p & equiv & 1 + kp ^ m (mod p ^ {m + 1}) end {align} ] Bởi vì (p nmid k ), chúng ta có [p ^ {m + 1} nmid (r ^ {p ^ { m-1} (p-1)} - 1). ]

Vì 3 là căn nguyên của 7, nên 3 là căn nguyên của (7 ^ k ) cho mọi số nguyên dương (k ).

Trong định lý sau, chúng tôi chứng minh rằng không có lũy thừa nào của 2, ngoài 2 hoặc 4, có căn nguyên thủy và đó là vì khi (m ) là một số nguyên lẻ, (ord_2 ^ km neq phi (2 ^ k) ) và điều này là do (2 ^ k mid (a ^ { phi (2 ^ k) / 2} -1) ).

Nếu (m ) là một số nguyên lẻ và nếu (k geq 3 ) là một số nguyên, thì [m ^ {2 ^ {k-2}} equiv 1 (mod 2 ^ k). ]

Chúng tôi chứng minh kết quả bằng quy nạp. Nếu (m ) là một số nguyên lẻ thì (m = 2n + 1 ) là một số nguyên (n ). Do đó, [m ^ 2 = 4n ^ 2 + 4n + 1 = 4n (n + 1) +1. ] Nó theo sau (8 mid (m ^ 2-1) ).

Bây giờ giả sử rằng [2 ^ k mid (m ^ {2 ^ {k-2}} - 1). ] Sau đó, có một số nguyên (q ) sao cho [m ^ {2 ^ {k- 2}} = 1 + q.2 ^ {k}. ] Như vậy bình phương cả hai vế, ta được [m ^ {2 ^ {k-1}} = 1 + q.2 ^ {k + 1} + q ^ 22 ^ {2k}. ] Như vậy [2 ^ {k + 1} mid (m ^ {2 ^ {k-1}} - 1). ]

Bây giờ lưu ý rằng 2 và 4 có gốc nguyên thủy tương ứng là 1 và 3.

Bây giờ chúng ta liệt kê tập hợp các số nguyên không có gốc nguyên thủy.

Nếu (m ) không phải là (p ^ a ) hoặc (2p ^ a ), thì (m ) không có gốc nguyên thủy.

Cho (m = p_1 ^ {s_1} p_2 ^ {s_2} ... p_i ^ {s_i} ). Nếu (m ) có gốc nguyên thủy (r ) thì (r ) và (m ) là tương đối nguyên tố và (ord_mr = phi (m) ). Chúng ta cũng có, chúng ta có ((r, p ^ s) = 1 ) trong đó (p ^ s ) là các số nguyên tố trong quá trình phân tích nhân tử của (m ). Theo định lý Euler, chúng ta có [p ^ s mid (r ^ { phi (p ^ s)} - 1). ] Bây giờ hãy để [L = [ phi (p_1 ^ {s_1}), phi (p_2 ^ {s_2}), ..., phi (p_i ^ {s_i})]. ] Chúng tôi biết rằng [r ^ L equiv 1 (mod p_k ^ {s_k}) ] cho tất cả (1 leq k leq m ). Do đó, sử dụng Định lý Phần dư Trung Quốc, chúng ta nhận được [m mid (r ^ L-1), ] dẫn đến (ord_mr = phi (m) leq L ). Bây giờ vì [ phi (m) = phi (p_1 ^ {s_1}) phi (p_2 ^ {s_2}) ... phi (p_n ^ {s_n}) leq [ phi (p_1 ^ {s_1 }), phi (p_2 ^ {s_2}), ..., phi (p_n ^ {s_n})]. ] Bây giờ bất đẳng thức trên chỉ đúng nếu [ phi (p_1 ^ {s_1}), phi (p_2 ^ {s_2}), ..., phi (p_n ^ {s_n}) ] tương đối nguyên tố. Bây giờ lưu ý rằng theo Định lý 41, [ phi (p_1 ^ {s_1}), phi (p_2 ^ {s_2}), ..., phi (p_n ^ {s_n}) ] không phải là tương đối nguyên tố trừ khi (m = p ^ s ) hoặc (m = 2p ^ s ) trong đó (p ) là một số nguyên tố lẻ và (t ) là một số nguyên dương bất kỳ.

Bây giờ chúng ta chỉ ra rằng tất cả các số nguyên có dạng (m = 2p ^ s ) đều có gốc nguyên thủy.

Hãy xem xét một số nguyên tố (p neq 2 ) và let (s ) là một số nguyên dương, thì (2p ^ s ) có một gốc nguyên thuỷ. Trên thực tế, nếu (r ) là một modulo gốc lẻ (p ^ s ), thì nó cũng là một modulo gốc nguyên thủy (2p ^ s ) nhưng nếu (r ) là chẵn, ( r + p ^ s ) là một modulo gốc nguyên thủy (2p ^ s ).

Nếu (r ) là một modulo gốc nguyên thủy (p ^ s ) thì [p ^ s mid (r ^ { phi (p ^ s)} - 1) ] và không có số mũ dương nào nhỏ hơn ( phi (p ^ s) ) có thuộc tính này. Cũng lưu ý rằng [ phi (2p ^ s) = phi (p ^ s), ] để [p ^ s mid (r ^ { phi (2p ^ s)} - 1). ]

Nếu (r ) là số lẻ, thì [2 mid (r ^ { phi (2p ^ s)} - 1). ] Do đó theo Định lý 56, chúng ta nhận được [2p ^ s mid (r ^ { phi (2p ^ s)} - 1). ] Điều quan trọng cần lưu ý là không có lũy thừa nào nhỏ hơn của (r ) đồng dư với 1 modulo (2p ^ s ). Sức mạnh này cũng sẽ tương ứng với 1 modulo (p ^ s ) mâu thuẫn với (r ) là gốc nguyên thủy của (p ^ s ). Theo đó (r ) là một modulo gốc nguyên thủy (2p ^ s ).

Trong khi, nếu (r ) chẵn, thì (r + p ^ s ) là lẻ. Do đó [2 mid ((r + p ^ s) ^ { phi (2p ^ s)} - 1). ]

Vì (p ^ s mid (r + p ^ sr) ), chúng ta thấy rằng [p ^ s mid ((r + p ^ s) ^ { phi (2p ^ s)} - 1). ] Kết quả là chúng ta thấy rằng (2p ^ s mid ((r + p ^ s) ^ { phi (2p ^ s)} - 1) ) và vì không có lũy thừa nào nhỏ hơn của (r + p ^ s ) đồng dư với 1 modulo (2p ^ s ), chúng ta thấy rằng (r + p ^ s ) là một modulo gốc nguyên thủy (2p ^ s ).

Kết quả là theo Định lý 63, Định lý 65 và Định lý 66, chúng ta thấy rằng

Số nguyên dương (m ) có gốc nguyên thủy nếu và chỉ khi (n = 2,4, p ^ s ) hoặc (2p ^ s )

cho số nguyên tố (p neq 2 ) và (s ) là một số nguyên dương.
Bài tập

  1. Các số nguyên 4, 12, 28, 36, 125 nào sau đây có một gốc nguyên thủy.
  2. Tìm một gốc nguyên thủy của 4, 25, 18.
  3. Tìm tất cả các gốc nguyên thủy modulo 22.
  4. Chứng tỏ rằng có cùng một số gốc nguyên thủy modulo (2p ^ s ) như modulo (p ^ s ), trong đó (p ) là một số nguyên tố lẻ và (s ) là một số nguyên dương .
  5. Tìm tất cả các gốc nguyên thủy modulo 25.
  6. Chứng tỏ rằng số nguyên (n ) có gốc nguyên thủy nếu và chỉ khi các nghiệm duy nhất của đồng dư (x ^ 2 equiv 1 (mod n) ) là (x equiv pm1 (mod n) ).

Bằng chứng về sự tồn tại của rễ nguyên thủy

Trong cuốn sách của tôi (Lý thuyết số cơ bản, Stillwell), bài tập 3.9.1 yêu cầu đưa ra một bằng chứng thay thế về sự tồn tại của một căn nguyên đối với bất kỳ số nguyên tố nào.

Cho $ p $ là số nguyên tố và coi nhóm $ mathbb/ p mathbb$.

Giả sử rằng các phần tử khác 0 $ text p $ có đơn hàng tối đa $ n & lt p - 1 $. Chứng tỏ rằng điều này ngụ ý $ x ^ n equiv 1 ( text p) $ cho tất cả các giá trị $ p - 1 $ khác 0 của $ x $, $ text p $, trái với định lý đồng dư đa thức Lagrange.

Những gì tôi đã xem xét cho đến nay là tất cả các phần tử khác 0 của nhóm $ mathbb/ p mathbb$ tạo các nhóm con có thứ tự $ k leq n & lt p - 1 $, sao cho $ k mid p - 1 $ (theo định lý Lagrange cho các nhóm). Tuy nhiên, hiển thị rằng $ k mid n $ lại bỏ qua tôi. Bất kỳ ý tưởng nào thêm?


Không có công thức chung nào để tìm một căn nguyên. Thông thường, những gì bạn làm là chọn một số và kiểm tra. Khi bạn tìm thấy một gốc nguyên thủy, bạn sẽ tìm thấy tất cả các gốc khác.

Làm thế nào bạn kiểm tra

Để kiểm tra $ a $ có phải là gốc nguyên thủy của $ p $ hay không, bạn cần làm như sau. Đầu tiên, hãy đặt $ s = phi (p) $ trong đó $ phi () $ là hàm phụ của Euler. Nếu $ p $ là số nguyên tố thì $ s = p-1 $. Sau đó, bạn cần xác định tất cả các thừa số nguyên tố của $ s $: $ p_1, ldots, p_k $. Cuối cùng, hãy tính $ a ^ mod p $ cho tất cả $ i = 1 ldots k $ và nếu bạn tìm thấy $ 1 $ trong số các phần còn lại thì nó KHÔNG phải là gốc nguyên thủy, ngược lại thì đúng là như vậy.

Vì vậy, về cơ bản bạn cần tính và kiểm tra các số $ k $ trong đó $ k $ là số các thừa số nguyên tố khác nhau trong $ phi (p) $.

Hãy để chúng tôi tìm giá trị gốc thấp nhất của $ 761 $:

  • $ s = phi (761) = 760 = 2 ^ 3 times5 times19 $
  • quyền hạn để kiểm tra là: 760 đô la / 2 = 380 đô la, 760 đô la / 5 = 152 đô la và 760 đô la / 19 = 40 đô la (chỉ 3 thay vì kiểm tra tất cả chúng)
  • kiểm tra 2:
    • $ 2 ^ <380> equiv 1 mod 761 $ oops
    • $ 3 ^ <380> equiv -1 mod 761 $ OK
    • $ 3 ^ <152> equiv 1 mod 761 $ oops
    • $ 5 ^ <380> equiv 1 mod 761 $ oops
    • $ 6 ^ <380> equiv -1 mod 761 $ OK
    • $ 6 ^ <152> equiv 67 mod 761 $ OK
    • $ 6 ^ <40> equiv -263 mod 761 $, xin chào!

    Vì vậy, gốc nguyên thủy nhỏ nhất của 761 là 6.

    Cách bạn chọn

    Thông thường, bạn chọn ngẫu nhiên hoặc bắt đầu từ 2 và đi lên (ví dụ: khi tìm kiếm gốc nguyên thủy nhất), hoặc theo bất kỳ trình tự nào khác tùy thuộc vào nhu cầu của bạn.

    Lưu ý rằng khi bạn chọn ngẫu nhiên, $ phi (p) $ càng có nhiều thừa số nguyên tố, nói chung, xác suất tìm thấy ngẫu nhiên càng ít. Ngoài ra, sẽ có nhiều quyền hạn hơn để kiểm tra.

    Ví dụ: nếu bạn chọn một số ngẫu nhiên để kiểm tra xem có phải là số nguyên gốc của $ 761 $ hay không, thì xác suất tìm thấy một số là khoảng $ frac <1> <2> times frac <4> <5> times frac <18> <19> $ hoặc 38% và có 3 lũy thừa để kiểm tra. Nhưng nếu bạn đang tìm các gốc nguyên thủy của, chẳng hạn, $ 2311 $ thì xác suất tìm thấy một cách ngẫu nhiên là khoảng 20% ​​và có 5 lũy thừa để kiểm tra.

    Làm thế nào bạn tìm thấy tất cả các gốc nguyên thủy khác

    Khi bạn đã tìm thấy một gốc nguyên thủy, bạn có thể dễ dàng tìm thấy tất cả các gốc khác. Thật vậy, nếu $ a $ là mod gốc nguyên thủy $ p $ và $ p $ là số nguyên tố (để đơn giản hơn), thì $ a $ có thể tạo ra tất cả các phần dư khác $ 1 ldots (p-1) $ dưới dạng lũy ​​thừa: $ a ^ 1 Equiv a, a ^ 2, ldots, a ^ tương đương với 1 $. Và $ a ^ m mod p $ là một gốc nguyên thủy khác nếu và chỉ khi $ m $ và $ p-1 $ là cùng chuẩn (nếu $ gcd (m, p-1) = d $ thì $ (a ^ m) ^ <(p-1) / d> equiv (a ^)^ Equiv 1 mod p $, vì vậy chúng ta cần $ d = 1 $). Nhân tiện, đây chính là lý do tại sao bạn có $ phi (p-1) $ gốc nguyên thủy khi $ p $ là số nguyên tố.

    Ví dụ: $ 6 ^ 2 = 36 $ hoặc $ 6 ^ <15> tương đương 686 $ không phải là gốc nguyên thủy của $ 761 $ vì $ gcd (2,760) = 2 & gt1 $ và $ gcd (15,760) = 5 & gt1 $, nhưng, cho ví dụ, $ 6 ^ 3 = 216 $ là một gốc nguyên thủy khác của 761.


    Tiểu mục 10.5.1 Tìm một liên kết gốc cao hơn ¶ permalink

    Đây là một cách để giải quyết sự đồng dư đầu tiên. Đầu tiên, hãy tìm một modulo gốc nguyên thủy (19 ). Rõ ràng là chúng ta có thể hỏi Sage, hoặc sử dụng Bổ đề 10.2.3 với thử và sai. Trong quá khứ không xa, mặt sau của mỗi văn bản lý thuyết số đều có một bảng gốc sơ khai!

    Bây giờ những gì chúng tôi sẽ làm là cố gắng đại diện cho cả hai các mặt của beginx ^ 4 equiv 13 text <(mod> 19) end như quyền hạn của gốc nguyên thủy đó.

    Phần đơn giản là đại diện cho (x ^ 4 ), chúng tôi chỉ nói rằng (x equiv 2 ^ i ) cho một số (chưa biết) (i ), vì vậy beginx ^ 4 equiv left (2 ^ i right) ^ 4 equiv 2 ^ <4 xì-căng-đan . end Phần khó hơn là tìm ra sức mạnh của (2 ) mang lại cho (13 ). Một lần nữa, không có lối tắt, mặc dù sách trước đây có bảng rất lớn về chúng và quyền hạn (để dễ dàng tham khảo). Trong thực tế, người ta sẽ có sẵn tất cả các quyền hạn của một gốc nguyên thủy nhất định để sử dụng trước thời hạn.

    Bằng cách thay thế các gốc nguyên thủy cho (x ^ 4 ) và (13 ), chúng ta có thể nói rằng beginx ^ 4 equiv 13 text <(mod> 19) end trở thành bắt đầu2 ^ <4 prefer equiv 2 ^ <5> text <(mod> 19) . End

    Đây là một dạng vấn đề quen thuộc hơn nhiều. Làm thế nào chúng ta sẽ giải quyết điều này ở trường trung học? Bạn sẽ giải nó theo cách này, với phương trình (không phải đồng dư): begin2 ^ <4 prefer = 2 ^ <5> Rightarrow 4i = 5 Rightarrow i = 5/4 . End Chúng tôi sẽ cố gắng làm một cái gì đó rất giống ở đây.

    Điều rất quan trọng là sự đồng dư này, theo một nghĩa nào đó, thực sự không còn là đồng dư trong ( mathbb_ <19> ). Chính xác mà nói, mọi thứ trong tầm mắt thực sự nằm trong (U_ <19> ), một nhóm trật tự tuần hoàn ( phi (19) = 18 ). Nhưng một nhóm thứ tự tuần hoàn (18 ) sẽ giống như suy nghĩ modulo mười tám! Vì vậy, chúng tôi có thể lấy ra số mũ, giống như trong tính toán trước, nhưng làm những việc (mod (18 )): begin4i equiv 5 text <(mod> 18) . End (Xem Bài tập 10.6.12.)

    Đáng buồn thay, điều này không có một giải pháp. Nhưng chúng tôi đã tìm ra nó mà không cần sử dụng mọi điện thứ tư ngoài đó! Thật vậy, làm điều đó xác nhận kết quả của chúng tôi:

    Ví dụ 10.5.1

    Thay vào đó, hãy thử cùng một modulo đồng dư (17 ) - nghĩa là chúng ta có thể giải được không beginx ^ 4 equiv 13 text <(mod> 17) ? end Ở đây, gốc nguyên thủy là (3 ), và hóa ra là (3 ^ 4 equiv 13 ), vì vậy chúng ta có thể thử. Điều này cho bắt đầu3 ^ <4 xì-pov 3 ^ 4 text <(mod> 17) Mũi tên phải 4i equiv 4 text <(mod> 16) ,, end mà chắc chắn có giải pháp.

    Trên thực tế, có bốn giải pháp ( (1,5,9,13 )) cho đồng dư giảm begini equiv 1 text <(mod> 4) end vì vậy có bốn nghiệm ( (3 ^ 1,3 ^ 5,3 ^ 9,3 ^ <13> )) cho đồng dư ban đầu. Hãy kiểm tra điều này:

    Bạn thậm chí có thể thấy nó tại nơi làm việc cho những thứ phức tạp hơn.

    Ví dụ 10.5.2

    Nếu chúng ta thử giải (x ^ 6 equiv 8 ) (mod (49 )), chúng ta sẽ cần một gốc sơ khai gồm 49 3 công trình. Tôi có thể tìm ra sức mạnh (3 ^ i ) của (3 ) mang lại (8 ):

    Vì vậy, chúng tôi viết (x = 3 ^ i ) cho một số chưa biết (i ), và lấy begin3 ^ <6 prefer equiv 3 ^ <36> text <(mod> 49) , end điều đó cho chúng ta bắt đầu6i equiv 36 text <(mod> phi (49) = 42) end và điều này giảm xuống begini equiv 6 text <(mod> 7) . end Vì vậy, (i = 6,13,20,27,34,41 ) đều hoạt động, có nghĩa là (x = 3 ^ Equiv 43,10,16,6,39,33 ) tất cả đều hoạt động.


    5.3: Sự tồn tại của các rễ nguyên thủy - Toán học

    Văn phòng: 234B, Kỹ thuật 1
    Điện thoại: (312) 567-3128
    E-mail: kaul [at] math.iit.edu

    Thời gian: 3:15 chiều, Thứ Ba & Thứ Năm.
    Địa điểm: 103, Engineering 1 Bldg.

    Giờ làm việc: 2 giờ chiều - 4 giờ chiều, Thứ Tư, đi bộ và theo lịch hẹn.
    Các phiên sự cố vào thứ Hai lúc 5:40 chiều.

    Các Tài liệu phát thông tin khóa học có mô tả sâu rộng về khóa học - chủ đề, sách giáo khoa, chính sách đánh giá sinh viên, cũng như các thông tin liên quan khác. Đọc nó cẩn thận!

    Lời khuyên dành cho sinh viên
    Lời khuyên tuyệt vời của Doug West về cách viết lời giải bài tập về nhà trong một khóa học như thế này.
    Tại sao chúng ta phải học cách chứng minh?
    Làm thế nào để đọc Toán học? Thông tin cơ bản, thêm chi tiết.
    Cách học và cách học toán.
    Một lưu ý trừu tượng hơn, đây là cuộc thảo luận về Ngôn ngữ và Ngữ pháp của Toán học - đó là những gì bạn đang học trong một khóa học như thế này.

    Terry Tao, người đoạt huy chương Fields năm 2006, là lời khuyên tuyệt vời cho các chuyên gia toán học, đặc biệt là những người dự định học tiếp lên cao học. Đọc bắt buộc.


    Lý thuyết số: Trong ngữ cảnh và tương tác

    Chúng ta sẽ sớm bắt đầu nói về mật mã và các vấn đề liên quan. Trước khi làm như vậy, chúng ta sẽ xem trước nhu cầu tính toán của mình bằng cách sử dụng các gốc nguyên thủy để giải quyết một số đồng dư theo cách hay.

    Giả sử bạn muốn giải quyết một đồng dư liên quan nhiều hơn những điều cơ bản mà chúng tôi đã giải quyết cho đến nay. Một biểu mẫu chung mà chúng tôi có thể muốn giải quyết sẽ trông giống như

    trong đó (a ) hoặc (b ) có thể là một biến và (n ) sẽ là số nguyên tố hoặc lũy thừa. Đây là hai ví dụ:

    Bạn có thể nghĩ cách đầu tiên là tìm modulo gốc cao hơn (n text <,> ) và cách thứ hai là tìm lôgarit modulo (n text <.> )

    Như chúng ta sẽ thấy bên dưới, chiến lược chung của chúng ta sẽ là tìm một gốc nguyên thủy (g ) của (n ) (khi điều này là có thể) và viết cả hai dưới dạng lũy ​​thừa của (g text <,> ), ví dụ: (a = g ^ i ) và (c = g ^ j ) cho một số (i, j in mathbb text <.> ) Sau đó, sự tương đồng của chúng ta sẽ trở thành

    và nghĩ về nó như việc giải theo số mũ (ib ) và (j ) sẽ có hiệu quả.

    Tiểu mục 10.5.1 Tìm gốc cao hơn

    Với phần giới thiệu đó, chúng ta hãy xem xét một cách để giải quyết sự đồng dư đầu tiên bằng cách sử dụng ý tưởng này.

    Đầu tiên, hãy tìm một modulo gốc nguyên thủy (17 text <.> ) Rõ ràng là chúng ta có thể hỏi Sage và lệnh nội trang của nó là original_root, hoặc sử dụng Bổ đề 10.2.3 với thử và sai. Trong quá khứ không xa, mặt sau của mỗi văn bản lý thuyết số đều có một bảng gốc sơ khai!

    Bây giờ những gì chúng tôi sẽ làm là cố gắng đại diện cho cả hai các mặt của

    như quyền hạn của gốc nguyên thủy đó.

    Phần đơn giản là đại diện cho (x ^ 3 text <> ), chúng ta chỉ nói rằng (x equiv 3 ^ i ) cho một số (chưa biết) (i text <,> ) vậy

    Phần khó hơn là tìm ra sức mạnh của (3 ) mang lại cho (5 text <.> ) Một lần nữa, không có phím tắt, mặc dù các văn bản lý thuyết số trong quá khứ có các bảng khổng lồ về chúng và sức mạnh của chúng (cho Dễ tham khảo). Trong thực tế, người ta sẽ có sẵn tất cả các quyền hạn của một gốc nguyên thủy nhất định để sử dụng trước thời hạn.

    Bằng cách thay thế các gốc nguyên thủy trong (x ^ 3 ) và (5 text <,> ), chúng ta biến đổi

    Đây là một dạng vấn đề quen thuộc hơn nhiều. Làm thế nào chúng ta sẽ giải quyết điều này ở trường trung học? Bạn sẽ giải nó theo cách này, với các phương trình (không phải đồng dư):

    Chúng tôi sẽ cố gắng làm một cái gì đó rất giống ở đây.

    Điều rất quan trọng là sự đồng dư này, theo một nghĩa nào đó, thực sự không còn là đồng dư trong ( mathbb_ <17> text <.> ) Nói chính xác, mọi thứ trong tầm mắt thực sự nằm trong (U_ <17> text <,> ) một nhóm thứ tự tuần hoàn ( phi (17) = 16 text <.> ) Nhưng một nhóm thứ tự tuần hoàn (16 ) sẽ giống như suy nghĩ modulo mười sáu! Vì vậy, chúng tôi có thể lấy ra số mũ, giống như trong tính toán trước, nhưng làm những việc (mod (16 )):

    (Xem Bài tập 10.6.14 để giải thích cho việc thực hiện thao tác này.)

    Đoán một chút và kiểm tra (hoặc các phương pháp mạnh hơn trước đó trong sách) cho thấy rằng (i = 7 ) là đủ, do đó (x = 3 ^ <7> equiv 11 ) (mod (17 )) là giải pháp. Và chúng tôi đã tìm ra nó mà không cần lấy từng khối lập phương ra khỏi đó!

    Thật vậy, chỉ làm điều đó xác nhận kết quả của chúng tôi. Chúng tôi lấy tất cả các khối bắt đầu từ (2 text <,> ) và một khối tương ứng với (11 ) là những gì chúng tôi muốn:

    Lưu ý việc sử dụng phạm vi từ Sage note 2.1.3. Bạn nghĩ tại sao chúng tôi sử dụng nó ở đây?

    Ví dụ 10.5.1.

    Nếu chúng ta thay đổi đồng dư thành lũy thừa thứ tư (x ^ 4 equiv 5 ) (mod (17 )), thì thay đổi duy nhất là bây giờ chúng ta phải giải (4i equiv 5 ) (mod ( 16 )). Tuy nhiên, không có giải pháp nào như vậy vì ( gcd (4,16) = 4 nmid 5 text <,> ) và chúng tôi xác nhận điều này bằng cách thấy rằng (5 ) không hiển thị trong danh sách này:

    Ví dụ 10.5.2.

    Cuối cùng, hãy thử giải mã liên quan chặt chẽ (x ^ 3 equiv 7 ) (mod (19 )). Ở đây, gốc nguyên thủy là (2 text <,> ) và hóa ra là (2 ^ 6 equiv 7 text <,> ) nên chúng tôi có thể thử một giải pháp. Chúng tôi đạt được

    mà chắc chắn có giải pháp.

    Trên thực tế, có ba giải pháp ( (2,8,14 )) để giảm bớt sự đồng dư

    vì vậy có ba nghiệm ( (2 ^ 2,2 ^ 8,2 ^ <14> )) cho đồng dư ban đầu. Hãy kiểm tra điều này:

    Một chiến lược tương tự có thể hoạt động cho các kết quả cấp độ cao hơn. (Xem [E.2.4, Định lý 8.17] để biết tuyên bố chung về thời điểm tồn tại các nghiệm như vậy, mà chúng tôi sẽ bỏ qua vì lợi ích của không gian.)

    Ví dụ 10.5.3.

    Nếu chúng ta thử giải (x ^ 6 equiv 8 ) (mod (49 )), chúng ta sẽ cần một gốc sơ khai gồm 49 3 công trình. Tôi có thể tìm ra sức mạnh (3 ^ i ) của (3 ) mang lại (8 text <:> )

    Có vẻ như đó là (3 ^ <36> text <.> ) Vì vậy, chúng tôi viết (x = 3 ^ i ) cho một số chưa xác định (i text <,> ) và nhận được

    Vì vậy, (i = 6,13,20,27,34,41 ) đều hoạt động, có nghĩa là (x = 3 ^ Equiv 43,10,16,6,39,33 ) tất cả đều hoạt động.

    Tiểu mục 10.5.2 Các logarit rời rạc

    Tương tự, chúng ta có thể thử giải các ví dụ về lôgarit như

    Thật vậy, việc giải quyết vấn đề này là một ví dụ về cái được gọi là một vấn đề. Những vấn đề như vậy rõ ràng là rất, rất khó để giải quyết nhanh chóng, nhưng (!) Không ai có từng đã chứng minh cái này.

    Ví dụ 10.5.4.

    Hãy giải (5 ^ x equiv 17 text <(mod> 19) text <.> ) Như chúng ta đã lưu ý trong Ví dụ 10.5.2, modulo gốc nguyên thủy 19 là 2 và chúng ta có thể kiểm tra điều đó (5 Equiv 2 ^ <16> text <(mod> 19) ) và (17 equiv 2 ^ <10> text <(mod> 19) text <.> ) Sau đó, thay thế chúng, chúng ta thấy cái đó

    Vì mỗi số trong đồng dư sau này là số chẵn, chúng ta có thể giảm giá trị này thành (8x equiv 5 ) (mod (9 )), điều này làm giảm thêm thành phần dễ giải (- x equiv 5 ) (mod (9 )).

    Lấy (x equiv -5 equiv 4 text <,> ) và ghi nhớ mô-đun ban đầu của (18 text <,> ) cho thấy rằng chúng ta có thể cho phép (x equiv 4,13 ) trong việc giải quyết đồng dư ban đầu. Và thực sự

    Sage note 10.5.5. Nhắc nhở về bình đẳng.

    Để kiểm tra xem hai thứ có bằng nhau hay không, hãy nhớ rằng bạn chỉ có thể sử dụng dấu == với hai biểu thức và xem liệu bạn nhận được True hay False.

    Ví dụ 10.5.6.

    Hãy thử giải (16 ^ x equiv 13 text <(mod> 19) text <.> )

    Một lần nữa, (2 ) là gốc nguyên thủy của (19 text <,> ) và rõ ràng là (16 = 2 ^ 4 text <.> ) Nó có thể khó biểu diễn hơn (13 text < > ) tất nhiên chúng ta có thể làm điều đó với máy tính, nhưng lưu ý rằng (13 + 19 = 32 = 2 ^ 5 text <.> ) Đôi khi chúng ta thực sự có thể làm chúng bằng tay!

    Do đó, sự đồng dư của chúng ta trở thành

    Tuy nhiên, vì ( gcd (4,18) = 2 nmid 5 text <,> ) theo Mệnh đề 5.1.1 nên đồng dư sau này không có nghiệm, nên đồng dư ban đầu cũng vậy. (Hóa ra (16 ) chỉ có thứ tự (9 ) như một phần tử của (U_ <19> text <,> ) và rõ ràng (13 ) không phải là một trong những phần tử trong nhóm con được tạo bởi (16 text <.> ))


    Ghi chú Toán học của Joni

    Trong bài đăng này, chúng tôi chứng minh sự tồn tại của các lũy thừa nguyên tố modulo gốc, bằng cách sử dụng lý thuyết số cơ bản và trình bày nhiều vấn đề trong đó các căn nguyên có thể được áp dụng. Ví dụ, bài đăng này thích hợp cho việc luyện thi olympiad.

    Giới thiệu

    Rễ nguyên thủy số nguyên tố modulo

    Moduli sức mạnh chính

    Trong trường hợp các lũy thừa cao hơn $ p $, một lần nữa có một kết quả tốt đẹp: Nếu $ g $ là một modulo gốc nguyên thủy $ p $ và $ p ^ 2 $, thì nó là một gốc nguyên thủy đối với tất cả các lũy thừa. Giả sử $ g ^ k equiv 1 pmod> $. Sau đó, theo giả định $ p (p-1) mid k $. Chúng tôi cho thấy bằng cách quy nạp trên $ alpha $ rằng $ p ^ < alpha-1> (p-1) mid k. $ Trường hợp $ alpha = 2 $ đã được xem xét. Nếu trường hợp $ alpha $ đã được chứng minh, $ g ^ Equiv 1 pmod> $ ngụ ý $ g ^ < frac

    > Equiv 1 pmod> $ vì $ g ^ k-1 = (g ^ < frac

    > -1) (g ^ < frac

    > +. + g ^ < frac

    > +1) $ và hệ số sau tương ứng với $ p pmod$ vì $ g ^ < frac

    > equiv 1 pmod p $. Do đó, giả thuyết quy nạp cho $ p ^ < alpha> mid k $ và $ p-1 mid k $ đã được biết đến. Tuyên bố hiện đã được chứng minh (nhân tiện, phương pháp chúng tôi đã sử dụng để xử lý các đồng dư $ pmod> $ có thể được tổng quát để chứng minh cái gọi là nâng bổ đề số mũ). & # 9632

    Vì $ varphi (2 ^ < alpha>) = 2 ^ < alpha-1>, $ số $ 5 $ rất gần với việc trở thành một gốc nguyên thủy và điều này là đủ cho nhiều ứng dụng.

    Các vấn đề có thể giải quyết được với các gốc nguyên thủy

    Bài toán 15. Cho $ p $ là một số nguyên tố. Sau đó, độ dài của khoảng thời gian biểu diễn thập phân của $ frac <1>

    $ là $ p-1 $, nếu $ 10 $ là gốc nguyên thủy thì $ pmod p $ và nếu không thì khoảng thời gian ngắn hơn (nó là $ text_

    (10)$).

    trong đó $ q = p_1 ^ < alpha_1>. p_k ^ < alpha_k> $ và $ left ( frac

    right) $ là biểu tượng Legendre ($ left ( frac

    right) $ bằng $ nếu $ p mid n $ và ngược lại nó cho giá trị $ 1 ​​$ nếu $ n tương đương với một ^ 2 pmod p $ cho một số $ a $ và nó cho giá trị $ -1 $ nếu không). Biểu thức trên được gọi là biểu tượng Jacobi $ pmod q $.


    Đồ thị của các nhóm trên bề mặt

    14-4 Chi F p r

    Một lần nữa để ngắn gọn, đặt F p r = G F p r. Để tìm các phép tương tự của các định lý Maschke và Proulx cho các chi của nhóm phẳng hữu hạn và nhóm hình xuyến tương ứng, Jones đã kết hợp phân tích của cô ấy trong Phần 14-3 cho trường hợp này NS = 1 với trường hợp NS ≥ 2 của phần này. Trong trường hợp chung, chúng tôi đặt Δ+ = <α r - l,…, α 2 , α, 1>, cơ sở cho PNS(α) (không gian vectơ của tất cả các đa thức có bậc nhỏ hơn NS hết ℤP, đẳng cấu với ℤP NS ), ở đâu α là một căn nguyên thủy của một đa thức bất khả quy monic bậc NS hết ℤP và chúng tôi đặt Δ× = <α k >, ở đâu (p r − 1, k) = 1. Cho Δ = Δ+ ∪ ΔNS, và tạo thành đồ thị màu C Δ F p r, x k. Sau đó, đặt G F p r, α k biểu thị các đặc tính thấm đẫm giả cơ bản không bị ảnh hưởng bởi sự giảm này. Một lần nữa, chúng tôi gọi đây là đồ thị trường hữu hạn.

    Các chi của lĩnh vực F p r được cho bởi

    Một số quan sát theo thứ tự:

    Định nghĩa 14-8 bao gồm Định nghĩa 14-6, là trường hợp đặc biệt NS = 1.

    Nếu như (p r − 1, k) = 1, sau đó (p r − 1, − k) = 1 cũng được nhưng sử dụng Δ× = <αk > thay vì <>k > chỉ đảo ngược tất cả các mũi tên nhân, do đó các bút danh bên dưới là đồng phân. Do đó, giá trị nhỏ nhất được thực hiện trên 1 2 ϕ p r - 1 bộ tạo nhân, trong đó ϕ là hàm euler phi.

    Để γ F p r được xác định rõ ràng, chúng ta cần thiết lập hai thuộc tính:

    Đối với một đa thức bất khả quy monic cố định NS(NS) của mức độ NS hết ℤP, G F p r, α k phụ thuộc vào k nhưng không dựa trên gốc nguyên thủy cụ thể α của NS(NS) đã chọn. (Xem Vấn đề 14-12.)

    Chọn một khác NS(NS) như ở trên tạo ra một tập hợp các bút danh đẳng lập. (Xem Vấn đề 14-13. Vấn đề này nói chung là mở, nhưng yêu cầu bồi thường cho P = 4, 8, 9 và 16-tất cả những gì chúng ta cần cho phần còn lại của chương này. Đối với công việc sau này, đang chờ giải quyết Vấn đề 14-13, chúng tôi sẽ lấy mức tối thiểu trên tất cả các đa thức bất khả quy monic có bậc NS, cũng thế.)

    Ví dụ, nếu P = NS = 2, đa thức phù hợp duy nhất là NS 2 + NS + 1 và chúng tôi lấy α 2 = α + 1 sao cho 〈α〉 = <1, α, α + 1>. Biểu đồ màu máy bay C(F 4, α) được cho trong Hình 14-4. Chúng tôi sử dụng Δ+ = <α, 1>, bổ sung mô hình bởi α với một cạnh chéo và Δ× = <α>.

    Bây giờ hãy xem xét P = 2 vẫn còn, nhưng với NS = 3. Chúng tôi sử dụng NS 3 + NS + 1, như trong ví dụ của Phần 14.2. Chúng tôi hiển thị C( NS 8, α) trong Hình 14-5, được vẽ trong mặt phẳng với một đường cắt ngang. Điều này thiết lập rằng γ( NS 8) ≤ 1. Để cho thấy rằng γ( NS 8) ≥ 1, chúng tôi có thể xem xét riêng đồ thị màu C( NS 8, α), C( NS 8, α 2 và C( NS 8, α 3), tìm một đồ thị con Kuratowski trong mỗi trường hợp. (Đây là ba đồ thị không đẳng cấu lẫn nhau, khi kiểm tra cấu hình của các kỹ thuật số có thể thấy rõ.) Thay vào đó, chúng ta lưu ý rằng G 1, α, α 2 ℤ 2 3 = Q 3 trong mỗi trường hợp. Theo Định lý 5-25, NS3 là duy nhất không thể tuân theo trong lĩnh vực này. Nếu chúng ta có thể chỉ ra rằng một cung nhân tham gia các đỉnh đối cực, thì NS( NS 8, α k ) sẽ không phẳng, theo Định lý Đường cong Jordan, vì chu kỳ 6 chia mặt phẳng (thu được dưới phép chiếu lập thể) thành hai vùng, với một phản mã trong mỗi vùng. Vì vậy, giải phương trình a + (1 + α + α 2 ) = aα kmột = (1 + α + α 2 )(α k - 1) - 1, đỉnh bắt đầu duy nhất của một cung như vậy. (Đối với Hình 14-5, chúng tôi tính toán rằng một = (1 + α + α 2 )(α − 1) − 1 = α 5 (α 3 ) − 1 = α 2, như được hiển thị trong hình.) α( NS 8) = 1.

    Các lập luận tương tự cho thấy γ F p r ≥ 2 với mỗi p r ≥ 16, với NS ≥ 2: cho P = 2, bắt đầu bằng K2 × K2 × K2 × K2 = C4 × C4 trên điểm xuyến cho P ≥ 5, tìm một đồ thị con của C p r homeomorphic để C5 × C5 trên hình xuyến. Trong cả hai trường hợp, chúng ta có thể tìm thấy một cạnh không thể thêm vào trên hình xuyến, sao cho γ F p r ≥ 1 + 1 = 2. Vì P = 3 và p r ≥ 16, C3 3 là một đồ thị con và chúng tôi biết rằng γ(C3 3) = 7 (Định lý 7-29).

    Vì vậy, để hoàn thành việc phân loại các trường hữu hạn phẳng và hình xuyến, chúng ta chỉ cần nghiên cứu F 9. Xem xét việc xây dựng F 9 được đưa ra trong Phần 14-2, tạo ra vết chìm hình xuyến của Hình 14-6. Nhưng γ( NS 9) ≥ γ(C3 × C3) = 1. Như vậy γ( NS 9) = 1.

    Thu thập các kết quả của phần này và phần trước, chúng ta nhận được hai định lý sau của Jones:

    Trường hữu hạn F p r là trường phẳng nếu và chỉ khi p r = 2, 3, 4, 5, 7 hoặc 11.

    Trường hữu hạn F p r là trường hình xuyến nếu và chỉ khi p r = 8, 9, 13 hoặc 17.

    Định lý tiếp theo cho hai kết quả tiệm cận, cũng được Jones phát triển trong [J4].

    (i) F 2 r là tiệm cận 1 + 2 NS − 3 (NS − 4).

    (ii) F p p là tiệm cận đứng p p + 1 4.

    Các giới hạn sau [J4] sẽ hữu ích trong phần tiếp theo:


    Căn nguyên - Đại số, Khoa học Toán học CSIR-NET Toán học Thuyết minh | EduRev

    Cho là một số nguyên dương. MỘT gốc nguyên thủy mod n là một số nguyên g sao cho mọi số nguyên tương đối nguyên tố với n đều đồng dư với một lũy thừa của g mod n. Tức là, số nguyên g là một căn nguyên (mod n) nếu với mọi số tương đối nguyên tố với n có một số nguyên z sao cho a ≡ (g z (mod n)).

    2 là một mod gốc nguyên thủy 5, bởi vì với mọi số, một số nguyên tố tương đối đến 5 đều có một. 2 z ≡ a. Tất cả các số tương đối nguyên tố đến 5 là 1, 2, 3, 4 và mỗi số này (mod 5) là chính nó (ví dụ 2 (mod 5) = 2).

    4 không phải là một mod gốc nguyên thủy 5, bởi vì với mọi số tương đối nguyên tố đến 5 (một lần nữa: 1, 2, 3, 4) thì không có lũy thừa nào của 4 là đồng dư. Sức mạnh của 4 (mod 5) chỉ đồng dư với 1 hoặc 4. Không có sức mạnh nào của 4 đồng dư với 2 hoặc 3.

    Khi các gốc nguyên thủy tồn tại, thường rất thuận tiện để sử dụng chúng trong các chứng minh và các cấu trúc rõ ràng, ví dụ, nếu p là một số nguyên tố lẻ và g là một căn nguyên nguyên thủy mod p, thì phần dư bậc hai mod p chính xác là lũy thừa chẵn của căn nguyên sơ. . Các gốc nguyên thủy cũng rất quan trọng trong các ứng dụng mật mã liên quan đến vấn đề log rời rạc, đáng chú ý nhất là giao thức trao đổi khóa Diffie-Hellman.

    Thuật ngữ và một định nghĩa chính thức

    Vì vậy, Z *NS có φ (n) phần tử, trong đó φ là hàm trọng tâm của Euler.

    MỘT gốc nguyên thủy mod n là một phần tử g ∈ Z *NS mà quyền hạn tạo ra tất cả Z *NS. Nghĩa là, mọi phần tử b ∈ Z *NS có thể được viết dưới dạng g x mod n, với một số nguyên x.

    Bối cảnh và động lực

    Bộ có một thuộc tính quan trọng: đó là đóng theo mod nhân n. Đó là, nếu và c là số nguyên dương nhỏ hơn n đồng dư với ab mod n, khi đó cũng. Điều này là do ab và n không có nhân tử chung (bằng cách tính thừa số duy nhất), và do đó c và n cũng không có nhân tử chung (vì nếu d | c và d | n thì d | ab cũng vậy, vì ab = c + nx một số nguyên x)

    Thuộc tính này, cùng với các thuộc tính cơ bản khác của phép nhân mod n, ngụ ý rằng đó là một nhóm dưới phép nhân.

    Đối với bất kỳ phần tử a ∈ Z *NS, hãy xem xét chuỗi các quyền hạn của nó . Tất cả các lũy thừa của a đều nằm trong tập hợp hữu hạn , vì vậy chuỗi lũy thừa a cuối cùng lặp lại. Trên thực tế, định lý Euler ngụ ý rằng nó lặp lại với chu kỳ

    Vì vậy, một đặc điểm khác của rễ nguyên sinh về trình tự này là: Rễ nguyên thủy là phần tử mà dãy lũy thừa của a có tối thiểu giai đoạn = Stage

    Các lũy thừa của 1 là 1,1,1. Thứ tự của 1 là 1.

    Các lũy thừa của 2 là 2,4,8,7,5,1. Thứ tự của 2 là 6.

    Các lũy thừa của 4 là 4,7,1. Thứ tự của 4 là 3.

    Các lũy thừa của 5 là 5,7,8,4,2,1. Thứ tự của 5 là 6.

    Các lũy thừa của 7 là 7,4,1. Thứ tự của 7 là 3.

    Các lũy thừa của 8 là 8,1. Thứ tự của 8 là 2.

    Vì vậy, các gốc nguyên thủy mod 9 là 2 và 5.

    Sự tồn tại của rễ nguyên thủy

    Các gốc nguyên thủy không nhất thiết tồn tại mod n với n bất kỳ. Đây là một phân loại đầy đủ:

    Có các nghiệm nguyên mod n nếu và chỉ khi n = 1,2,4, p k hoặc 2p k trong đó p là số nguyên tố lẻ.

    Tìm nguồn gốc nguyên thủy

    Việc chứng minh định lý (một phần được trình bày dưới đây) về cơ bản là không mang tính xây dựng: nghĩa là nó không đưa ra một cách hiệu quả để tìm một căn nguyên thủy khi nó tồn tại. Một khi một gốc nguyên thủy g đã được tìm thấy, những cái còn lại rất dễ xây dựng: chỉ cần lấy lũy thừa g a trong đó a là tương đối nguyên tố.

    Có một số trường hợp đặc biệt khi tìm thấy chúng sẽ dễ dàng hơn, ví dụ:

    Giả sử p là số nguyên tố sao cho 2p + 1 cũng là số nguyên tố. (P như vậy được gọi là Số nguyên tố Sophie Germain.) Chứng tỏ rằng nếu p ≡ 1 mod 4 thì 2 là một nguyên hàm mod 2p +1.

    Dung dịch: Vấn đề là danh sách các thứ tự có thể có của các phần tử của rất ngắn: thứ tự của 2 phép chia vì vậy nó là một trong hai Nó không thể là 1 hoặc 2 nên chúng ta chỉ cần loại trừ P. Nhưng là biểu tượng Legendre, đây là tiêu chí của Euler. But by the second supplement to quadratic reciprocity,

    So the only remaining possibility is that the order of 2 mod 2p +1 is 2p.

    For instance, this shows that 2 is a primitive root mod 83.

    Các ứng dụng

    When there is a primitive root g mod n, the elements of Z*NS can be written as Multiplying two elements corresponds to adding their exponents mod That is, the multiplicative arithmetic in Z*NS reduces to additive arithmetic in

    Let k be an integer and p an odd prime number. How many nonzero kth powers are there mod p?

    The question certainly depends on the relationship between k and p. When k = 2 the answer is p-1/2 (see quadratic residues), but when k = p - 1 the answer is 1 (by Fermat's little theorem).

    As an illustration, take Then it's easy to check that g = 2 is a primitive root mod p. The ninth powers mod p are but we can consider the exponents mod 12 because So we get

    so there are four 9th powers mod 13. The exponents are multiples of 3, which is gcd. (9,13 -1). There are 13 - 1/3 = 4 of these.

    In general, since every nonzero element of ZP can be written as g a mod p for some integer x, the equation x k ≡ y mod p can be rewritten mod p. Because g is a primitive root, this happens if and only if

    So the question becomes: as a ranges over Zp-1, how many values can ak mod p-1 take on? In fact, the extended Euclidean algorithm implies that is the set of multiples of gcd

    There are exactly

    such values, so this is the answer.

    Here is another problem where it can help to write the elements of Z*P as powers of a primitive root.

    Partial proof of the theorem

    One half of this theorem is not hard to prove: Suppose where a and b are relatively prime and > 3. Suppose x is relatively prime to ab. Then since mod a and mod b, it follows that

    Nhưng are both even, so their lcm is strictly less than their product. So the order of x is strictly less than So there is no primitive root mod ab.

    The only n that cannot be written in this way are and higher powers of 2. But for any odd x,

    which can be proved by the LTE lemma (or by induction). Từ there is no primitive root mod

    Some of the proof of the other direction can be found in the wiki on orders.


    Xem video: Cậu Bé Sao Hỏa: Thánh Nhân Sẽ Xuất Hiện Cứu Vớt Thế Giới. Bí Ẩn Lịch Sử (Tháng Giêng 2022).