Modüler ters nedir?
Bir a tam sayısının m modülüne göre modüler çarpımsal tersi, \((a \cdot x) \bmod m = 1\) eşitliğini sağlayan x tam sayısıdır. Modüler aritmetikte adeta "bölme" işleminin karşılığıdır ve sayılar teorisinin, RSA şifreleme sisteminin ve birçok kodlama teorisi algoritmasının temelinde yer alır. Bu hesaplama aracı, x değerini genişletilmiş Öklid algoritmasını kullanarak bulur.
$$\text{a} \cdot x \equiv 1 \pmod{\text{m}} \quad\Longrightarrow\quad x = \text{a}^{-1} \bmod \text{m}$$
Hesaplama aracı nasıl kullanılır?
a sayısını ve m modülünü (m ≥ 2 olacak şekilde) girin. Araç, 0 ≤ x < m aralığındaki en küçük negatif olmayan ters değeri x'i verir, bir tersin var olup olmadığını teyit eder ve gcd(a, m) değerini gösterir. Eğer gcd(a, m) ≠ 1 ise ters mevcut değildir ve sonuç "Yok" olarak bildirilir.
Formülün açıklaması
Bir ters yalnızca \(\gcd(a, m) = 1\) olduğunda, yani a ile m aralarında asal olduğunda vardır. Genişletilmiş Öklid algoritması, \(a \cdot x + m \cdot y = \gcd(a, m)\) eşitliğini sağlayan x ve y tam sayılarını bulur. gcd değeri 1 olduğunda, x'i m modülüne göre indirgemek tersi verir. Sonuç negatifse, üzerine m eklenerek pozitif bir değere normalize edilir.
Çözümlü örnek
3 sayısının 11 modülüne göre tersini bulalım. \(3x \equiv 1 \pmod{11}\) eşitliğini sağlayan x'i arıyoruz. Denediğimizde, $$3 \times 4 = 12 = 11 + 1$$ olur, dolayısıyla \(12 \bmod 11 = 1\) elde edilir. Buna göre x = 4. Genişletilmiş Öklid algoritması da aynı değeri verir ve \(\gcd(3, 11) = 1\) olduğundan tersin var olduğu doğrulanır.
Sıkça sorulan sorular
Ne zaman ters bulunmaz? a ile m'nin 1'den büyük ortak bir çarpanı olduğunda ters yoktur — örneğin 6 modülüne göre 4 sayısının (gcd = 2) tersi yoktur.
m'nin asal olması gerekir mi? Hayır. m, 2 veya daha büyük herhangi bir tam sayı olabilir; önemli olan yalnızca a ile m'nin aralarında asal olmasıdır.
Sonuç hangi aralıkta verilir? Ters, en küçük negatif olmayan kalan olarak, 0 ile m − 1 arasında verilir.
