25 Asal Modüllü Kongrüanslar

Bir polinom kongrüansını çözme problemini önce asal kuvvet modüllerine, oradan da kök yükseltme yoluyla asal modüllere indirgemiştik. Zincirin son halkası, yani

\[f(x) \equiv 0 \pmod p \qquad (p \text{ asal})\]

biçimindeki kongrüanslar, aslında zincirin en düzenli halkasıdır: modül asal olunca $\mathbb{Z}_p$ bir cisim gibi davranır ve polinomların bildiğimiz cebirsel özellikleri hemen hemen olduğu gibi geçerli kalır.

Bu kongrüansın çözümleri, modülo $p$’ye göre bir $a_1, a_2, \dots, a_p$ tam kalanlar sistemi denenerek her zaman bulunabilir. Bu bölümde asıl amacımız bu aramayı kısaltmak ve çözüm sayısı hakkında bir üst sınır elde etmektir.

25.1 Dereceyi $p$’nin Altına İndirme

Modülo $p$’de $x^p$ ile $x$ aynı değeri aldığından ($u^p \equiv u$), derecesi $p$ veya daha yüksek olan bir kongrüansı her zaman daha düşük dereceli bir kongrüansla değiştirebiliriz.

Teorem 25.1 (Derece İndirgeme) $f(x)$ tam katsayılı bir polinom, $p$ bir asal sayı ve $f(x) \equiv 0 \pmod p$ kongrüansının derecesi $p$ olsun. Bu durumda aşağıdakilerden biri gerçekleşir:

ya her $x$ tam sayısı $f(x) \equiv 0 \pmod p$ kongrüansının bir çözümüdür;
ya da $g(x) \equiv 0 \pmod p$ kongrüansının derecesi $p$’den küçük, baş katsayısı modülo $p$’ye göre $1$’e kongrüan ve çözüm kümesi $f(x) \equiv 0 \pmod p$ kongrüansınınkiyle aynı olan tam katsayılı bir $g(x)$ polinomu vardır.

İspat

$f(x)$ polinomunu $x^p - x$ polinomuna bölelim. $x^p - x$ polinomunun baş katsayısı $1$ olduğundan, bölme işlemi tam katsayılar içinde yapılabilir:

\[f(x) = q(x)\,(x^p - x) + r(x)\]

Burada $q(x)$ ve $r(x)$ tam katsayılı polinomlardır; ayrıca $r(x)$ ya sıfır polinomudur ya da

\[\partial r(x) < \partial (x^p - x) = p\]

sağlanır.

Fermat teoremi gereği her $u$ tam sayısı için $u^p \equiv u \pmod p$, yani $u^p - u \equiv 0 \pmod p$’dir. O hâlde yukarıdaki eşitlikte $x = u$ yazılırsa

\[f(u) \equiv r(u) \pmod p, \qquad \forall u \in \mathbb{Z}\]

bulunur. Şimdi iki durum söz konusudur.

i) $r(x) \equiv 0$ ise. Yani $r(x)$ ya sıfır polinomudur ya da bütün katsayıları $p$ ile bölünür. Bu durumda her $u \in \mathbb{Z}$ için $r(u) \equiv 0 \pmod p$, dolayısıyla

\[f(u) \equiv 0 \pmod p, \qquad \forall u \in \mathbb{Z}\]

olur; yani her tam sayı kongrüansın bir çözümüdür.

ii) $r(x) \not\equiv 0$ ise. Yani $r(x)$ sıfır polinomundan farklıdır ve en az bir katsayısı $p$ ile bölünmez. Bu durumda $r(x)$ polinomu

\[r(x) = r_m x^m + r_{m-1}x^{m-1} + \cdots + r_1 x + r_0\]

biçimindedir; burada $r_m \not\equiv 0 \pmod p$ ve $\partial r(x) = m < p$’dir.

$(r_m, p) = 1$ olduğundan $r_m x \equiv 1 \pmod p$ kongrüansı çözülebilirdir ve bir tek çözümü vardır; bu çözüm $x \equiv b \pmod p$ olsun.

Artık üç kongrüansın çözüm kümeleri arasındaki ilişkiyi kurabiliriz:

$f(x) \equiv 0 \pmod p$ ile $r(x) \equiv 0 \pmod p$ kongrüanslarının çözümleri aynıdır (çünkü her $u$ için $f(u) \equiv r(u)$).
$(b, p) = 1$ olduğundan $r(x) \equiv 0 \pmod p$ ile $b\,r(x) \equiv 0 \pmod p$ kongrüanslarının çözümleri de aynıdır.

O hâlde aranan polinom olarak

\[g(x) = b\,r(x)\]

alınabilir: derecesi $m < p$’dir ve baş katsayısı $b\,r_m \equiv 1 \pmod p$’dir.

$\blacksquare$

Örnek 25.1 $x^7 + x^3 + 2 \equiv 0 \pmod 5$ kongrüansını, derecesi $5$’ten küçük ve baş katsayısı $1$ olan bir kongrüansa indirgeyiniz.

Çözüm

$f(x) = x^7 + x^3 + 2$ polinomunu $x^5 - x$ polinomuna bölelim:

\[x^7 + x^3 + 2 = x^2\,(x^5 - x) + \underbrace{2x^3 + 2}_{r(x)}\]

O hâlde her $u$ tam sayısı için $f(u) \equiv r(u) \pmod 5$’tir ve $\partial r(x) = 3 < 5$’tir.

Baş katsayıyı $1$ yapmak için $r_3 x \equiv 1 \pmod 5$, yani $2x \equiv 1 \pmod 5$ kongrüansını çözelim: $b \equiv 3 \pmod 5$. Buradan

\[g(x) = 3\,r(x) = 6x^3 + 6 \equiv x^3 + 1 \pmod 5\]

bulunur. Demek ki $x^7 + x^3 + 2 \equiv 0 \pmod 5$ ile $x^3 + 1 \equiv 0 \pmod 5$ kongrüanslarının çözümleri aynıdır.

Sağlama. $x^3 + 1 \equiv 0 \pmod 5$ kongrüansının tek çözümü $x \equiv 4 \pmod 5$’tir ($4^3 + 1 = 65$). Gerçekten de $4^7 + 4^3 + 2 = 16450 = 5 \cdot 3290$’dır ve $x = 0,1,2,3$ değerlerinin hiçbiri asıl kongrüansı sağlamaz.

$\blacksquare$

Pratikte ne işe yarar?

Teorem, modülo $p$’de çalışırken derecenin her zaman $p$’nin altına çekilebileceğini söyler. Bu hem elle arama alanını küçültür hem de bir sonraki teoremin vereceği “çözüm sayısı $\leq$ derece” sınırını keskinleştirir.

25.2 Çarpan Teoremi

Cebirden bilinen “kök ⟺ çarpan” ilkesi, modül asal olduğunda kongrüanslar için de geçerlidir.

Teorem 25.2 (Çarpan Teoremi) $f(x)$ tam katsayılı bir polinom, $\partial f(x) \geq 1$ ve $p$ bir asal sayı olsun. Bir $a$ tam sayısının $f(x) \equiv 0 \pmod p$ kongrüansının çözümü olması için gerek ve yeter koşul,

\[f(x) \equiv (x - a)\,\rho(x) \pmod p\]

olacak şekilde tam katsayılı bir $\rho(x)$ polinomunun var olmasıdır.

İspat

Gereklik. $a$ tam sayısı $f(x) \equiv 0 \pmod p$ kongrüansının bir çözümü olsun. $f(x)$ polinomunu $x - a$ polinomuna bölelim. $x-a$ polinomunun baş katsayısı $1$ olduğundan bölme tam katsayılar içinde yapılabilir ve kalan bir sabittir:

\[f(x) = (x-a)\,\rho(x) + r \tag{$\ast$}\]

Burada $\rho(x)$ tam katsayılı bir polinom, $r$ ise bir tam sayıdır. $(\ast)$’da $x = a$ yazılırsa $f(a) = r$ bulunur. $a$ bir çözüm olduğundan $f(a) \equiv 0 \pmod p$, yani

\[r \equiv 0 \pmod p\]

olur. Bunu $(\ast)$’da kullanırsak

\[f(x) \equiv (x-a)\,\rho(x) \pmod p\]

elde edilir.

Yeterlik. $f(x) \equiv (x-a)\rho(x) \pmod p$ olacak şekilde tam katsayılı bir $\rho(x)$ polinomu var olsun. Bu kongrüansta $x = a$ yazılırsa

\[f(a) \equiv (a-a)\,\rho(a) = 0 \pmod p\]

bulunur; yani $a$ tam sayısı $f(x) \equiv 0 \pmod p$ kongrüansının bir çözümüdür.

$\blacksquare$

25.3 Lagrange Teoremi

Artık bu bölümün ana sonucunu ispatlayabiliriz: asal modülde çözüm sayısı dereceyi aşamaz.

Teorem 25.3 (Lagrange Teoremi) $p$ bir asal sayı olmak üzere

\[f(x) = a_n x^n + a_{n-1}x^{n-1} + \cdots + a_1 x + a_0 \equiv 0 \pmod p\]

kongrüansının derecesi $n$ olsun; yani $a_n \neq 0$ ve $a_n \not\equiv 0 \pmod p$ olsun. Bu durumda kongrüansın en fazla $n$ tane çözümü vardır.

İspat

İspatı $n$ üzerinden tümevarımla yapalım.

Başlangıç adımı ($n = 1$). $a_1 x + a_0 \equiv 0 \pmod p$ kongrüansında $p \nmid a_1$, yani $(a_1, p) = 1$’dir. Birinci dereceden kongrüanslar hakkında bildiklerimize göre bu kongrüansın tam olarak bir çözümü vardır; özel olarak en fazla $1$ çözümü vardır. Teorem $n = 1$ için doğrudur.

Tümevarım hipotezi. Teoremin $n = k-1$ için doğru olduğunu kabul edelim ($k > 1$, $k \in \mathbb{N}$); yani $(k-1)$. dereceden bir $g(x) \equiv 0 \pmod p$ kongrüansının en fazla $k-1$ tane çözümü olduğunu varsayalım.

Tümevarım adımı. $f(x) \equiv 0 \pmod p$, $k$. dereceden bir kongrüans olsun. İki durum söz konusudur.

i) Kongrüansın hiç çözümü yoktur. Bu durumda ispatlanacak bir şey yoktur; $0 \leq k$ olduğundan teorem $n = k$ için doğrudur.

ii) Kongrüansın bir çözümü vardır; bu çözüm $x \equiv a \pmod p$ olsun. Teorem 25.2 gereği

\[f(x) \equiv (x-a)\,g(x) \pmod p \tag{$\ast$}\]

olacak şekilde tam katsayılı bir $g(x)$ polinomu vardır. Üstelik bu polinom, Teorem 25.2’ın ispatındaki bölme işleminin bölümüdür: $f(x)$ derecesi $k$ olan bir polinom, $x - a$ ise baş katsayısı $1$ olan birinci dereceden bir polinom olduğundan $g(x)$’in derecesi $k-1$ ve baş katsayısı $a_k$’dır. $a_k \not\equiv 0 \pmod p$ olduğundan $g(x) \equiv 0 \pmod p$ kongrüansının derecesi de $k-1$’dir.

Tümevarım hipotezine göre $g(x) \equiv 0 \pmod p$ kongrüansının en fazla $k-1$ tane çözümü vardır. Bu çözümler

\[x \equiv c_1, \quad x \equiv c_2, \quad \dots, \quad x \equiv c_r \pmod p, \qquad r \leq k-1\]

olsun.

Şimdi $d$ tam sayısı, $f(x) \equiv 0 \pmod p$ kongrüansının herhangi bir çözümü olsun; yani $f(d) \equiv 0 \pmod p$. $(\ast)$’da $x = d$ yazılırsa

\[(d - a)\,g(d) \equiv 0 \pmod p\]

bulunur. $p$ asal olduğu için bir çarpımın $p$ ile bölünmesi, çarpanlardan en az birinin $p$ ile bölünmesini gerektirir:

Eğer $g(d) \equiv 0 \pmod p$ ise, $x \equiv d \pmod p$ çözümü $c_1, \dots, c_r$ çözümlerinden biridir.
Eğer $g(d) \not\equiv 0 \pmod p$ ise, $d - a \equiv 0 \pmod p$, yani $d \equiv a \pmod p$ olur; bu çözüm $x \equiv a$ çözümüyle aynıdır.

O hâlde $f(x) \equiv 0 \pmod p$ kongrüansının çözümleri

\[x \equiv a, \quad x \equiv c_1, \quad x \equiv c_2, \quad \dots, \quad x \equiv c_r \pmod p\]

listesinden ibarettir ve çözüm sayısı en fazla $r+1$’dir. $r \leq k-1$ olduğundan

\[r + 1 \leq k\]

bulunur. Yani teorem $n = k$ için de doğrudur.

Tümevarım ilkesi gereği teorem her $n \geq 1$ doğal sayısı için doğrudur.

$\blacksquare$

Modülün asal olması şart

Lagrange teoreminin ispatında asallık iki kez kullanıldı: hem Teorem 25.2’da, hem de “$(d-a)g(d) \equiv 0$ ise çarpanlardan biri $\equiv 0$” adımında.

Modül asal değilse sonuç bozulur. Kongrüansların çözümleri bölümündeki

\[x^2 - 1 \equiv 0 \pmod 8\]

kongrüansının derecesi $2$’dir, ama $x \equiv 1, 3, 5, 7$ olmak üzere dört çözümü vardır. Benzer biçimde kök yükseltme bölümünde $x^3 + x - 19 \equiv 0 \pmod{49}$ kongrüansının derecesi $3$ iken sekiz çözümü çıkmıştı.

Bir sonraki adım

Lagrange teoremi, primitif kök teorisinin de temel taşıdır: $x^d - 1 \equiv 0 \pmod p$ kongrüansının en fazla $d$ çözümü olması, modülo $p$’de belirli mertebeden eleman sayısını sınırlar. Bunu bir sonraki bölümde kullanacağız.

25.1 Dereceyi \(p\)’nin Altına İndirme

25.2 Çarpan Teoremi

25.3 Lagrange Teoremi