Jacobi Sembolü
Legendre Sembolü yalnızca tek asal modüller için tanımlıydı. Ancak pratikte ve ileri düzey kriptografik algoritmalarda, asal çarpanlarına ayrılmamış büyük kompozit (asal olmayan) sayılarla çalışmamız gerekir. Carl Gustav Jacob Jacobi, Legendre sembolünün özelliklerini kullanarak bu kavramı tüm tek tam sayılara genelleştirmiştir.
1. Jacobi Sembolünün Tanımı
Tanım: Jacobi Sembolü
bir tam sayı ve bir tek tam sayı olsun. kabul edelim.
Eğer sayısının asal çarpanlarına ayrılmış hali ('ler tek asal sayılar) ise, 'nin 'ya göre Jacobi Sembolü şu şekilde tanımlanır:
(Not: Buradaki asal sayılarının birbirinden farklı olması gerekmez. Aynı asal çarpandan birden fazla varsa, çarpımda o kadar kez tekrar edilir.)
Bu tanımdan yola çıkarak Jacobi sembolünün doğası hakkında üç temel çıkarım (not) elde ederiz:
- Eğer tanımdaki sayısı zaten bir tek asal sayı ise, Jacobi Sembolü doğrudan Legendre Sembolü ile çakışır (ikisi aynı şey olur).
- Sağ taraftaki Legendre sembollerinin her biri yalnızca değerlerini alabildiğinden, Jacobi Sembolünün de alabileceği değerler yalnızca veya 'dir.
⚠️ DİKKAT: Jacobi Sembolünün Tuzağı
Jacobi sembolü, Legendre sembolünün görünümünü taklit etse de "çözülebilirlik" konusunda aynı garantiyi vermez!
- Eğer ise, kongrüansının çözümü kesinlikle yoktur. (, modülo 'ya göre bir KNR'dir.)
- Ancak olması, denklemin çözülebilir olduğunu GARANTİ ETMEZ. Örnek: Jacobi sembolünü inceleyelim. olduğundan:
Sembolün değeri çıkmasına rağmen, kongrüansının hiçbir tam sayı çözümü yoktur! Çözümün olması için sağ taraftaki tüm Legendre sembollerinin ayrı ayrı olması gerekir.
2. Jacobi Sembolünün Temel Özellikleri
Jacobi sembolü, Legendre sembolünün sahip olduğu tüm o muazzam çarpımsal özellikleri aynen korur.
Teorem: Jacobi Sembolünün Cebirsel Özellikleri
ve tek tam sayılar; ve tam sayılar olsun. koşulu altında aşağıdaki özellikler geçerlidir:
- Eğer ise,
İspat
ve sayılarını tek asal çarpanlarına ayıralım: ve olsun.
1) Birinci Özelliğin İspatı: Sol tarafı Jacobi tanımına göre açalım:
Bu çarpım, sayısının tüm asal çarpanlarının Legendre sembollerinin yan yana çarpımıdır. Dolayısıyla sağ tarafa, yani ifadesine eşittir.
2) İkinci Özelliğin İspatı:
Terimleri aynı tabanlara (aynı 'lere) göre gruplayalım:
Legendre sembolünün çarpımsallık özelliğinden (Teorem 2):
3) Üçüncü Özelliğin İspatı: İkinci özelliği kullanarak: Birinci özelliği kullanarak:
4) Dördüncü Özelliğin İspatı: İlk 3 özelliğin doğrudan birleştirilmesidir:
5) Beşinci Özelliğin İspatı: Eğer ise, modüler aritmetik kuralı gereği 'nun her bir asal çarpanı için de geçerlidir. Legendre sembolü modüler denkliği koruduğundan:
Tüm 'ler için bu eşitlik sağlandığından çarpımları da birbirine eşit olur:
3. Jacobi Sembolü İçin Özel Değerler
Jacobi sembolü, daha önce Euler Kriteri ve Gauss Lemması ile asal modüller için bulduğumuz ve 'nin karesel karakteri formüllerini birebir aynı şekilde korur. Ancak ispatı, asal çarpanlar üzerinde çok zarif bir modüler tümevarım (indüksiyon) gerektirir.
Teorem: Jacobi Sembolünde Özel Değerler ( ve )
bir tek tam sayı olsun. Bu durumda:
İspat
şeklinde tek asal çarpanlarına ayrılmış olsun.
1) Birinci Formülün İspatı: Jacobi tanımını kullanarak sol tarafı açalım:
'ler asal olduğu için Legendre'nin özel formülünü kullanabiliriz:
Yardımcı Cebirsel Gerçek: ve iki tek tam sayı olsun.
ve tek sayı oldukları için ve çift sayıdır. İki çift sayının çarpımı 4'ün katıdır. Bu ifadeyi 2'ye böldüğümüzde sonuç kesinlikle 2'nin bir katı (çift sayı) olur. O halde modülo 2'de bu fark 'a denktir:
Bu mantığı indüksiyon yöntemiyle tüm 'lere genellersek:
Modülo 2'deki denklik, 'in üssündeki çiftlik/teklik durumunu (işareti) değiştirmeyeceğinden, denklemindeki toplamı doğrudan bu sonuca eşitleyebiliriz:
2) İkinci Formülün İspatı: Yine Jacobi tanımını kullanarak sol tarafı açalım:
Yardımcı Cebirsel Gerçek: ve iki tek tam sayı olsun.
Her tek sayının karesi modülo 8'de 1'e denktir. Yani ve sayıları 8'in katlarıdır ( ve ). Dolayısıyla bu çarpım 64'ün katı olur, 8'e böldüğümüzde ise sonuç hala çift sayı olur (). O halde:
Bu mantığı yine indüksiyonla tüm 'lere uygularsak:
Bu sonucu denklemindeki üsse yazdığımızda ispat tamamlanır:
4. Jacobi Sembolü İçin Kuadratik Resiprosite Teoremi
Legendre sembolü için ispatladığımız "Altın Teorem" (Karşılıklılık), Jacobi sembolü için de birebir aynı formda geçerlidir. Bu teorem, devasa kompozit sayılarla çalışırken asal çarpanlara ayırma zahmetinden kurtulup doğrudan "takla attırma" (ters çevirme) işlemi yapmamıza olanak tanır.
Teorem: Jacobi Sembolü İçin Karşılıklılık Teoremi
ve iki tek tam sayı ve olsun. Bu durumda:
eşitliği sağlanır.
İspat
ve tek tam sayılarını asal çarpanlarına ayıralım: ve ( ve 'ler tek asal sayılar).
Jacobi sembolünün tanımı ve çarpımsallık özelliğinden (Teorem 2):
Buradaki sembolleri, tabanlar asal olduğu için doğrudan Legendre sembolleridir. Bu yüzden onlara klasik Kuadratik Resiprosite Teoremini uygulayabiliriz:
Bu eşitliği çarpım sembolünün içine yerleştirirsek:
Çarpımı iki parçaya (semboller ve işaretler) ayıralım:
Birinci köşeli parantezin içi tam olarak Jacobi sembolünün açılımıdır. İkinci kısımdaki üs toplamını ise çarpanlarına ayırabiliriz:
Bir önceki teoremin özel değerler ispatında kullandığımız o "Yardımcı Cebirsel Gerçek" (mod 2'deki denklik) gereği biliyoruz ki:
Bu denklikleri üsse yazdığımızda ve her iki tarafı ile çarptığımızda ispat tamamlanır:
5. Çözümlü Örnekler
Örnek: kongrüansının çözümü var mıdır? (Başka bir deyişle, , modülo 'ye göre bir KR midir?)
💡 Çözümü Göster / Gizle
Hatırlatma (Asallık Testi): Asal olmayan bir doğal sayısının, koşuluna uyan en az bir asal böleni vardır. Dolayısıyla, bu koşula uyan hiçbir asal sayıya bölünemeyen bir sayı kesinlikle asaldır.
Sorumuzdaki modül olan 'nin durumunu inceleyelim: olup; kontrol etmemiz gereken asallar 'dir. Bu asal sayıların hiçbiri 'yi tam bölmediğinden, bir asal sayıdır.
O halde bir tek tam sayı, bir tek asal sayı ve 'dir. Şimdi Jacobi sembolünü hesaplayalım. ( asal olduğu için, burada Jacobi sembolü ile Legendre sembolü birbiriyle çakışır ve bulacağımız sonuç bize %100 kesin bir çözülebilirlik yanıtı verir).
Jacobi Resiprosite Teoremini uygulayarak "takla" attıralım:
Üs () bir çift sayı olduğu için 'dir. İşaret değişmez:
Şimdi 'yi modülo 'e göre indirgeyelim ():
Karşımıza 2'nin karesel karakteri çıktı. Özel değer formülünü uygularsak:
Üssü hesaplayalım: . . Bu sayı bir çift sayıdır.
Sonuç: Zincirleme eşitliklerden elde edilir. Buna "Legendre sembolü gözüyle" baktığımızda ( asal olduğundan); , modülo 'ye göre kesin bir Kuadratik Rezidü'dür (KR). Dolayısıyla kongrüansı çözülebilirdir.
6. Çalışma Problemleri (Kendini Dene)
Konuyu pekiştirmek için aşağıdaki problemleri öğrendiğin Legendre/Jacobi sembolü kuralları, Euler Kriteri ve Kuadratik Resiprosite teoremlerini kullanarak çözebilirsin.
Soru 1: Aşağıdaki sembollerin değerlerini hesaplayınız.
Soru 2: Aşağıdaki kongrüansların hangileri çözülebilirdir?
- a)
- b)
- c)
- d)