23 Yüksek Dereceden Kongrüanslar

$n \geq 1$ bir tam sayı ve

\[f(x) = c_n x^n + c_{n-1} x^{n-1} + \cdots + c_1 x + c_0\]

olsun ($c_n \neq 0$; $c_n, \dots, c_0 \in \mathbb{Z}$). Amacımız, $m \geq 2$ bir doğal sayı olmak üzere

\[f(x) \equiv 0 \pmod m\]

kongrüansını çözmektir.

Doğrudan modülo $m$’de çalışmak, $m$ büyüdükçe elverişsizleşir. Bunun yerine problemi, $m$’nin asal kuvvet çarpanlarına göre daha küçük parçalara ayırırız.

23.1 İndirgeme Teoremi

Teorem 23.1 (Asal Kuvvetlere İndirgeme) $m$ sayısının asal çarpanlara ayrılışı $m = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$ olsun. Bu durumda $f(x) \equiv 0 \pmod m$ kongrüansını çözme problemi,

\[ \left. \begin{aligned} f(x) &\equiv 0 \pmod{p_1^{e_1}} \\ f(x) &\equiv 0 \pmod{p_2^{e_2}} \\ &\;\;\vdots \\ f(x) &\equiv 0 \pmod{p_k^{e_k}} \end{aligned} \right\} \tag{$*$} \]

kongrüans sistemini çözme problemine denktir.

İspat

($\Rightarrow$) Kongrüans çözülebilirse sistem de çözülebilirdir.

$f(x) \equiv 0 \pmod m$ çözülebilir olsun; yani $f(u) \equiv 0 \pmod m$ olacak şekilde bir $u$ tam sayısı vardır. Her $i$ için $p_i^{e_i} \mid m$ olduğundan

\[f(u) \equiv 0 \pmod{p_i^{e_i}}, \qquad i = 1, \dots, k\]

bulunur. Yani $(*)$ sistemindeki her kongrüans da çözülebilirdir.

($\Leftarrow$) Sistem çözülebilirse kongrüans da çözülebilirdir.

$(*)$ sistemindeki kongrüansların hepsi çözülebilir olsun. Bu durumda

\[f(a_1) \equiv 0 \pmod{p_1^{e_1}}, \quad f(a_2) \equiv 0 \pmod{p_2^{e_2}}, \quad \dots, \quad f(a_k) \equiv 0 \pmod{p_k^{e_k}}\]

olacak şekilde $a_1, \dots, a_k$ tam sayıları vardır.

Farklı asal kuvvetler aralarında asal olduğundan

\[\left( \frac{m}{p_i^{e_i}},\; p_i^{e_i} \right) = 1, \qquad i = 1, \dots, k\]

olur. Dolayısıyla her $i$ için

\[\frac{m}{p_i^{e_i}}\, x \equiv 1 \pmod{p_i^{e_i}}\]

lineer kongrüansı çözülebilirdir; yani

\[\frac{m}{p_i^{e_i}}\, b_i \equiv 1 \pmod{p_i^{e_i}}\]

olacak şekilde $b_1, \dots, b_k$ tam sayıları vardır. Şimdi

\[u = \frac{m}{p_1^{e_1}} b_1 a_1 + \frac{m}{p_2^{e_2}} b_2 a_2 + \cdots + \frac{m}{p_k^{e_k}} b_k a_k \; \in \mathbb{Z}\]

diyelim. Toplamdaki $j \neq i$ terimlerinin her biri $p_i^{e_i}$ ile bölündüğünden, modülo $p_i^{e_i}$’de yalnızca $i$. terim kalır:

\[u \equiv \frac{m}{p_i^{e_i}} b_i a_i \equiv 1 \cdot a_i = a_i \pmod{p_i^{e_i}}\]

O hâlde $u \equiv a_1 \pmod{p_1^{e_1}}, \; \dots, \; u \equiv a_k \pmod{p_k^{e_k}}$ olur. Buradan

\[ \begin{aligned} f(u) &\equiv f(a_1) \equiv 0 \pmod{p_1^{e_1}} \\ f(u) &\equiv f(a_2) \equiv 0 \pmod{p_2^{e_2}} \\ &\;\;\vdots \\ f(u) &\equiv f(a_k) \equiv 0 \pmod{p_k^{e_k}} \end{aligned} \]

elde edilir. Bir sayı, her biri diğerleriyle aralarında asal olan sayıların hepsine bölünüyorsa en küçük ortak katlarına da bölünür:

\[f(u) \equiv 0 \pmod{\left[ p_1^{e_1}, \dots, p_k^{e_k} \right]}\]

$(p_i^{e_i}, p_j^{e_j}) = 1$ ($i \neq j$) olduğundan

\[\left[ p_1^{e_1}, \dots, p_k^{e_k} \right] = p_1^{e_1} \cdots p_k^{e_k} = m\]

olur. Sonuç olarak $f(u) \equiv 0 \pmod m$, yani asıl kongrüans da çözülebilirdir.

$\blacksquare$

Bu teoremin iki doğrudan sonucu vardır ve pratikte sürekli kullanılır.

Çözümsüzlük ölçütü

$f(x) \equiv 0 \pmod{p_i^{e_i}}$ kongrüanslarından herhangi birinin çözümü yoksa, $f(x) \equiv 0 \pmod m$ kongrüansının da çözümü yoktur.

Bu, çözümsüzlüğü göstermenin en hızlı yoludur: tek bir küçük asal kuvvet yeter.

Teorem 23.2 (Çözüm Sayısının Çarpımsallığı) $f(x) \equiv 0 \pmod{p_i^{e_i}}$ kongrüansının çözüm sayısı $N_i$ olsun ($i = 1, \dots, k$). Bu durumda $f(x) \equiv 0 \pmod m$ kongrüansının çözüm sayısı

\[N = N_1 \cdot N_2 \cdots N_k\]

dır.

23.2 Çözüm Algoritması

$m$ sayısını asal çarpanlarına ayırın: $m = p_1^{e_1} \cdots p_k^{e_k}$.
Her $p_i^{e_i}$ için $f(x) \equiv 0 \pmod{p_i^{e_i}}$ kongrüansının çözümlerini bulun. Modüller küçük olduğundan bu adım genellikle deneme yoluyla yapılabilir.
Herhangi biri çözümsüzse durun: asıl kongrüans da çözümsüzdür.
Her $i$ için $\dfrac{m}{p_i^{e_i}} b_i \equiv 1 \pmod{p_i^{e_i}}$ denkliğinden $b_i$ değerlerini hesaplayın.
Çözümleri şu formülle birleştirin: \[x \equiv \sum_{i=1}^{k} \frac{m}{p_i^{e_i}}\, b_i\, a_i \pmod m\] Burada $a_i$, $i$. alt kongrüansın çözümlerinden biridir. Tüm $(a_1, \dots, a_k)$ kombinasyonları alınarak $N_1 N_2 \cdots N_k$ çözümün hepsi elde edilir.

23.3 Çözümlü Uygulamalar

Örnek 23.1 $x^2 + x + 7 \equiv 0 \pmod{189}$ kongrüansını çözünüz.

Çözüm

$189 = 3^3 \cdot 7 = 27 \cdot 7$ olduğundan $x^2 + x + 7 \equiv 0 \pmod{27}$ ve $x^2 + x + 7 \equiv 0 \pmod 7$ kongrüanslarının çözümlerini bulalım.

Alt kongrüanslar.

Modülo $27$’de çözümler: \[x \equiv 4, \quad x \equiv 13, \quad x \equiv -5 \pmod{27}\]

(Sağlama: $4^2+4+7 = 27$, $13^2+13+7 = 189 = 7 \cdot 27$, $(-5)^2-5+7 = 27$.)

Modülo $7$’de çözümler: \[x \equiv 0, \quad x \equiv -1 \pmod 7\]

(Sağlama: $0+0+7 = 7$, $1-1+7 = 7$.)

Buna göre çözüm sayısı $N = 3 \cdot 2 = 6$ olacaktır.

Birleştirme katsayıları.

$\dfrac{189}{27} = 7$ ve $7 b_1 \equiv 1 \pmod{27}$: $7 \cdot 4 = 28 \equiv 1$ olduğundan $b_1 \equiv 4 \pmod{27}$.

$\dfrac{189}{7} = 27$ ve $27 b_2 \equiv 1 \pmod 7$: $27 \equiv -1$ olduğundan $b_2 \equiv -1 \pmod 7$.

O hâlde çözümler

\[x \equiv 7 \cdot 4 \cdot a_1 + 27 \cdot (-1) \cdot a_2 = 28 a_1 - 27 a_2 \pmod{189}\]

biçimindedir; burada $a_1 \in \{4, 13, -5\}$ ve $a_2 \in \{0, -1\}$’dir.

$a_1$	$a_2$	$28a_1 - 27a_2$	mod $189$
$4$	$0$	$112$	$112$
$4$	$-1$	$139$	$139$
$13$	$0$	$364$	$175$
$13$	$-1$	$391$	$13$
$-5$	$0$	$-140$	$49$
$-5$	$-1$	$-113$	$76$

Sonuç. $x^2 + x + 7 \equiv 0 \pmod{189}$ kongrüansının tüm çözümleri:

\[x \equiv 13, \; 49, \; 76, \; 112, \; 139, \; 175 \pmod{189}\]

(Sağlama örneği: $13^2 + 13 + 7 = 189 \equiv 0$; $49^2 + 49 + 7 = 2457 = 189 \cdot 13 \equiv 0$.)

$\blacksquare$

Örnek 23.2 $f(x) = x^3 + 19x^2 - x + 23 \equiv 0 \pmod{42}$ kongrüansını çözünüz.

Çözüm

$42 = 2 \cdot 3 \cdot 7$ olduğundan üç alt kongrüansı ayrı ayrı çözelim. Katsayıları her modülde indirgemek işi kolaylaştırır.

Modülo 2. $19 \equiv 1$, $23 \equiv 1$ olduğundan \[f(x) \equiv x^3 + x^2 + x + 1 \equiv 0 \pmod 2\] Çözüm: $x \equiv 1 \pmod 2$. (Tek çözüm, $N_1 = 1$.)

Modülo 3. $19 \equiv 1$, $23 \equiv 2$ olduğundan \[f(x) \equiv x^3 + x^2 - x + 2 \equiv 0 \pmod 3\] Çözümler: $x \equiv 1$ ve $x \equiv -1 \pmod 3$. ($N_2 = 2$.)

Modülo 7. $19 \equiv 5$, $23 \equiv 2$ olduğundan \[f(x) \equiv x^3 + 5x^2 - x + 2 \equiv 0 \pmod 7\] Çözümler: $x \equiv 1$, $x \equiv 2$ ve $x \equiv -1 \pmod 7$. ($N_3 = 3$.)

O hâlde çözüm sayısı $N = 1 \cdot 2 \cdot 3 = 6$’dır.

Birleştirme katsayıları.

$\dfrac{42}{2} = 21$ ve $21 b_1 \equiv 1 \pmod 2$: $21 \equiv 1$ olduğundan $b_1 \equiv 1 \pmod 2$.

$\dfrac{42}{3} = 14$ ve $14 b_2 \equiv 1 \pmod 3$: $14 \equiv 2$, $2 \cdot 2 = 4 \equiv 1$ olduğundan $b_2 \equiv -1 \pmod 3$.

$\dfrac{42}{7} = 6$ ve $6 b_3 \equiv 1 \pmod 7$: $6 \equiv -1$ olduğundan $b_3 \equiv -1 \pmod 7$.

Çözümler:

\[x \equiv 21 a_1 - 14 a_2 - 6 a_3 \pmod{42}\]

burada $a_1 = 1$; $a_2 \in \{1, -1\}$; $a_3 \in \{1, 2, -1\}$.

$a_1$	$a_2$	$a_3$	$21a_1 - 14a_2 - 6a_3$
$1$	$1$	$1$	$1$
$1$	$1$	$2$	$-5 \equiv 37$
$1$	$1$	$-1$	$13$
$1$	$-1$	$1$	$29$
$1$	$-1$	$2$	$23$
$1$	$-1$	$-1$	$41$

Sonuç. Kongrüansın tüm çözümleri:

\[x \equiv 1, \; 13, \; 23, \; 29, \; 37, \; 41 \pmod{42}\]

(Sağlama örneği: $x = 1$ için $1 + 19 - 1 + 23 = 42 \equiv 0$; $x = 23$ için $12167 + 10051 - 23 + 23 = 22218 = 42 \cdot 529 \equiv 0$.)

$\blacksquare$

23.4 Problemler

Alıştırma 23.1 (Kongrüansları Çözme) Aşağıdaki kongrüansları çözünüz.

a) $x^3 + 2x - 3 \equiv 0 \pmod 9$ b) $x^3 + 2x - 3 \equiv 0 \pmod 5$

c) $x^3 + 2x - 3 \equiv 0 \pmod{45}$ d) $x^3 + 4x + 8 \equiv 0 \pmod{15}$

İpucu: (c) şıkkında $45 = 9 \cdot 5$ olduğundan (a) ve (b) şıklarının sonuçlarını birleştirmeniz yeterlidir.

\(a_1\)	\(a_2\)	\(28a_1 - 27a_2\)	mod \(189\)
\(4\)	\(0\)	\(112\)	\(112\)
\(4\)	\(-1\)	\(139\)	\(139\)
\(13\)	\(0\)	\(364\)	\(175\)
\(13\)	\(-1\)	\(391\)	\(13\)
\(-5\)	\(0\)	\(-140\)	\(49\)
\(-5\)	\(-1\)	\(-113\)	\(76\)

\(a_1\)	\(a_2\)	\(a_3\)	\(21a_1 - 14a_2 - 6a_3\)
\(1\)	\(1\)	\(1\)	\(1\)
\(1\)	\(1\)	\(2\)	\(-5 \equiv 37\)
\(1\)	\(1\)	\(-1\)	\(13\)
\(1\)	\(-1\)	\(1\)	\(29\)
\(1\)	\(-1\)	\(2\)	\(23\)
\(1\)	\(-1\)	\(-1\)	\(41\)