Asal Kök

Vikipedi, özgür ansiklopedi

Bir asal kök modülü n sayılar teorisindeki modüler aritmetikten bir kavramdır. Eğer n ≥ 1 olan bir tamsayı ise, n formuna göre aralarında asal sayılar mod n'e göre çarpılarak, bir grup oluşturacak şekilde yapılan işlem,(Z/nZ)^× veya Z_n^* olarak gösterilir. Bir asal sayı için p ≥ 3 ve k ≥ 1 ise, bu grup ancak ve ancak 1, 2, 4, p^k, veya 2 p^k 'ya denktir. Bu döngüsel grubun bir üreteci asal kök modülü n veya Z_n^* 'in bir asal elemanıdır şeklinde tanımlanır.

Bir asal kök modülü n, diğer bir değişle, mod n'e göre g gibi öyle bir tamsayıdırki n'le beraber ortak çarpanı olmayan her tamsayı, g 'nin bir kuvvetine denktir. Örneğin n=14 alalım.(Z/14Z)^× 'in elemanları

1, 3, 5, 9, 11 ve 13 'ün denk sınıflarından oluşur.

mod 14'e göre 3² ≡ 9, 3³ ≡ 13, 3⁴ ≡ 11, 3⁵ ≡ 5 ve 3⁶ ≡ 1 olduğundan, 3 mod 14'e göre bir asal köktür. Mod 14 için diğer ve tek asal kök ise 5'tir.

 n     nk (mod 14) – (satırlardaki değerler döngüsel şarta bağlı olarak tekrardan sonra kesilmiştir)
 1 :   1,
 2 :   2,  4,  8 
 3 :   3,  9, 13, 11,  5,  1 
 4 :   4,  2,  8 
 5 :   5, 11, 13,  9,  3,  1
 6 :   6,  8
 7 :   7,
 8 :   8,
 9 :   9, 11,  1
10 :  10,  2,  6,  4, 12,  8
11 :  11,  9,  1
12 :  12,  4,  6,  2, 10,  8
13 :  13,  1
14 :   0,

14'le aralarında asal olan sayılar yalnızca kuvvetlerinden biri 1 (mod 14)'e ulaşan sayılardır. Bu sayıların oluşturduğu küme S = (1, 3, 9, 13, 11, 5)'dir.

Problemi f(n, k) = n^k − 1 ≡ 0 (mod 14) gibi ele alırsak, n için tasarlanan köklerin k > 0 olan kuvvetleri için bir polinom sağladığını görürüz. S kümesindeki elemanların tümü, R = {3, 5} kümesindeki sayılardan ve onların kuvvetlerinden elde edilebilir. Ama örneğin 11'den ve onun kuvvetlerinden elde edilemez (mod 14 için). S kümesi tüm kökleri içerir. R kümesi ise asal kökleri içerir. Bunların (mod 14)'e göre tüm kuvvetleri döngüsel olarak tüm kökleri elde eder.