Modüler aritmetiğe giriş
Herkes zaten modüler aritmetik yapar: saat 8'den 10 saat sonra saat 6'dır ve pazardan sonraki gün pazartesidir. n adımdan sonra yeniden 0'dan başlayan saymanın, kuralları ve sürprizleri olan, sayılar teorisinde ve interneti koruyan kriptografide merkezi bir yer tutan, kendine ait eksiksiz bir aritmetiği olduğu ortaya çıkar.
Kalanlar ve denklik
a'yı n'ye bölün ve yalnızca kalanı tutun: bu a mod n'dir, 0 ile n − 1 arasında bir sayı. 26 mod 7 = 5, çünkü 26 = 3 × 7 + 5. Aynı kalana sahip sayılar mod n'de aynı şekilde davranır, bu yüzden onlara denk deriz: 26 ≡ 5 ≡ −2 (mod 7). Carl Friedrich Gauss bu gösterimi 1801 tarihli Disquisitiones Arithmeticae adlı eserinde getirdi ve bu gösterim, Fermat ile Euler'in eski gözlemlerini kendine özgü bir aritmetiğe dönüştürdü. n konumlu bir saatte her tam sayı kendi kalanına düşer; tam turlar unutulur.
Toplama, çıkarma ve çarpma
Üç olağan işlem her zamanki gibi çalışır ve istediğiniz zaman mod n'ye göre indirgeyebilirsiniz: bir toplamın kalanı, kalanların toplamının kalanıdır; aynısı farklar ve çarpımlar için de geçerlidir. 37 × 48'in son basamağını bulmak için yalnızca son basamakları çarpın: 7 × 8 = 56, yani 6 ile biter. Modüler aritmetiği bilgisayarlar için bu kadar yararlı kılan budur: sayılar ne kadar büyük olursa olsun, ara değerler asla n²'yi aşmaz.
Bölme bir ters gerektirir
İstisna bölmedir. 2 × 3 ≡ 2 × 8 (mod 10), çünkü ikisi de mod 10'da 6'dır, ama 3 ile 8 farklıdır; yani 2'yi öylece sadeleştiremezsiniz. a'ya bölmek, onun tersiyle, yani a × x ≡ 1 olan x sayısıyla çarpmak demektir ve bu sayı tam olarak a ile n'nin ortak çarpanı olmadığında vardır. Onu genişletilmiş Öklid algoritması bulur: en büyük ortak bölen için Öklid'in bölme adımlarını uygular ve her adımda bir çarpanı izler; böylece kalan 1'e ulaştığında çarpan, tersin kendisidir. n asal olduğunda 0 dışındaki her sayının tersi vardır ve bölme her zaman mümkündür.
Kuvvetler, Fermat ve Euler
Kuvvetler tekrar eder. 3'ün mod 7'ye göre kuvvetlerini alın: 3, 2, 6, 4, 5, 1 ve sonra yine 3. Bu döngünün uzunluğu 3'ün mertebesidir. 1640'ta Pierre de Fermat, asal bir p için p, a'yı bölmediği sürece a^(p − 1) ≡ 1 (mod p) olduğunu fark etti; dolayısıyla her mertebe p − 1'i böler. Leonhard Euler bunu kanıtladı ve p − 1 yerine n ile aralarında asal olan değerlerin sayısını koyarak herhangi bir n'ye genişletti. Çok büyük kuvvetler ardışık kare alma ile hesaplanır: a, a², a⁴, a⁸ … her biri bir öncekinin karesidir ve mod n'ye göre indirgenir, sonra üssün ikili basamaklarına göre çarpılır.
Kontrol basamakları ve takvimler
Modüler aritmetik hataları yakalar. Bir ISBN-10'un son basamağı, on basamağın tamamının ağırlıklı toplamı 11'in katı olacak şekilde seçilir; böylece tek bir yanlış basamak da, iki komşu basamağın herhangi bir yer değiştirmesi de fark edilir. Banka kartı numaraları mod 10'a göre Luhn kontrolünü, IBAN'lar ise mod 97'ye göre bir kontrol kullanır. Takvimler mod 7 ile işler: herhangi bir tarihin haftanın hangi günü olduğu birkaç kalanla bulunabilir; sürekli takvimler ve kıyamet günü kuralı (doomsday rule) böyle çalışır.
Kriptografi
Modern kriptografi, hesaplaması kolay ama geri alınması zor modüler kuvvetler üzerine kuruludur. 1976 tarihli Diffie–Hellman anahtar değişiminde iki kişi, büyük bir asala göre mod alınmış kuvvetleri değiş tokuş ederek açık bir hat üzerinden ortak bir sırda anlaşır. 1977'de Rivest, Shamir ve Adleman tarafından yayımlanan RSA, iki büyük asalın çarpımı olan n için bir m mesajını m^e mod n olarak şifreler ve şifreyi, yalnızca bu iki asalı bilen birinin hesaplayabileceği ikinci bir d üssüyle çözer. Ders kitabı örneğinde n = 3233 = 61 × 53, e = 17 ve d = 413'tür: 65, 2790 olur ve 2790 yeniden 65 olur.
Keşfedin
30 basamağa kadar sayılar için a mod n'yi ve mod n'ye göre toplamları, farkları, çarpımları, kuvvetleri, tersleri ve bölümleri hesaplamak için modüler saati açın. Her sonuç adımlarıyla birlikte gelir: kalanlı bölme, ardışık kare almadan gelen kuvvetler ya da genişletilmiş Öklid algoritmasının tablosu. Saat, bir toplamanın sarmalından kuvvetlerin döngüsüne kadar sonuca nasıl ulaşıldığını çizer ve küçük n için işlemin tablosu tüm sonuçları bir arada gösterir.
Sık sorulan sorular
≡ sembolü ne anlama gelir?
a ≡ b (mod n), a ile b'nin n'ye bölündüğünde aynı kalanı verdiğini ya da buna denk olarak n'nin a − b'yi böldüğünü söyler. 38 ≡ 2 (mod 12), çünkü 38 − 2 = 36, 12'nin katıdır.
mod, programlamadaki % operatörüyle aynı mı?
Pozitif sayılar için evet. Negatif sayılar için C, Java ve JavaScript gibi birçok dil negatif bir kalan döndürür: orada −7 % 3, −1'dir, oysa −7 mod 3 = 2. Python'un % operatörü pozitif bir n için matematiksel kuralı izler.
Bir sayının mod n'ye göre mertebesi nedir?
a^k ≡ 1 (mod n) olan en küçük k > 0 sayısıdır. Yalnızca a ile n'nin ortak çarpanı olmadığında vardır. 2'nin mod 7'ye göre mertebesi 3'tür, çünkü 2³ = 8 ≡ 1; 3'ün mod 7'ye göre mertebesi ise 6'dır, dolayısıyla 3'ün kuvvetleri sıfır olmayan her kalanı dolaşır: 3, mod 7'ye göre bir ilkel köktür.
Modüler aritmetiği kim icat etti?
Kalanlar çok daha önce kullanılıyordu; örneğin 3. ile 5. yüzyıllar arasından kalma Çin kalan teoreminde ve Fermat ile Euler tarafından. Gauss 1801'de onu denklik gösterimiyle birlikte sistematik bir aritmetiğe dönüştürdü.
Denemeye hazır mısınız?
PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.
Modüler saati açın