Gauss Lemması ve 2'nin Karesel Karakteri
Legendre Sembolünün değerini hesaplamak için her zaman Euler Kriterine başvurmak zorunda değiliz. Carl Friedrich Gauss, modüler sistemin sadece yarısını ('den 'ye kadar olan kısmı) inceleyerek sembolün değerini veren inanılmaz zarif bir sayma yöntemi ispatlamıştır.
1. Gauss Lemması
Teorem: Gauss Lemması
bir tek asal sayı, bir tam sayı ve olsun.
tam sayılarını ile bölüp kalanları bulalım. Eğer 'den büyük olan kalanların sayısı ise:
olur.
İspatı
tam sayılarını ile bölüp kalanları bulalım. Bu kalanlar kümesini büyüklüklerine göre ikiye ayıralım:
- 'den büyük olan kalanların sayısı olsun ve bunları ile gösterelim.
- 'den küçük olan kalanların sayısı olsun ve bunları ile gösterelim.
Başlangıçtaki sayılar olduğu için modülo 'de birbirine denk olamazlar, dolayısıyla elde edilen tüm kalanlar birbirinden farklıdır. Kümenin eleman sayıları toplamı eşittir:
Kalanların sınırlarını yazarsak:
Şimdi büyük kalanları modül değerinden çıkararak yeni bir küme oluşturalım: . Bu sayılar da birbirinden farklıdır ve aralığına düşerler.
Kritik Soru: Acaba herhangi bir değeri, küçük kalanlardan bir değerine eşit olabilir mi? Aksini varsayalım ve olsun. Modüler aritmetiğe geçersek:
Başlangıçtaki tanımımız gereği ve ( olacak şekilde tam sayıları vardır).
olduğundan sadeleştirme yapabiliriz:
Ancak olduğundan, toplamları en fazla olabilir. iken bu toplam modülo 'de 'a denk olamaz. Çelişki!
Demek ki kümesi ile kümesinin hiçbir ortak elemanı yoktur. Her iki kümenin elemanları toplamı adettir ve hepsi ile arasındadır. O halde bu iki kümenin birleşimi bize tam olarak şu diziyi verir:
Bu iki kümenin tüm elemanlarını kendi aralarında çarpalım:
Şimdi bu eşitliğin modülo 'deki durumuna bakalım ( olduğundan olur):
ve 'lerin orijinal halleri 'nın kalanlarıydı. Yerlerine koyarsak:
Faktöriyelli ifade ile aralarında asal olduğu için her iki tarafı bölebiliriz:
Her iki tarafı ile çarparsak (çünkü 'dir):
Euler Kriterinden biliyoruz ki 'dir. Öyleyse:
Her iki taraf da yalnızca olabileceği ve olduğu için denklik doğrudan eşitliğe dönüşür:
Gauss Lemması, tek başına bir sayısal hesaplama yönteminden ziyade, arkasından gelecek olan devasa teoremleri kanıtlamak için bir köprüdür. Aşağıdaki teorem, Gauss Lemmasını kullanarak 'nın ve özel olarak 'nin karesel durumunu çok daha pratik bir formüle bağlar.
2. Legendre Sembolü İçin Genel Formül ve 2'nin Karesel Karakteri
Teorem: Karesel Karakterlerin Hesabı
bir tek asal sayı ve (Yani tek tam sayı ve ile aralarında asal) olsun. Bu durumda:
- Eğer ise, dir.
- dir.
(Not: sembolü, x'in tam değerini (bölümünü) ifade eder.)
İspat
1) Birinci Kısmın İspatı: olmak üzere sayılarına modülünde Bölme Algoritması uygulayalım:
Burada bölüm , tam değer fonksiyonu kullanılarak şeklinde ifade edilebilir. Denklemi yeniden yazalım:
Bu eşitliği 'den 'ye kadar toplayalım:
Kalanlar olan dizisi, Gauss Lemması ispatındaki (büyük kalanlar) ve (küçük kalanlar) dizilerinin ta kendisidir. Kalanlar toplamını ayırırsak:
Öte yandan Gauss Lemması ispatında, 'den 'ye kadar olan sayıların toplamını iki parçaya ayırmıştık:
Şimdi denkleminden denklemini taraf tarafa çıkaralım ('ler birbirini götürür):
Sol taraftaki ardişık sayıların toplam formülü 'dir. Yerine yazarsak:
Bu denklemi modülo 2'de (çiftlik-teklik) inceleyelim. tek asal sayı olduğundan 'dir. tek tam sayı kabul edildiği için çifttir, yani 'dir. Denklem şu hale gelir:
Eğer dersek, bulunur. Sonuç olarak Gauss Lemması gereği olduğundan, üslerin mod 2'deki denkliği işareti değiştirmeyeceği için:
2) İkinci Kısmın İspatı (2'nin Karesel Karakteri): Bu ispat için etiketli ana denklemimizde alıp irdeleyeceğiz. Eğer ise toplam formülündeki terimlere bakalım:
'nin alabileceği en büyük değer 'dir. O halde 'nin alabileceği en büyük değer 'dir. olduğu için kesri daima 1'den küçüktür. Dolayısıyla tam kısmı sıfırdır:
Şimdi denkleminde ve toplam yerine yazalım:
Yine bu denklemi modülo 2'de okuyalım. tek asal olduğundan 'dir:
Gauss Lemmasına geri dönersek olduğunu biliyoruz. Mod 2'deki denklik üslerde işareti etkilemediğinden:
3. Teoremlerin Uygulamaları ve Çözümlü Örnekler
İspatladığımız bu soyut teoremlerin, modüler aritmetikteki karmaşık sayıların karesel karakterini bulmak için nasıl güçlü bir araca dönüştüğünü aşağıdaki örneklerle inceleyelim.
Örnek: kongrüansının çözümünün olup olmadığını Gauss Lemması ve Euler Kriteri olmak üzere iki farklı yolla inceleyiniz.
💡 Çözümü Göster / Gizle
Çözüm: Burada (tek asal) ve 'dir. .
1. Yol (Gauss Lemması ile): Öncelikle 'dir. 22'nin 1'den 20'ye kadar olan ardışık katlarını alıp, modülo 41'deki karşılıklarına bakalım:
Bu 20 adet kalanın içinden 'ten büyük olanları saydığımızda (örneğin 22, 25, 28, 31, 34, 37, 40, 21, 24, 27, 30), toplam sayının adet olduğunu görürüz. Gauss Lemmasına göre:
Sonuç çıktığı için 22 bir KNR'dir ve denklemin çözümü yoktur.
2. Yol (Euler Kriteri ile): Aynı soruyu Euler kriteri ile çözelim. olmalıdır.
Üsleri toplayarak sonuca gidelim:
Yani . Sonuç yine (KNR) olarak bulunur.
Örnek: Euler Kriteri ile bulduğumuz özel değer formülünün doğruluğunu Gauss Lemmasını kullanarak ispatlayınız.
💡 Çözümü Göster / Gizle
Çözüm:
alalım. Gauss Lemması gereği 'in katlarını yazarsak:
Bu negatif sayıların modülo 'deki asıl kalanlarını (modül ekleyerek) bulalım:
Bu dizideki en küçük eleman olan sayısı bile değerinden büyüktür. Yani bu kalanların hepsi 'den büyüktür. Dolayısıyla büyük kalanların sayısı (), doğrudan dizinin eleman sayısına eşittir:
Gauss Lemmasına göre olduğundan ispat tamamlanır:
Örnek: kongrüansının çözülebilirliğini -toplam formülü ve Gauss Lemması olmak üzere iki yolla analiz ediniz.
💡 Çözümü Göster / Gizle
Çözüm: Verilenler: , .
1. Yol (-Toplam Formülü ile): Önceki teoremde tanımladığımız formülünü uygulayalım. .
Tam değerleri hesaplarsak: . Yani . Buradan . (Çözüm yok).
2. Yol (Gauss Lemması ile): 3'ün ilk 8 katının modülo 17'deki değerleri:
Bu sayılardan 'ten büyük olanlar yalnızca: 'tir. Toplam adet olduğu için yine bulunur.
Örnek: Legendre sembolünün özelliklerini kullanarak kongrüansının çözümünün olup olmadığını bulunuz.
💡 Çözümü Göster / Gizle
Çözüm: ve 'dir. Legendre sembolünün çarpımsallık özelliğini kullanarak sayıyı parçalayalım
Özel değer formüllerinden her iki parçayı ayrı ayrı hesaplayalım:
- . Üssü hesaplayalım: . Bu tek bir sayı olduğu için 'dir.
Bu iki sonucu çarptığımızda:
Sonuç (KNR) olduğundan denklemin çözümü yoktur.
Örnek: tek asal sayı olmak üzere, denkleminin çözülebilir olması için gerek ve yeter koşul nedir?
💡 Çözümü Göster / Gizle
Çözüm: Denklemin çözülebilmesi için 2'nin KR olması, yani olması zorunludur. 2'nin karesel karakter formülünü hatırlayalım
Bu eşitliğin çıkabilmesi için, üs olan ifadesinin çift tam sayı () olması zorunludur:
Asal sayılar analiz edildiğinde bu durumun sadece veya (yani ) formatındaki asallarda sağlandığı kesin olarak görülür.
Örnek: bir tam sayı ve olsun. Eğer , modülo 'ye göre bir Kuadratik Rezidü ise, olduğunu gösteriniz.
💡 Çözümü Göster / Gizle
Çözüm: , bir KR olduğundan denklemini sağlayan en az bir tam sayısı vardır.
olduğundan, ve dolayısıyla da modül ile aralarında asaldır ().
Kongrüansın her iki tarafının 'nci kuvvetini alalım:
ve aralarında asal olduğu için Euler Teoremi devreye girer ve iken 'dir. Yerine yazdığımızda ispat tamamlanır: