Kuadratik (İkinci Dereceden) Rezidüler
Yüksek mertebeden kongrüansları () genel hatlarıyla inceledikten sonra, Sayılar Teorisinin en önemli özel durumu olan durumuna, yani İkinci Dereceden (Kuadratik) Kongrüanslara geçiş yapıyoruz.
Modüler aritmetikte kök bulma problemlerinin temelini oluşturan bu konu, en temelde şu soruyla başlar: Genel bir ikinci dereceden modüler denklemi nasıl çözeriz?
1. Genel İkinci Dereceden Denklemlerin İndirgenmesi
bir asal sayı ve olmak üzere, şartını sağlayan genel ikinci dereceden kongrüans şu şekildedir:
Eğer ise, bu denklem halini alır ve sadece ile değerleri denenerek çözümler kolayca bulunabilir. Dolayısıyla asıl problem, olan tek asal sayılar için çözümlerin aranmasıdır.
Aşağıdaki teorem, modül tek asal sayısı olduğunda, karmaşık görünen bu genel denklemin basit bir formatına nasıl eşdeğer olduğunu gösterir.
Teorem: Kuadratik İndirgeme ve Tam Kareye Tamamlama
bir tek asal sayı ve olmak üzere;
kongrüansını çözmek, diskriminantı olan
kongrüansını çözmeye denk (eşdeğer) bir problemdir.
İspat
diyelim.
bir tek asal sayı () ve olduğundan, sayısı da ile aralarında asaldır, yani 'dir. Bu sayede kongrüansın çözüm kümesini değiştirmeden (sadeleştirme ve genişletme kuralları gereği) her iki tarafı ile çarpabiliriz:
Şimdi bu ifadeyi klasik cebirdeki gibi "tam kareye" tamamlayalım. İlk iki terim 'nin açılımına çok benzemektedir:
Eşitliği yakalamak için denklemimize ekleyip çıkaralım:
Bu aşamada değişken değişimi yapıyoruz. diyelim. Bu durumda denklem şu sade forma dönüşür:
Birebir Eşleme (1-1 Örtenlik):
- Eğer denkleminin bir çözümü varsa, değeri de denkleminin bir çözümüdür.
- Tersine, eğer denkleminin bir çözümü varsa, olduğu için lineer kongrüansını sağlayan tek bir çözümü kesin olarak vardır ve bu , asıl denklemini sağlar.
O halde bu iki denklemin çözümleri arasında birebir bir eşleme vardır ve problemi başarıyla formatına indirgedik.
Bu indirgeme ispatı bize gösteriyor ki; ikinci dereceden karmaşık bir denklemi çözmenin bütün sırrı, aslında basit bir sayının karekökünün modüler aritmetikte var olup olmadığını bulmaktan geçmektedir. Bu da bizi Sayılar Teorisinin temel kavramlarından biriyle tanıştırır.
Örnek: İkinci Dereceden Denklemi İndirgeme ve Çözme
kongrüansını ele alalım. Burada (tek asal), , ve 'dır. koşulu sağlanmaktadır.
1. Adım: Diskriminantı () Hesaplama Teoreme göre denklemin diskriminantı:
Bu değeri modülo 11'de indirgersek:
2. Adım: İndirgenmiş Denklemi Kurma ve Çözme () Karmaşık denklemimiz artık gibi çok daha basit bir forma dönüşmüştür. Hangi sayıların karesi modülo 11'de 9'u verir?
3. Adım: Orijinal Değişkenine Dönüş Teoremdeki değişken dönüşümümüz şeklindeydi. Değerleri yerine koyarsak olur. Bulduğumuz değerlerini tek tek lineer denklemlere eşitleyelim:
Durum 1: için
(Modüler bölme için sağ tarafa 11 ekleyip sayıyı 6'nın katı yapalım: )
Durum 2: için
Sonuç olarak, başlangıçtaki kongrüansının çözüm kümesi eksiksiz bir şekilde olarak elde edilmiştir.
(Sağlama: için .)
2. Kuadratik Rezidü (Kalan) Kavramı
Bir sayının modüler aritmetikte karekökü alınabiliyorsa, o sayıya kuadratik rezidü denir.
Tanım: Kuadratik Rezidü ve Non-Rezidü
bir tam sayı ve olsun.
Eğer kongrüansının en az bir çözümü varsa, tam sayısına modülo 'ye göre bir Kuadratik Rezidü (Karesel Kalan) denir.
Eğer kongrüansının hiçbir çözümü yoksa, tam sayısına modülo 'ye göre bir Kuadratik Non-Rezidü (Karesel Olmayan Kalan) denir.
📝 Notasyon Anlaşması (Kısaltmalar)
Notlarımızın devamında ve ilerleyen teorik ispatlarda, terim tekrarlarını önlemek adına şu standart kısaltmaları kullanacağız:
- Kuadratik Rezidü yerine KR
- Kuadratik Non-Rezidü yerine KNR
Örnek: Kuadratik Rezidü Tespiti
kongrüansını inceleyelim. sayısı modülo 13'e göre bir KR midir yoksa KNR midir?
Modülo 13'teki sayıların karelerini test ettiğimizde:
olduğunu görürüz.
Denklemi sağlayan bir değeri (çözümü) bulunduğu için; 3 sayısı, modülo 13'e göre bir kuadratik rezidüdür (KR).
📝 Not: Denklik Sınıfları Üzerinde Çalışmak
Eğer , modülo 'ye göre bir kuadratik rezidü ise ve denkliği sağlanıyorsa, tam sayısı da modülo 'ye göre bir kuadratik rezidüdür.
Dolayısıyla, modülo 'ye göre kuadratik rezidüleri ararken sonsuz tam sayı kümesini değil, yalnızca modülo 'ye göre birbirine denk olmayan (farklı kalan sınıfındaki) sayıları inceleriz. Birbirine denk olan sayıların kuadratik durumlarına aynı gözle bakarız.
Örnek: Modülo 7 İçin KR ve KNR Kümeleri
Modülo 7 sistemini ele alalım. Tüm denklik sınıflarını taramak için aralığındaki sayıların karelerini incelediğimizde:
Kare alma işlemi sonucunda elde ettiğimiz birbirinden farklı kalanlar yalnızca 1, 2 ve 4'tür. 7'den küçük diğer pozitif tam sayılar (3, 5 ve 6) ise hiçbir sayının karesi olarak elde edilememiştir. Bu durumda modülo 7 için kümelerimiz kesin olarak şöyledir:
- Kuadratik Rezidüler (KR):
- Kuadratik Non-Rezidüler (KNR):