Legendre Sembolü ve Euler Kriteri
Bir önceki bölümde bir sayının kuadratik rezidü (KR) veya kuadratik non-rezidü (KNR) olma durumunu denklemler üzerinden tanımlamıştık. Ancak sayılar büyüdükçe her defasında "Acaba modülo 'de karesi 'yı veren bir sayı var mıdır?" diye tek tek kare alarak kontrol etmek imkansızlaşır.
Bu durumu matematiksel olarak çok daha kompakt ve işlevsel bir forma sokan gösterim Legendre Sembolü'dür.
1. Legendre Sembolü Tanımı
Tanım: Legendre Sembolü
bir tek asal sayı ve herhangi bir tam sayı olsun. 'nın modülo 'ye göre kuadratik karakterini belirten Legendre Sembolü, ile gösterilir ve şu şekilde tanımlanır:
Örnek: Legendre Sembolü Değerleri
1. Kuadratik Rezidü Örneği: kongrüansının çözülebilir olduğu barizdir (Örn: ). Bu durumda , modülo 7'ye göre bir Kuadratik Rezidü (KR) olduğundan sembolün değeri 'dir:
2. Kuadratik Non-Rezidü Örneği: kongrüansını inceleyelim. Çözüm kümesinin olmadığını (3'ün KNR olduğunu) test ederek görebiliriz. Dolayısıyla sembolün değeri 'dir:
Tanımı oldukça basit görünse de, Legendre sembolünün asıl gücü sahip olduğu çarpımsal özelliklerden ve Euler Kriterinden gelir.
2. Euler Kriteri ve Sembolün Özellikleri
Aşağıdaki teorem, Legendre sembolü ile modüler üs alma işlemi arasında kusursuz bir köprü kurar. Kriptografide büyük asal sayılarla çalışırken, bir sayının KR olup olmadığını tespit etmek için çözülebilirlik testleri yapmak yerine yalnızca Euler Kriteri kullanılır.
Teorem: Euler Kriteri ve Legendre Sembolünün Özellikleri
bir tek asal sayı; ve tam sayılar ve olsun. Bu durumda aşağıdaki dört özellik geçerlidir:
- Euler Kriteri:
- Çarpımsallık Kuralı:
- Periyodiklik (Modüler Denklik): Eğer
- Özel Değerler:
İspat
1) Euler Kriterinin İspatı: Bu ispatı, daha önce işlediğimiz ". Kuvvetten Kongrüanslar (Euler Kriteri Genellemesi)" teoreminin olan özel durumu üzerinden yapacağız.
KR Durumu: modülo 'ye göre bir KR olsun. Bu durumda kongrüansın çözümü vardır. Önceki teoremimiz gereği çözüm olması için olmalıdır. Legendre tanımı gereği 'dir. Dolayısıyla:
KNR Durumu: modülo 'ye göre bir KNR olsun. Çözüm yoktur ve önceki teorem gereği 'dir. Öte yandan Fermat'nın Küçük Teoreminden dolayı 'dir. İki kare farkı ile açarsak:
asal olduğu için bu çarpanlardan birini tam bölmek zorundadır. olduğunu bildiğimizden birinci çarpanı bölemez. O halde mecburen ikinci çarpanı böler:
Legendre tanımı gereği KNR için 'dir. Sonuç olarak yine eşitlik sağlanır:
2) Çarpımsallık Kuralının İspatı: Euler kriterini (1. kuralı) yerine alarak yazalım:
Yine Euler kriterinden ve olduğunu biliyoruz. Yerlerine yazarsak:
Sembollerin alabileceği değerler yalnızca ve 'dir. tek asal sayı () olduğu için modülo 'de 'dir. Modüler denklikteki değerler ancak tam olarak birbirine eşitlerse denk olabilirler. Dolayısıyla:
3) Periyodikliğin İspatı: Kabul edelim ki olsun. Her iki tarafın 'inci kuvvetini alırsak:
Euler kriteri gereği bu kuvvetler Legendre sembollerine denktir:
İkinci ispatta vurguladığımız mantıkla, sadece olabilen bu sembollerin modülo 'de denk olması, birbirlerine birebir eşit olduklarını kanıtlar.
4) Özel Değerlerin İspatı:
- için Euler Kriterini uygularsak:
- Çarpımsallık özelliğini kullanarak (Teorem 2):
- için Euler Kriterini uygularsak, Sayılar Teorisinde ve Soyut Cebirde çok sık karşılaşacağımız o meşhur özdeşliği elde ederiz:Değerler aralığında olduğu için eşitlik kesindir:
3. İnteraktif Legendre Hesaplayıcısı
Legendre sembolünün tanımını ve özelliklerini öğrendikten sonra, farklı ve değerleri için sembolün nasıl davrandığını gözlemlemek faydalı olacaktır. Aşağıdaki interaktif hesaplayıcı, herhangi bir ve tek asal değeri için 'nın değerini hızlıca hesaplamanıza olanak tanır.