Çin Kalan Teorisi (Chinese Remainder Theorem)

Yazan : Şadi Evren ŞEKER

Sayı teorisinde çinliler tarafından uygulanan bir yöntemdir. Tam tercümesi çin kalan teorisi olarak yapılabilir. Onluk sayı sisteminin geliştirilmediği zamanlarda büyük sayıları hatırlamak için geliştirilmiş bir yöntemdir. Basitçe bir sayının bölümlerinden kalan sayılar tutulur. Örneğin 7’ye bölümünden 4, 5’e bölümünden 3 kalan en küçük sayı 18’dir. Dolayısıyla onluk sistemin olmadığı bir sayı sisteminde 18 sayısını hatırlamak için 7,4,5 ve 3 sayılarını hatırlamak yeterlidir.

x= a mod m

x= b mod n

dolayısıyla a ≡ b mod n denilebilir ancak ve ancak n|(b-a) (n , b-a’yı tam bölerse) denilebilir.

Örneğin aşağıdaki sayısal örnek üzerinden çin hatırlatma kuramını inceleyelim:

x ≡ 2 mod 3

x ≡ 3 mod 4

x ≡ 1 mod 5

olarak sistemimiz tanımlanmış olsun.  Bu sistemin çözümü olan x değerlerini bulalmaya çalışalım. Öncelikle uzatlımış öklit algoritmasını kullanarak4x5 = 20 ‘ye göre 3’ün tersini bulalım:

(−13) × 3 + 2 × 20 = 1 , eklenen değer 2×20 = 40

Ardından diğer bir ters alma işlemini 3×5 = 15’e göre 4 için yapalım:

(−11) × 4 + 3 × 15 = 1 , eklenen değer 3×15= 45

Son olarak 3×4 = 12 için 5’in tersini alalım:

5 × 5 + (−2) × 12 = 1, eklenen değer -2×12 = -24

yukarıdaki değerler elde edildikten sonra tersi alınan değerler ile eklenen değerlerin çarpımlarını toplayalım:

ilk adımda 2 için 40 eklenmişti : 2 x40 =80

ikinci adımda 3 için 45 elkenmişti : 3 x 45 = 135

üçüncü adımda 1 için -24 eklenmişti : 1 x -24 = -24

toplam olarka 2 × 40 + 3 × 45 + 1 × (−24) = 191 bulunur.

191 mod 60 = 11 olduğuna göre sonuç kümemiz, 11 mod 60 ve bu değerin ahenk sınıfıdır.