Modüler Aritmetik Konu Anlatımı

Konu anlatımı notları

1. Modüler Aritmetiğe Giriş

   Tamsayılar kümesinde bölünebilme ilişkisi, denklik bağıntıları aracılığıyla modüler aritmetiğin temelini oluşturur. Sabit bir m pozitif tamsayısı verildiğinde, iki tamsayının m ile bölümünden kalanlar eşit ise bu iki sayı modül m'e göre birbirine denktir (kongrüanstır).

   Matematiksel olarak, a ve b tamsayıları için m sayısı $a - b$ farkını tam bölüyorsa, yani $m \mid (a - b)$ ise bu durum şu şekilde ifade edilir:

   $a \equiv b \pmod{m}$

   Kongrüans Bağıntısının Özellikleri

   Modül m üzerindeki kongrüans bağıntısı bir denklik bağıntısıdır ve şu özellikleri sağlar:

   • Yansıma: Her a tamsayısı için $a \equiv a \pmod{m}$ dir.
   • Simetri: $a \equiv b \pmod{m}$ ise $b \equiv a \pmod{m}$ dir.
   • Geçişme: $a \equiv b \pmod{m}$ ve $b \equiv c \pmod{m}$ ise $a \equiv c \pmod{m}$ dir.

   Kalan Sınıfları Kümesi ($\mathbb{Z}_m$)

   Bir m tamsayısına göre tüm tamsayılar m farklı denklik sınıfına ayrılır. Bu denklik sınıfları $\bar{a} = \{x \in \mathbb{Z} : x \equiv a \pmod{m}\}$ biçiminde tanımlanır.

   Kalan sınıfları kümesi $\mathbb{Z}_m = \{\bar{0}, \bar{1}, \bar{2}, \dots, \overline{m-1}\}$ olarak gösterilir ve üzerinde toplama ile çarpma işlemleri iyi tanımlıdır:

   • Toplama: $\bar{a} + \bar{b} = \overline{a + b}$
   • Çarpma: $\bar{a} \cdot \bar{b} = \overline{a \cdot b}$

   Aritmetik İşlemlerin Korunması

   Eğer $a \equiv b \pmod{m}$ ve $c \equiv d \pmod{m}$ ise:

   • $a + c \equiv b + d \pmod{m}$
   • $a - c \equiv b - d \pmod{m}$
   • $a \cdot c \equiv b \cdot d \pmod{m}$
   • Her k pozitif tamsayısı için $a^k \equiv b^k \pmod{m}$

   Doğrusal Kongrüans Denklemleri

   Bilinmeyen içeren en temel modüler denklem formu $ax \equiv b \pmod{m}$ şeklindedir. Bu tür denklemlerin çözümünün varlığı tamsayıların en büyük ortak bölenine (EBOB) bağlıdır.

   $d = \gcd(a, m)$ olsun:

   • Eğer d sayısı b'yi bölmüyorsa ($d \nmid b$), kongrüansın çözümü yoktur.
   • Eğer d sayısı b'yi bölüyorsa ($d \mid b$), denklemin modül m içinde tam olarak d tane birbirine denk olmayan çözümü vardır.

   Çarpımsal Ters Kavramı

   Bir a tamsayısının modül m'e göre çarpımsal tersi, $ax \equiv 1 \pmod{m}$ bağıntısını sağlayan x tamsayısıdır. Bu tersin var olabilmesi için gerek ve yeter koşul $\gcd(a, m) = 1$ olmasıdır. Bu durumda çözüm tektir ve $a^{-1} \pmod{m}$ ile gösterilir.

   Fermat ve Euler Teoremleri

   Modüler aritmetikte büyük kuvvetlerin hesaplanmasında temel teoremler kullanılır:

   • Fermat'nın Küçük Teoremi: p bir asal sayı ve a, p ile aralarında asal bir tamsayı ise, $a^{p-1} \equiv 1 \pmod{p}$ olur. Genel olarak her a için $a^p \equiv a \pmod{p}$ geçerlidir.
   • Euler Teoremi: $\phi(m)$ Euler totient fonksiyonu olmak üzere, $\gcd(a, m) = 1$ ise $a^{\phi(m)} \equiv 1 \pmod{m}$ elde edilir.

   Çin Kalan Teoremi (CRT)

   İkişerli aralarında asal olan $m_1, m_2, \dots, m_k$ modülleri için kurulan eşzamanlı lineer kongrüans sistemi:

   $x \equiv a_1 \pmod{m_1}$
   $x \equiv a_2 \pmod{m_2}$
   $\vdots$
   $x \equiv a_k \pmod{m_k}$

   $M = m_1 m_2 \dots m_k$ modülünde tek bir ortak çözüme sahiptir. Bu teorem veri şifreleme ve hızlı aritmetik hesaplamalarda yaygın olarak kullanılır.