Kuvvet Rezidüler ve Mertebe (Eksponent) Kavramı
Sayılar Teorisi II dersi kapsamında, yüksek mertebeden kongrüansların çözüm stratejilerini geride bıraktıktan sonra, modüler yapılardaki çözülebilirliği ve döngüsel periyotları incelediğimiz bu konuya giriş yapıyoruz.
1. . Kuvvet Rezidü Kavramı
Bir sayının belirli bir modüle göre bir tam kuvvetinin alınıp alınamayacağını ifade eden yapıya "rezidü (kalan)" denir.
Tanım: . Kuvvet Rezidü
pozitif bir tam sayı ve bir modül olsun. Eğer:
kongrüansının (denkliğinin) bir çözümü varsa, sayısına modülo 'ye göre bir . kuvvet rezidüsü denir.
Örnek: Rezidü Kavramı
denklemini inceleyelim. denediğimizde:
Denklem sağlandığı için 2 sayısı, modülo 5'e göre bir 3. kuvvet rezidüsüdür.
Rezidüler bize temelde bir denklemin kökü olup olmadığını söyler. Ancak modüler aritmetikte asıl sihir, bir sayının kuvvetlerini almaya devam ettiğimizde ortaya çıkan döngüselliktir. Sayılar sonsuza kadar büyümez, modüle ulaştığında başa sarar. İşte bu "başa sarma" noktasını ölçmek için yeni bir kavrama ihtiyacımız var.
2. Mertebe (Eksponent) Nedir?
Euler-Fermat Teoreminden biliyoruz ki; ise 'dir. Yani 'nın kuvvetlerini almaya devam ettiğimizde eninde sonunda sonucu 1 yapan bir üs (garanti olarak ) karşımıza çıkar. Peki döngüyü tamamlayıp 1 sonucunu veren en küçük üs hangisidir?
Tanım: Mertebe (Eksponent)
bir tam sayı ve olsun.
koşulunu sağlayan en küçük pozitif tam sayısına, 'nın modülo 'ye göre mertebesi (veya eksponenti) denir ve genellikle ile gösterilir.
Mertebeyi tanımladık, peki bu sayı rastgele bir değer midir? Elbette hayır. Bir sayının modüler döngü uzunluğu (mertebesi), o modülün Euler Phi değeriyle doğrudan ve kusursuz bir bölünme ilişkisi içindedir.
3. Mertebe ve Euler Phi İlişkisi
Sayılar Teorisinin en temel ve zarif ispatlarından biri olan bu ilişki, mertebenin sınırlarını kesin olarak çizer.
Teorem: Mertebe 'i Böler
bir tam sayı, ve 'nın modülo 'ye göre mertebesi olsun. Bu durumda , 'i tam böler. Notasyonla:
İspat
Bu teoremi ispatlamak için Bölme Algoritmasını kullanacağız. Elimizde iki tam sayı var: ve .
sayısını 'ye bölelim. Bu durumda, bölüm ve kalan olmak üzere şöyle bir denklem yazabiliriz:
Euler-Fermat Teoremi gereği, olduğu için şunu kesin olarak biliyoruz:
Şimdi yerine bölme algoritmasından elde ettiğimiz eşitliği yazalım:
Üslü sayıların özelliklerini kullanarak bu ifadeyi parçalayalım:
Başlangıçtaki kabulümüze göre , 'nın mertebesidir. Yani mertebe tanımı gereği 'dir. Bunu denklemde yerine koyalım:
Kritik Mantıksal Adım: Elimizde şartını sağlayan bir sayısı kaldı. Üstelik bölme algoritmasının kuralı gereği bu sayısı 'den küçüktür ().
Fakat biz 'yi, şartını sağlayan en küçük pozitif tam sayı olarak tanımlamıştık! Eğer olsaydı, 'den daha küçük pozitif bir sayı bu şartı sağlamış olurdu ki bu durum mertebe tanımıyla çelişir.
Çelişkiyi önlemenin tek yolu 'nin sıfır olmasıdır:
Kalan sıfır olduğuna göre, bölme denklemine geri dönersek:
Bu da tam olarak 'nin 'i tam böldüğü anlamına gelir.
Örnek: Mertebenin 'i Bölmesi
ve olsun. olduğu açıktır. Öncelikle 'dır.
Şimdi 2'nin modülo 7'ye göre mertebesi olan değerini bulalım. Bunun için 2'nin kuvvetlerini sırasıyla alıyoruz:
Sonucu 1 yapan en küçük pozitif üs 3 olduğu için 2'nin mertebesi 'tür.
Teoremin ifade ettiği üzere, mertebe olan 3 sayısı, değerini tam böler ().
Bu teorem sayesinde mertebenin alabileceği değerleri sınırlandırmış olduk. Peki, bir sayının kuvvetlerini alırken iki farklı üs bize aynı sonucu veriyorsa (örneğin ) bu durum üsler hakkında bize ne söyler? İşte bu nokta, mertebenin bir "periyot" olarak nasıl davrandığını gösterir.
4. Üslerin Denkliği ve Periyodiklik
İki farklı kuvvetin modüler sistemde aynı kalanı vermesi tesadüf değildir. Üslerin arasındaki fark, doğrudan sayının mertebesiyle bağlantılıdır.
Önerme: Üslerin Denkliği ve Mertebe İlişkisi
bir tam sayı, ve 'nın modülo 'ye göre mertebesi olsun. tam sayıları için bu ilişki mantıksal olarak şu şekilde ifade edilir:
İspat
İspata başlarken genelliği bozmadan olduğunu kabul edebiliriz.
Elimizdeki başlangıç denkliği:
olduğu için, 'nın herhangi bir pozitif kuvveti de ile aralarında asaldır, yani 'dir. Bu sayede her iki tarafı güvenle 'ya bölebiliriz (veya çarpımsal tersi olan ile çarpabiliriz):
Şimdi, bir önceki teoremde uyguladığımız Bölme Algoritmasını tekrar kullanalım. tam sayısını, mertebemiz olan 'ye bölelim. Bölüm ve kalan olmak üzere:
Bu eşitliği modüler denklemimizde yerine yazalım:
Üslü sayıların özellikleriyle parçalayalım:
Mertebe tanımı gereği 'dir. Yerine koyduğumuzda:
Kritik Mantıksal Adım: Yine aynı çelişki argümanına ulaştık. Elimizde var ve kalan olduğu için şartını sağlıyor. Ancak , bu denkliği sağlayan en küçük pozitif tam sayıydı! Eğer olsaydı, mertebe tanımı çökerdi.
Bu çelişkiden kaçınmanın tek yolu kalanın sıfır olmasıdır:
Kalan sıfır olduğuna göre bölme algoritmamıza geri dönersek:
Bu da tam olarak 'nin farkını tam böldüğü anlamına gelir.
Örnek: Üslerin Denkliği ve Mertebe İlişkisi
Bir önceki örnekten devam edelim: Modülümüz , sayımız ve bu sayının mertebesi 'tür. Denklemdeki üsler olarak ve seçelim.
Üslerin modülo 7'deki değerlerini hesaplarsak:
Görüldüğü üzere denkliği kusursuz bir şekilde sağlanmaktadır.
Önermenin ifade ettiği kurala göre; mertebemiz olan , üslerin farkı olan sayısını tam bölmelidir. Gerçekten de 'dır.
Şimdiye kadar hep saf bir tabanının mertebesiyle ilgilendik. Pratik problemlerde ise çoğu zaman, mertebesini zaten bildiğimiz bir sayının belli bir kuvvetinin (örneğin ) mertebesini hesaplamamız istenir. Her defasında tek tek kuvvet alarak döngüyü baştan hesaplamak yerine, aşağıdaki teorem sayesinde tek bir formülle sonuca ulaşabiliriz.
5. Bir Kuvvetin Mertebesini Hesaplama
Eğer bir tabanın mertebesini biliyorsanız, o tabandan türetilmiş herhangi bir kuvvetin mertebesini de zahmetsizce bulabilirsiniz.
Teorem: Bir Kuvvetin Mertebesi
bir tam sayı, ve olmak üzere, 'nın modülo 'ye göre mertebesi olsun. Bu durumda, tam sayısının modülo 'ye göre mertebesi şu formülle hesaplanır:
İspat
olduğundan, 'dir.
tam sayısının modülo 'ye göre mertebesi olsun (). Mertebe tanımı gereği:
Bir önceki önermeden biliyoruz ki, eğer bir kuvvet 1'e denkse, tabanın mertebesi o kuvveti tam böler. 'nın mertebesi olduğuna göre:
Bölünebilme özelliğini kullanarak her iki tarafı değerine bölelim:
Biliyoruz ki, bir sayıyı en büyük ortak bölenine böldüğümüzde elde edilen bölümler her zaman aralarında asaldır:
Aritmetiğin Esas Yardımcı Teoremi (Öklid Lemması) gereği; eğer bir tam sayı bir çarpımı tam bölüyorsa ve çarpanlardan biriyle aralarında asalsa, diğer çarpanı tam bölmek zorundadır. Bu nedenle:
Öte yandan, 'nın 'nci kuvvetini alalım:
'nın mertebesi olduğundan 'dir. Yerine yazarsak:
Yani, 'nın 'nci kuvveti 1'e denktir. Mertebenin tanımı ve bir önceki önerme gereği, 'nın mertebesi olan , 1 sonucunu veren her kuvveti tam bölmek zorundadır:
Hem hem de pozitif tam sayılar olduğundan, ve durumlarının aynı anda sağlanabilmesi için bu iki ifadenin birbirine eşit olması zorunludur:
Örnek: Bir Kuvvetin Mertebesini Bulma
ve olsun. 'dir.
Hesaplamalar yapıldığında olduğu ve daha küçük bir kuvvette 1 sonucuna ulaşılamadığı görülür. Yani 2'nin modülo 11'e göre mertebesi 'dur.
Şimdi, tabanımızın . kuvveti olan sayısının mertebesini arayalım. Teoreme göre bu yeni sayının mertebesi şu formülle bulunur:
Sağlamasını yapmak için elde ettiğimiz sayının (yani 5'in) modülo 11'deki kuvvetlerine bakalım:
Görüldüğü üzere, 'ün (yani 5'in) mertebesi gerçekten de formülün verdiği gibi tam olarak 5'tir.
6. Primitif (İlkel) Kök Kavramı
Tanım: Primitif Kök
bir tam sayı ve olsun. Eğer 'nın modülo 'ye göre mertebesi tam olarak ise, 'ya modülo 'ye göre bir primitif kök (ilkel kök) denir.
Her modül değerinin bir primitif kökü olmak zorunda değildir. Hangi modüllerin primitif kök barındırdığı, Sayılar Teorisinin ünlü ve kapsamlı teoremlerinden biriyle kesin olarak sınıflandırılmıştır.
Teorem: Primitif Köklerin Varlığı
bir tam sayı olsun. Modülo 'ye göre bir primitif kökün var olabilmesi için gerek ve yeter şart 'nin aşağıdaki formlardan birinde olmasıdır:
Burada herhangi bir tek asal sayı ve herhangi bir pozitif tam sayıdır. 'nin başka hiçbir değeri için modülo 'ye göre primitif kök yoktur.
Örnek: Primitif Kökün Varlığı ve Yokluğu
1. Primitif Kökü Olan Bir Modül (): asaldır ( formuna uyar). 'dır. Acaba bir primitif kök müdür? 3'ün modülo 7'ye göre kuvvetlerine bakalım:
Görüldüğü üzere, 1 sonucunu veren en küçük pozitif üs 6'dır. Yani 3'ün mertebesi tam olarak 'ya eşittir. Bu nedenle 3, modülo 7'ye göre bir primitif köktür.
2. Primitif Kökü Olmayan Bir Modül (): sayısını inceleyelim. olduğundan, varlık teoreminin izin verdiği kümelerinden hiçbirine uymaz. 'tür ve 8 ile aralarında asal sayılar 'dir. Bu sayıların kuvvetlerini alırsak:
Görüldüğü üzere hiçbir elemanın mertebesi 'e ulaşamaz (maksimum mertebe 2'de kalır). Bu nedenle modülo 8'in hiçbir primitif kökü yoktur.
Eğer elimizde bir primitif kök varsa, bu kök o modüldeki bütün çarpımsal yapıyı tek başına üretebilme gücüne sahiptir. Aşağıdaki teorem, primitif köklerin bu "üretici" gücünü ve üslerle olan kusursuz ilişkisini gösterir.
Teorem: Primitif Köklerin Özellikleri
, modülo 'ye göre bir primitif kök olsun. Bu durumda aşağıdaki özellikler sağlanır:
- Herhangi tam sayıları için:
- Herhangi tam sayısı için:
- tam sayıları, modülo 'ye göre bir asal kalanlar sistemi oluşturur.
İspat
1) Birinci Özelliğin İspatı:
Gereklilik (): Kabul edelim ki olsun. , modülo 'ye göre primitif kök olduğundan 'dir ve mertebesi tanım gereği 'dir. Önceki önermemizden (Üslerin Denkliği ve Mertebe İlişkisi) biliyoruz ki, eğer iki kuvvet birbirine denkse, tabanın mertebesi bu üslerin farkını tam böler. Mertebe olduğuna göre:
Yeterlilik (): Kabul edelim ki olsun. Bu durumda bölünebilme tanımı gereği, olacak şekilde bir tam sayısı vardır. Eşitliği üslü ifadeye taşırsak:
Euler-Fermat Teoremi gereği olduğundan 'dir. Yerine yazarsak:
Böylece birinci kısmın ispatı tamamlanır.
2) İkinci Özelliğin İspatı: Birinci ispatta alırsak:
ve demek demektir. Dolayısıyla:
3) Üçüncü Özelliğin İspatı:, modülo 'ye göre primitif kök olduğundan 'dir. Dolayısıyla 'nın tüm pozitif kuvvetleri de ile aralarında asaldır:
Bu durum, dizisindeki her bir elemanın ile aralarında asal olduğunu gösterir. Ayrıca bu kümenin eleman sayısı tam olarak kadardır.
İspatı tamamlamak için geriye sadece bu tane elemandan hiçbir ikisinin modülo 'ye göre birbirine denk olmadığını göstermek kalıyor. Aksini varsayalım ve olmak üzere iki kuvvet denk olsun:
Birinci özellik gereği bu denkliğin sağlanması için:
olması zorunludur. Ancak ve 'nın her ikisi de ile arasında olduğundan, aralarındaki farkın mutlak değeri 'den küçüktür (). 'den küçük olup da 'e tam bölünebilen tek sayı 'dır. Bu nedenle olmak zorundadır.
Sonuç olarak, eğer ise 'dir. Bu kümedeki tüm elemanlar birbirinden farklıdır ve hepsi ile aralarında asal olduğu için bir asal kalanlar sistemi oluştururlar.
Örnek: Asal Kalanlar Sisteminin Üretilmesi
Bir önceki örnekte bulduğumuz, modülünün primitif kökü olan sayısını kullanalım. Teoremin 3. maddesine göre, 3'ün 'ya kadar olan kuvvetlerinin tüm asal kalanlar sistemini oluşturması gerekir.
Değerleri sırasıyla tekrar yazarsak:
Elde ettiğimiz sonuçların kümesi 'dir. Gördüğünüz gibi, bir primitif kök olan 3, kendisiyle çarpılmaya devam edildikçe modülo 7'de sıfır hariç tüm sayıları (asal kalanlar sistemini) tamamen ve eksiksiz bir şekilde üretmiştir. Hiçbir değer kendini tekrar etmeden tüm kümeyi taramıştır.
Primitif köklerin bu elemanlık asal kalanlar sistemini tamamen taraması özelliği, bizi modüler aritmetiğin logaritması olarak adlandırabileceğimiz muazzam bir hesaplama aracına götürür: İndeks.
7. İndeks Kavramı (Ayrık Logaritma)
Klasik cebirde logaritma nasıl ki bir üssü bulmamızı sağlıyorsa, modüler aritmetikte de "İndeks" aynı görevi üstlenir.
Tanım: İndeks (Ayrık Logaritma)
, modülo 'ye göre bir primitif kök ve , koşulunu sağlayan herhangi bir tam sayı olsun.
koşulunu sağlayan ve aralığında bulunan yegane doğal sayısına, 'nin primitif köküne göre (ve modülo 'ye göre) indeksi denir.
Örnek: İndeks (Ayrık Logaritma) Hesaplama
Modülümüz ve primitif kökümüz olsun. sayısının 3 tabanına göre indeksini arıyoruz. 'dir.
Matematiksel olarak şu soruyu soruyoruz: "3'ün modülo 7'de kaçıncı kuvveti 4'e denktir?"
Yukarıda ürettiğimiz asal kalanlar tablosuna geri dönüp bakarsak:
olduğunu görürüz.
Bu durumda, denklemi sağlayan yegane değeri 4'tür. Notasyon ile ifade edersek:
Yani 4 sayısının 3 primitif köküne göre modülo 7'deki indeksi (ayrık logaritması) 4'tür.
8. . Kuvvetten Kongrüansların Çözülebilirliği
Bir denkleminin çözümünün olup olmadığını deneme yanılma yoluyla bulmak, modül büyüdükçe imkansız hale gelir. Ancak eğer modülümüz bir asal sayı ise, primitif köklerin ve indekslerin özellikleri sayesinde bu çözülebilirliği tek bir hesaplamayla test edebiliriz.
Teorem: . Kuvvetten Kongrüanslar (Euler Kriteri Genellemesi)
bir asal sayı, pozitif bir tam sayı ve olsun. Bu durumda kongrüansı için şu iki durum geçerlidir:
- Eğer ise, kongrüansın hiçbir çözümü yoktur.
- Eğer ise, kongrüansın çözümü vardır ve modülo 'deki çözüm sayısı tam olarak tanedir.
İspat
1. Kısmın İspatı (Çözümsüzlük): Aksini varsayalım ve denklemin bir çözümü olduğunu kabul edelim. Bu durumda sağlanır. Denkliğin her iki tarafının 'inci kuvvetini alalım:
olduğundan çözüm olan da ile aralarında asaldır (). Euler-Fermat (veya Fermat'nın Küçük) Teoremi gereği 'dir. İfadeyi düzenlersek:
O halde, olması zorunludur. Eğer ifade 'e denk değilse, başlangıçtaki "bir çözümü vardır" varsayımımız çöker. Yani çözüm yoktur.
2. Kısmın İspatı (Çözüm Varlığı ve Sayısı): olduğunu kabul edelim. , modülo 'ye göre bir primitif kök ve 'nın bu primitif köke göre indeksi olsun. İndeks tanımı gereği:
Bunu kabulümüze yerleştirirsek:
bir primitif kök olduğundan mertebesi 'dir. Daha önce ispatladığımız "Bir kuvvet 'e denkse, tabanın mertebesi o üssü tam böler" kuralı gereği:
Sadeleştirmeleri yaparsak ifadesinin bir tam sayı olması gerektiği ortaya çıkar. Bu da demek oluyor ki:
Öte yandan, aradığımız çözümü de ile aralarında asal olacağından, bu çözümü formatında ( bir bilinmeyen üs olmak üzere) yazabiliriz. Denklemimize dönersek:
Primitif köklerin "Üslerin Denkliği" özelliğinden dolayı, bu tabanları modülo 'de (yani 'de) eşitleriz:
Bu, bilinmeyeni olan "Bir Bilinmeyenli Lineer Kongrüans" denklemidir. Linear kongrüanslar teorisinden biliyoruz ki; denkleminin çözümü olması için gerek ve yeter şart olmasıdır ve çözüm sayısı kadardır. Bizim denklemimizde , ve 'dir. adımında olduğunu kesin olarak kanıtlamıştık! Bu nedenle modülo 'de için tam olarak tane çözüm vardır. Bu çözümleri de doğrudan şeklinde ana denklemin çözümlerini üretir.
📌 Hatırlatma: Lineer Kongrüans Çözümleri
Birinci dereceden şeklindeki lineer denklemlerin çözülebilir olması için şartı sağlanmalıdır. Eğer bu şart sağlanıyorsa, denklemin modülo 'de tam olarak adet farklı çözümü vardır.
⚙️ Adım Adım Çözüm Algoritması:
Yüksek mertebeden bir modüler denklemi çözmek için, problemi karmaşık kuvvetlerden kurtarıp birinci dereceden (lineer) kongrüansa indirgeyen şu 6 adımlı algoritma uygulanır:
Çözülebilirlik Kontrolü (Euler Kriteri) Denklemin üssü olan ile modülün bir eksiği olan arasındaki en büyük ortak böleni () hesaplayın: . Ardından Euler şartının sağlanıp sağlanmadığını test edin. Eğer sonuç 'e denk değilse, denklem çözümsüzdür ve işlem burada biter. Sonuç ise, modülo 'de tam olarak adet farklı çözüm olduğu garanti edilir.
Primitif Kök () Seçimi Sistemi asıl yönetecek olan tabanı, yani modülo 'ye göre mertebesi tam olarak olan bir primitif kökünü tespit edin.
İndeks Değerini Bulma (Ayrık Logaritma) Denklemin sağ tarafındaki sayısının, bulduğunuz primitif köküne göre indeksini () hesaplayın. Matematiksel olarak, eşitliğini sağlayan üssünü bulun. Aynı mantıkla, aradığımız asıl kökünü de şeklinde tanımlayın.
Denklemi Lineer Kongrüansa Çevirme Orijinal denklemini primitif kök cinsinden yeniden yazın: . Primitif köklerin özelliklerini kullanarak tabanları atın ve üsleri modülo 'de eşitleyerek birinci dereceden (lineer) denklemi elde edin:
- Modüler Çözüm Kümesini Üretme Elde ettiğiniz lineer denklemi sadeleştirmek için, denklemin sağını, solunu ve modülünü 1. adımda bulduğumuz değerine bölün:
Bu sadeleştirilmiş denklemi sağlayan temel çözümünü bulun. Diğer adet kökü elde etmek için, modülün yeni periyodu olan değerini ilk köke ardışık olarak ekleyin:
- Orijinal Köklerine Dönüş
- adımda bulduğunuz tüm üslerini, denkleminde yerine koyun. Çıkan sonuçların modülo 'deki karşılıkları, orijinal yüksek mertebeli denkleminizin aranan kökleridir.
Örnek: denkleminin çözümü var mı, varsa çözümleri nelerdir?
💡 Çözümü Göster / Gizle
Bu yüksek mertebeli kongrüansın çözümü olup olmadığını ve varsa çözüm kümesini teorem yardımıyla bulalım. Verilenler: , , . Açıkça 'dir.
1. Adım: Çözülebilirlik Testi (Euler Kriteri Genellemesi)'tür. Test kuvvetimizi hesaplayalım:
Modüler indirgeme yapalım:
Sonuç 1 çıktığı için teoremin 2. koşulu sağlanır: Çözüm vardır ve çözüm sayısı tanedir.
2. Adım: Primitif Kök Bulma Çözümleri bulmak için modülo 17'ye göre bir primitif kök () bulmalıyız. 'dır. Mertebesi 16 olan sayıyı arıyoruz. değerini deneyelim. Mertebesi 'yi bölmek zorunda olduğundan sadece 1, 2, 4, 8 ve 16 kuvvetlerini kontrol etmek yeterlidir:
Sonucu 1 yapan en küçük üs 16 olduğu için , modülo 17'nin bir primitif köküdür.
3. Adım: İndeks Hesaplama ve Lineer Denkleme Geçiş Ana denklemdeki 13'ün, 3 primitif köküne göre indeksini () arıyoruz:
Yukarıdaki hesaplamalarımızda olduğunu bulmuştuk. Yani indeks 'tür.
Bilinmeyen 'i de olarak ifade edersek denklem şuna dönüşür:
Primitif kök kuralı gereği üsleri modülo 'de ('da) eşitleriz:
4. Adım: Çözümleri Elde Etme Lineer kongrüansı sadeleştirelim ():
Her iki tarafı 'e bölersek, modülü de 4'e bölmemiz gerekir (Modüler sadeleştirme kuralı):
Modülo 'da kalan y değerlerini (4 adet çözümümüz olacağını biliyorduk) 'ye vererek bulalım:
Bulduğumuz bu üsleri formatına yerleştirip asıl çözümleri elde edelim:
Sonuç olarak, denkleminin dört farklı çözümü vardır: .