7 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 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.

7.1 1. Jacobi Sembolünün Tanımı

Tanım 7.1 (Jacobi Sembolü) $P$ bir tam sayı, $Q > 1$ bir tek tam sayı ve $\gcd(P, Q) = 1$ olsun.

Eğer $Q$ sayısının asal çarpanlarına ayrılmış hâli $Q = q_1 q_2 \cdots q_s$ ise ($q_i$’ler tek asallar), $P$’nin $Q$’ya göre Jacobi sembolü şöyle tanımlanır:

\[\left( \frac{P}{Q} \right) = \left( \frac{P}{q_1} \right) \cdot \left( \frac{P}{q_2} \right) \cdots \left( \frac{P}{q_s} \right)\]

Buradaki $q_i$ asallarının birbirinden farklı olması gerekmez; aynı asal çarpandan birden fazla varsa çarpımda o kadar kez tekrar edilir.

Bu tanımdan iki temel çıkarım elde ederiz:

Eğer $Q$ zaten bir tek asal sayı ise, Jacobi sembolü doğrudan Legendre sembolüyle çakışır.
Sağ taraftaki Legendre sembollerinin her biri yalnızca $\pm 1$ alabildiğinden, Jacobi sembolünün alabileceği değerler de yalnızca $1$ veya $-1$’dir.

⚠️ 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 $\left( \frac{P}{Q} \right) = -1$ ise, $x^2 \equiv P \pmod Q$ kongrüansının çözümü kesinlikle yoktur.
Ancak $\left( \frac{P}{Q} \right) = 1$ olması, denklemin çözülebilir olduğunu garanti etmez.

Örnek: $9 = 3 \cdot 3$ olduğundan

\[\left( \frac{2}{9} \right) = \left( \frac{2}{3} \right) \cdot \left( \frac{2}{3} \right) = (-1) \cdot (-1) = 1\]

Sembolün değeri $1$ çıkmasına rağmen $x^2 \equiv 2 \pmod 9$ kongrüansının hiçbir çözümü yoktur; modülo $9$’daki kareler $\{0, 1, 4, 7\}$ kümesidir. Çözümün var olması için sağ taraftaki tüm Legendre sembollerinin ayrı ayrı $1$ olması gerekir.

7.2 2. Jacobi Sembolünün Temel Özellikleri

Jacobi sembolü, Legendre sembolünün sahip olduğu çarpımsal özellikleri aynen korur.

Teorem 7.1 (Jacobi Sembolünün Cebirsel Özellikleri) $Q > 1$ ve $Q' > 1$ tek tam sayılar; $P$ ve $P'$ tam sayılar olsun. $\gcd(PP', QQ') = 1$ koşulu altında aşağıdaki özellikler geçerlidir:

$\left( \frac{P}{Q} \right) \cdot \left( \frac{P}{Q'} \right) = \left( \frac{P}{QQ'} \right)$
$\left( \frac{P}{Q} \right) \cdot \left( \frac{P'}{Q} \right) = \left( \frac{PP'}{Q} \right)$
$\left( \frac{P^2}{Q} \right) = \left( \frac{P}{Q^2} \right) = 1$
$\left( \frac{P' P^2}{Q' Q^2} \right) = \left( \frac{P'}{Q'} \right)$
$P \equiv P' \pmod Q$ ise $\left( \frac{P}{Q} \right) = \left( \frac{P'}{Q} \right)$

İspat

$Q$ ve $Q'$ sayılarını tek asal çarpanlarına ayıralım: $Q = q_1 \cdots q_s$ ve $Q' = q'_1 \cdots q'_t$.

1) Birinci özellik. Sol tarafı Jacobi tanımına göre açalım:

\[\left( \frac{P}{Q} \right) \cdot \left( \frac{P}{Q'} \right) = \left[ \left( \frac{P}{q_1} \right) \cdots \left( \frac{P}{q_s} \right) \right] \cdot \left[ \left( \frac{P}{q'_1} \right) \cdots \left( \frac{P}{q'_t} \right) \right]\]

Bu çarpım, $QQ'$ sayısının tüm asal çarpanlarına ait Legendre sembollerinin çarpımıdır; dolayısıyla $\left( \frac{P}{QQ'} \right)$ ifadesine eşittir.

2) İkinci özellik.

\[\left( \frac{P}{Q} \right) \cdot \left( \frac{P'}{Q} \right) = \left[ \left( \frac{P}{q_1} \right) \cdots \left( \frac{P}{q_s} \right) \right] \cdot \left[ \left( \frac{P'}{q_1} \right) \cdots \left( \frac{P'}{q_s} \right) \right]\]

Terimleri aynı $q_i$’lere göre gruplayalım ve Legendre sembolünün çarpımsallık özelliğini uygulayalım:

\[= \left( \frac{PP'}{q_1} \right) \cdots \left( \frac{PP'}{q_s} \right) = \left( \frac{PP'}{Q} \right)\]

3) Üçüncü özellik. İkinci özelliği kullanarak $\left( \frac{P^2}{Q} \right) = \left( \frac{P}{Q} \right)^2 = (\pm 1)^2 = 1$; birinci özelliği kullanarak $\left( \frac{P}{Q^2} \right) = \left( \frac{P}{Q} \right)^2 = 1$.

4) Dördüncü özellik. İlk üç özelliğin doğrudan birleşimidir:

\[\left( \frac{P' P^2}{Q' Q^2} \right) = \left( \frac{P'}{Q'} \right) \cdot \underbrace{\left( \frac{P'}{Q^2} \right)}_{=1} \cdot \underbrace{\left( \frac{P^2}{Q'} \right)}_{=1} \cdot \underbrace{\left( \frac{P^2}{Q^2} \right)}_{=1} = \left( \frac{P'}{Q'} \right)\]

5) Beşinci özellik. $P \equiv P' \pmod Q$ ise, $Q$’nun her $q_i$ asal çarpanı için de $P \equiv P' \pmod{q_i}$ geçerlidir. Legendre sembolü modüler denkliği koruduğundan her $i$ için $\left( \frac{P}{q_i} \right) = \left( \frac{P'}{q_i} \right)$ olur; çarpımları da eşittir.

$\blacksquare$

7.3 3. Jacobi Sembolü İçin Özel Değerler

Jacobi sembolü, asal modüller için bulduğumuz $-1$ ve $2$’nin karesel karakteri formüllerini birebir aynı şekilde korur. Ancak ispatı, asal çarpanlar üzerinde zarif bir modüler tümevarım gerektirir.

Teorem 7.2 (Jacobi Sembolünde Özel Değerler) $Q > 1$ bir tek tam sayı olsun. Bu durumda:

$\left( \frac{-1}{Q} \right) = (-1)^{\frac{Q-1}{2}}$
$\left( \frac{2}{Q} \right) = (-1)^{\frac{Q^2-1}{8}}$

İspat

$Q = q_1 q_2 \cdots q_s$ şeklinde tek asal çarpanlarına ayrılmış olsun.

1) Birinci formülün ispatı. Jacobi tanımını kullanarak açalım:

\[\left( \frac{-1}{Q} \right) = \left( \frac{-1}{q_1} \right) \cdots \left( \frac{-1}{q_s} \right) = (-1)^{\frac{q_1-1}{2} + \cdots + \frac{q_s-1}{2}} \tag{$*$}\]

Yardımcı cebirsel gerçek. $a$ ve $b$ iki tek tam sayı olsun:

\[\frac{ab-1}{2} - \left( \frac{a-1}{2} + \frac{b-1}{2} \right) = \frac{(a-1)(b-1)}{2}\]

$a$ ve $b$ tek olduğundan $(a-1)$ ve $(b-1)$ çifttir; iki çift sayının çarpımı $4$’ün katıdır ve $2$’ye bölündüğünde sonuç yine çifttir. O hâlde modülo $2$’de bu fark sıfıra denktir:

\[\frac{ab-1}{2} \equiv \frac{a-1}{2} + \frac{b-1}{2} \pmod 2\]

Bu mantığı tümevarımla tüm $q_i$’lere genellersek:

\[\frac{q_1-1}{2} + \cdots + \frac{q_s-1}{2} \equiv \frac{q_1 \cdots q_s - 1}{2} = \frac{Q-1}{2} \pmod 2\]

Modülo $2$’deki denklik, $(-1)$’in üssündeki teklik/çiftlik durumunu değiştirmeyeceğinden $(*)$ denklemindeki toplamı bu sonuca eşitleyebiliriz.

2) İkinci formülün ispatı. Yine Jacobi tanımını açalım:

\[\left( \frac{2}{Q} \right) = \left( \frac{2}{q_1} \right) \cdots \left( \frac{2}{q_s} \right) = (-1)^{\frac{q_1^2-1}{8} + \cdots + \frac{q_s^2-1}{8}} \tag{$**$}\]

Yardımcı cebirsel gerçek. $a$ ve $b$ iki tek tam sayı olsun:

\[\frac{a^2b^2-1}{8} - \left( \frac{a^2-1}{8} + \frac{b^2-1}{8} \right) = \frac{(a^2-1)(b^2-1)}{8}\]

Her tek sayının karesi modülo $8$’de $1$’e denktir; yani $8 \mid a^2 - 1$ ve $8 \mid b^2 - 1$. Dolayısıyla çarpım $64$’ün katıdır ve $8$’e bölündüğünde sonuç hâlâ çifttir. O hâlde:

\[\frac{a^2b^2-1}{8} \equiv \frac{a^2-1}{8} + \frac{b^2-1}{8} \pmod 2\]

Bu mantığı tümevarımla tüm $q_i$’lere uygularsak:

\[\frac{q_1^2-1}{8} + \cdots + \frac{q_s^2-1}{8} \equiv \frac{(q_1 \cdots q_s)^2 - 1}{8} = \frac{Q^2-1}{8} \pmod 2\]

Bu sonucu $(**)$ denklemindeki üsse yazdığımızda ispat tamamlanır.

$\blacksquare$

7.4 4. Jacobi Sembolü İçin Karşılıklılık Teoremi

Legendre sembolü için ispatladığımız altın teorem, 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 ters çevirme işlemi yapmamıza olanak tanır — Jacobi sembolünün asıl pratik değeri buradadır.

Teorem 7.3 (Jacobi Sembolü İçin Karşılıklılık Teoremi) $P > 1$ ve $Q > 1$ iki tek tam sayı ve $\gcd(P, Q) = 1$ olsun. Bu durumda

\[\left( \frac{P}{Q} \right) \cdot \left( \frac{Q}{P} \right) = (-1)^{\frac{P-1}{2} \cdot \frac{Q-1}{2}}\]

eşitliği sağlanır.

İspat

$P$ ve $Q$ tek tam sayılarını asal çarpanlarına ayıralım: $P = p_1 \cdots p_r$ ve $Q = q_1 \cdots q_s$.

Jacobi sembolünün tanımı ve çarpımsallık özelliğinden:

\[\left( \frac{P}{Q} \right) = \prod_{j=1}^{s} \left( \frac{P}{q_j} \right) = \prod_{j=1}^{s} \prod_{i=1}^{r} \left( \frac{p_i}{q_j} \right)\]

Buradaki $\left( \frac{p_i}{q_j} \right)$ sembolleri, tabanlar asal olduğu için doğrudan Legendre sembolleridir; onlara klasik kuadratik resiprosite teoremini uygulayabiliriz:

\[\left( \frac{p_i}{q_j} \right) = \left( \frac{q_j}{p_i} \right) \cdot (-1)^{\frac{p_i-1}{2} \cdot \frac{q_j-1}{2}}\]

Bu eşitliği çarpımın içine yerleştirip sembolleri ve işaretleri ayıralım:

\[\left( \frac{P}{Q} \right) = \left[ \prod_{i=1}^{r} \prod_{j=1}^{s} \left( \frac{q_j}{p_i} \right) \right] \cdot (-1)^{\sum_{i} \sum_{j} \frac{p_i-1}{2} \cdot \frac{q_j-1}{2}}\]

Köşeli parantezin içi tam olarak $\left( \frac{Q}{P} \right)$ Jacobi sembolünün açılımıdır. Üsteki çift toplamı ise çarpanlarına ayırabiliriz:

\[\left( \frac{P}{Q} \right) = \left( \frac{Q}{P} \right) \cdot (-1)^{\left( \sum_{i} \frac{p_i-1}{2} \right) \cdot \left( \sum_{j} \frac{q_j-1}{2} \right)}\]

Bir önceki teoremde kullandığımız yardımcı cebirsel gerçek gereği:

\[\sum_{i=1}^{r} \frac{p_i-1}{2} \equiv \frac{P-1}{2} \pmod 2, \qquad \sum_{j=1}^{s} \frac{q_j-1}{2} \equiv \frac{Q-1}{2} \pmod 2\]

Bu denklikleri üsse yazıp her iki tarafı $\left( \frac{Q}{P} \right)$ ile çarptığımızda ispat tamamlanır.

$\blacksquare$

7.5 5. Çözümlü Örnek

Örnek 7.1 $x^2 \equiv 105 \pmod{317}$ kongrüansının çözümü var mıdır? Başka bir deyişle, $105$ sayısı modülo $317$’ye göre bir KR midir?

💡 Çözümü göster / gizle

Hatırlatma (asallık testi). Asal olmayan bir $t > 1$ doğal sayısının, $p \leq \sqrt{t}$ koşuluna uyan en az bir $p$ asal böleni vardır. Dolayısıyla bu koşula uyan hiçbir asala bölünemeyen bir sayı kesinlikle asaldır.

$17 < \sqrt{317} < 18$ olduğundan kontrol etmemiz gereken asallar $2, 3, 5, 7, 11, 13, 17$’dir. Bunların hiçbiri $317$’yi tam bölmediğinden $317$ bir asal sayıdır.

O hâlde $105$ tek bir tam sayı, $317$ tek bir asal ve $\gcd(105, 317) = 1$’dir. $317$ asal olduğu için Jacobi ve Legendre sembolleri burada çakışır; bulacağımız sonuç kesin bir çözülebilirlik yanıtı verir.

Jacobi karşılıklılık teoremini uygulayıp “takla” attıralım:

\[\left( \frac{105}{317} \right) \cdot \left( \frac{317}{105} \right) = (-1)^{\frac{105-1}{2} \cdot \frac{317-1}{2}} = (-1)^{52 \cdot 158}\]

Üs çift olduğundan sonuç $+1$’dir; yani işaret değişmez:

\[\left( \frac{105}{317} \right) = \left( \frac{317}{105} \right)\]

Şimdi $317$’yi modülo $105$’e indirgeyelim. $105 \cdot 3 = 315$ olduğundan $317 \equiv 2 \pmod{105}$:

\[\left( \frac{317}{105} \right) = \left( \frac{2}{105} \right)\]

Karşımıza $2$’nin karesel karakteri çıktı; özel değer formülünü uygulayalım:

\[\left( \frac{2}{105} \right) = (-1)^{\frac{105^2-1}{8}}\]

Üssü hesaplayalım: $105^2 = 11025$ ve $\tfrac{11024}{8} = 1378$. Bu çift bir sayı olduğundan:

\[\left( \frac{2}{105} \right) = 1\]

Sonuç: Zincirleme eşitliklerden $\left( \frac{105}{317} \right) = 1$ elde edilir. $317$ asal olduğundan bu, $105$’in modülo $317$’ye göre kesin bir kuadratik rezidü olduğu anlamına gelir; dolayısıyla $x^2 \equiv 105 \pmod{317}$ kongrüansı çözülebilirdir.

Sağlama (çarpanlara ayırarak). $105 = 3 \cdot 5 \cdot 7$ olduğundan:

$317 \equiv 5 \pmod{12}$ olduğundan $\left( \frac{3}{317} \right) = -1$
$317 \equiv 1 \pmod 4$ olduğundan $\left( \frac{5}{317} \right) = \left( \frac{317}{5} \right) = \left( \frac{2}{5} \right) = -1$
Benzer şekilde $\left( \frac{7}{317} \right) = \left( \frac{317}{7} \right) = \left( \frac{2}{7} \right) = +1$

Çarpım: $(-1)(-1)(+1) = 1$ ✓ İki yöntem birbirini doğrulamaktadır.

$\blacksquare$

7.6 6. Çalışma Problemleri

Konuyu pekiştirmek için aşağıdaki problemleri; öğrendiğiniz Legendre/Jacobi sembolü kuralları, Euler kriteri ve kuadratik resiprosite teoremlerini kullanarak çözebilirsiniz.

Alıştırma 7.1 (Sembol Değerleri) Aşağıdaki sembollerin değerlerini hesaplayınız:

\[\left( \frac{-23}{83} \right), \qquad \left( \frac{51}{71} \right), \qquad \left( \frac{71}{73} \right), \qquad \left( \frac{-35}{97} \right)\]

Alıştırma 7.2 (Çözülebilirlik Analizi) Aşağıdaki kongrüansların hangileri çözülebilirdir?

a) $x^2 \equiv 10 \pmod{127}$

b) $x^2 \equiv 234 \pmod{401}$

c) $x^2 \equiv -73 \pmod{143}$

d) $x^2 \equiv 45 \pmod{101}$

İpucu: $143 = 11 \cdot 13$ asal değildir; bu şıkta Jacobi sembolünün tuzağını hatırlayın.