Sayılar teorisi-ilkel kök

Question

13 modülüne göre kaç tane ilkel kök vardır?

her yerde "13 modülüne göre 4 tane ilkel kök vardır bunlar 2,6,7,11 dir" olarak yazılıp bırakılmış ama biz bu ilkel kökleri nasıl bulabiliriz? 2016 yılında da 41 için sorulmuş ama cevaplanmamış bu soru bugün yeniden gün yüzüne çıkmış olup bilgisi olanların paylaşıp yol göstermesi beklenmektedir.

Comments

Sonlu bir cismin, 0 dan farklı elemanlarının, çarpma işlemin  göre oluşturduğu grup hakkında bir şey biliyor musun?

---

hocam henüz soyut cebir dersini almadım 2.sınıf sayılar teorisi dersi altında euler $\phi$ fonksiyonu ve indisler yardımıyla çözümü anlayabilirim

---

$p$ bir asal sayı ise $\mathbb{Z}_p$ den $\bar{0}$ ı(0 ın sınıfını) atarsak geri kalanlar çarpma işlemi ile (abelyen=değişmeli) bir grup olur.

İlkel kökler bu grubun üreteçleridir.

Bu grubun yapısını bilirsek (ki biliniyor:bunu sormuştum)  ilkel köklerin sayısı çok kolay bulunuyor.

---

hocam özür dileyerek anlamadığımı belirtmek isterim aslında ilkel köklerin sayısını bulabiliyorum şöyle ki

$p=13$ asal olduğundan p modülüne göre $\phi(p-1)=\phi(13-1)=\phi(12)=\phi(2^2)\phi(3)=4$ olur.Ve bu köklerin bir takım kaynaklarda 2,6,7 ve 11 olduğu ifade edilmiş.Peki bu kökleri bulurken tek tek 2 den başlayıp 13 e kadar bütün sayıların 13 modülüne göre kuvvetlerinin kongrüansını mı incelemem gerekiyor.Yani

$2^1\equiv2\;\;mod13\\2^2\equiv4\;\;mod13\\2^3\equiv8\;\;mod13\\...\\...\\2^{11}\equiv7\;\;mod13$

bu şekilde 2 den başlayarak 13 e kadar olan sayıların 13 e kadar olan kuvvetlerini incelemek çok zor olsa gerek benim burada 2,6,7 ve 11 köklerini bulabilmemin daha pratik yolu nedir?

---

Birini bulduktan sonra diğerlerini bulmak kolay.

Answer 1

Bir cismin sonlu her altgrubu döngüseldir. 13 asal olduğundan $\mathbb{Z}/13\mathbb{Z}$ bir cisimdir. Demek ki $(\mathbb{Z}/13\mathbb{Z})^\star$ (0'dan farklı elemanlar kümesi) 12 elemanlı döngüsel bir gruptur, yani $\mathbb{Z}/12\mathbb{Z}$'ye izomorftur. Demek ki sorunuz aslında $\mathbb{Z}/12\mathbb{Z}$ grubunun kaç tane üreteci olduğu, bir başka deyişle 12'ye asal 12'den küçükeşit doğal sayı sayısı, namıdiğer Euler $\varphi$ fonksiyonunun 12'de aldığı değer. Bu da yukarıdaki yorumlardan anlaşılacağı üzere 4'tür. Demek ki $\mathbb{Z}/13\mathbb{Z}$ cisminde çarpımsal derecesi 12 olan 4 eleman vardır.

Üreteçleri bulmaya gelince... Birini bulsak diğerlerini de bulabiliriz: Biri $\alpha$ ise, diğerleri $\alpha$'yı 12'ye asal sayıların kuvvetlerini alarak buluruz: $\alpha$, $\alpha^5$, $\alpha^7$, $\alpha^{11}$. Üreteçlerden birini bulmak için şöyle yapılabilir: Bir $x$ al. Eğer $x^2 \neq -1$ ama $x^6 = -1$ ise, $x$'in mertebesi (ya da derecesi) 12 olmak zorundadır.

Genel olarak, asal bir $p$ için, $(\mathbb Z/p\mathbb Z)^\star$ grubunun bir üretecini bulmanın çok kısa bir yolu bilinmiyor. Bkz. https://en.wikipedia.org/wiki/Primitive_root_modulo_n#Finding_primitive_roots