Yazan : Şadi Evren ŞEKER
Bilgisayar bilimlerinin de çeşitli alanlarda kullandığı bu teorem literatürde iki farklı konu altıdan geçmektedir. Lagrange teoremini grup teorisi (group theory) altında veya sayılar teorisi (number theory) altında incelemek mümkündür. Bu yazıda bilgisayar bilimleri açısından önemli olan sayılar teorisindeki kullanımına yer verilecektir.
Lagrange Teoremi (Grup Teorisi)
Teorem tanımı itibariyle: “bir grubun, yine bu grubun herhangi bir derecesini bölebildiğini” göstermektedir.
Bir grup, sonlu sayıda eleman içeren sayı kümesi olarak düşünülebilir.
Bu tanımda grubun derecesi ile ifade edilen ise, gruptan üretilebilen dairesel alt grupların (cyclic sub groups) derecesidir. Bu durumda grubu bölen birinci derecen bir alt grup elde edilebilmesi, n. dereceden bir grup için bu işlemin en fazla n kere tekrarlanabilmesini gerektirir.
Lagrange Teoremi (Sayılar Teorisi)
Sayılar teorisindeki lagrange uygulaması, yukarıdaki grup teorisi tanımına çok benzer. Burada grup yerine bir çok terimli (polinom) alınır ve bir grubun derecesi yerine bir polinomun derecesinden bahsedilir.
Herhangi bir p asal sayısı için tanımlı olan modulo’da veya Zp olarak gösterebileceğimiz kümede, tanımlı olan n. dereceden bir f(x) çok terimli fonksiyonunun (polynomial function) sıfıra denk olmaması durumunda, verilen f(x) = 0 mod p denkleminin en fazla n çözümü bulunur.
Bu teoremin ispatı aşağıdaki şekilde yapılabilir:
Örneğin n dereceden bir polinom aşağıdaki şekilde yazılabilir:
Buradaki denklemin m adet kökü olduğunu kabul edelim. Denklemin derecesi n ve kök sayısı m olarak kabul edilirse, genelliğini kaybetmeden, m>0 için f(r)=0 sonucu veren bir r bulunabilir. Burada buluna r değeri, f polinomunun köklerinden birsidir.
Şayet polinomun köklerinden birisi (burada r) biliniyorsa,
g(x) = f(x)-f(r)
şeklinde yazılan yeni polinom, n-1. dereceden olur. Bu durumu aşağıdaki şekilde gösterebiliriz:
Buradaki g(x) polinomunun n-1 dereceden bir polinom olduğu söylenebilir. Bu yargı hem r kökünün çıkarılmış olması hem de sonucun (x – r) polinomuna bölümünden çıkarılabilir. Buradaki x-r polinomunun r değerinde bir kökü olduğunu ve f(x) polinomu n. dereceden olduğu için n kere (x-r) şeklinde (r değeri değişmekle birlikte) polinoma bölünebileceğini kabul edersek. f(x) polinomunun en fazla n adet kökü olduğu ispatlanmış olur.