Tamsayılar üzerinde kongrüansı iki katılabilir ilişkidir tamsayılar . İlk bir yapı olarak çalışılmıştır matematikçi Alman Carl Friedrich Gauss sonunda XVIII inci yüzyılın ve onun kamuoyuna sunulan Disquisitiones Arithmeticae içinde 1801 . Artık sayı teorisi , genel cebir ve kriptografide yaygın olarak kullanılmaktadır . Modüler aritmetik adı verilen bir matematik dalının temelini temsil eder .
Bu, kişinin doğrudan sayılar üzerinde değil, belirli bir tamsayı ile Öklid bölünmesiyle ilgili kalanları üzerinde mantık yürüttüğü bir aritmetiktir : modül ( makale boyunca n ile belirtilecektir ). Daha sonra uyumdan söz ederiz .
Tarihçe, modüler aritmetik için geliştirilen araçlar ve uygulamalar " Modüler aritmetik " makalesinde ele alınmaktadır . " Anneau ℤ / n ℤ " makalesinde daha kapsamlı ve daha az didaktik bir analiz önerilmiştir .
Modüler aritmetik, sayıların belirli bir değere ulaştıklarında "düşürüldüğü", değiştirilmiş tam sayıların aritmetik sistemidir.
Örnek olarak, bir saatin küçük ibresi tarafından gösterilen saatlerin "toplamasına" atıfta bulunan "saatin aritmetiği" ni verelim: somut olarak, saat 9'dan başlayıp 4 saat eklersek, daha doğrusu öğleden sonra 1'de bitirmek yerine (normal faturada olduğu gibi), 1 saatindeyiz. Aynı şekilde, gece yarısı başlar ve arka arkaya üç kez sabah 7'yi beklersek, sabah 9'da buluşuruz (akşam 9 yerine).
Temel olarak 12'ye bastığımızda sıfırdan baştan başlarız; modulo 12 üzerinde çalışıyoruz. Önceki örneğe dönersek, 9 ve 21'in uyumlu modulo 12 olduğunu söylüyoruz. 9, 21, 33, 45 vb. sayılar. modulo 12 çalışırken eşit kabul edilir.
Genellemek gerekirse, keyfi sayıda saat içeren bir saat hayal edebilir ve yeni bir modülle hesaplamalar yapabiliriz.
Tanımı - Let n olmak bir doğal sayı .
İki akraba tamsayılar bir ve b olduğu söylenen uyumlu modülo n kendi fark ise bölünebilir tarafından n olduğunu söylemek için bir form olduğunu b + kn ile k tam sayı.
Şimdi dışlamak önemsiz dava n = 0 (ahenk 0 modülo olan eşitlik , biz 1 tesadüfen ihbar modulo ki, herhangi iki tamsayılar eşdeğerdir).
Eşdeğer tanımı ise , n > 0 - Let ki burada n , sıfır olmayan bir doğal tam sayı.
İki tamsayı , bir ve b uyumlu modülo olduğu söylenmektedir , n geri kalanı ise Öklid bölümü arasında bir ile n bölünmesi eşittir b ile n .
İki tamsayının uyumunu ifade etmek için kullanılan karakter ≡'dir .
Bunu ifade edebilen bir ve b uyumlu modülo olan n dört formlarda:
Sonuncusu , 2009 ISO / IEC 80000-2 standardı tarafından tavsiye edilmektedir .
Hangi gösterimi seçerseniz seçin, bu " a , b modulo n ile uyumludur " şeklinde okunur .
Örneğin : 26 ≡ 12 (7) çünkü 26 - 12 = 14, 7'nin katı ( yukarıdaki tanım ), veya tekrar: çünkü 26 ve 12'nin her ikisinin de 7'ye bölünmesinde kalan 5 değeri vardır ( yukarıdaki eşdeğer tanım ).
UyarılarModulo n uyumu aşağıdaki özelliklere sahiptir:
Bu nedenle bir eşdeğerlik ilişkisidir .
Cebirsel özelliklerAyrıca dikkate değer cebirsel özelliklere sahiptir:
Evet bir 1 ≡ b 1 ( n ) ve bir 2 ≡ b 2 ( n ), yani
(Bu kolayca anlamak diğerleri gibi: eğer bir ≡ b ( N ) daha sonra AC ≡ bc ( n her tam sayı için) c ve bir q b ≡ q ( n her tam sayı için) q 0 ≥)
Tamsayıların toplanması ve çarpılması işlemleriyle belirli bir "uyumluluktan", yani (structure, +, ×) halka yapısıyla "uyumluluktan" bahsedebiliriz. Bu birkaç özellik, modüler aritmetiğin alanını tanımlamamıza izin verecektir: bölüm kümeleri ℤ / n ℤ.
Önceki özellikleri iki sayı birbirine modülo ile eşleşik göstermektedir , n bir uyum modulo sırasında, bir ekleme veya bir çarpma yerleri değiştirilebilir n . Fikir sonra tüm sayılar uyumlu birbirlerine modulo için birlikte gruba gelince n sadece bu sınıfın belirli bir temsilcisi ile bir denklik sınıfı ve işe çağırmak aynı sınıfta. Aynı sınıfın tüm sayılar bölme aynı geri kalan kısmı olarak n , biz bölme içinde kalanlar tercih n ve bir dizi iş ℤ belirtildiği n veya ℤ / n ℤ oluşan n elemanlarının daha basit {0 veya , 1, 2, ..., n - 1} artık halka modülü n veya hatta bölüm halkası olarak adlandırdığımız modülo n kalanı kümesi
Bu sette , tamsayılar kümesi ℤ üzerinde tanımlananlara benzer bir toplama ve çarpma tanımlanabilir :
Daha sonra aşağıdaki işlem tablolarını oluşturabiliriz:
+ | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|
0 | 0 | 1 | 2 | 3 | 4 | 5 |
1 | 1 | 2 | 3 | 4 | 5 | 0 |
2 | 2 | 3 | 4 | 5 | 0 | 1 |
3 | 3 | 4 | 5 | 0 | 1 | 2 |
4 | 4 | 5 | 0 | 1 | 2 | 3 |
5 | 5 | 0 | 1 | 2 | 3 | 4 |
× | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | 1 | 2 | 3 | 4 | 5 |
2 | 0 | 2 | 4 | 0 | 2 | 4 |
3 | 0 | 3 | 0 | 3 | 0 | 3 |
4 | 0 | 4 | 2 | 0 | 4 | 2 |
5 | 0 | 5 | 4 | 3 | 2 | 1 |
Bu işlemler, ℤ'daki toplama ve çarpma ile hemen hemen aynı özelliklere sahiptir.
Bu özelliklere sahip iki işlemli bir sete halka denir .
ℤ 'da yapmaya alışkın olduğumuz ve ℤ / n ℤ halkasında her zaman doğru olmayan tek işlem basitleştirmedir.
2 Aslında, eğer bir = 4 ℤ olarak, bildiğimiz bir = 2. Ancak 2 ise, 6 modulo bir = 4, sadece 2 biliyoruz bir O halde, 6 ile bölme içinde kalan 4 sahip bir içinde kalan 2 yer alır 3 ile bölme bir nedenle 6 ya 2 ya da 5. Daha basit bölme bir bakiye olarak sahip olabilir: biz 2 × 2 ≡ 2 x 5 sahip olan 2 ≡ 5 kalmadan.
Benzer şekilde, klasik sayı kümelerinde sürekli kullanılan özellik "iki terimli bir çarpımın sıfır olması için, terimlerden birinin olması gerekli ve yeterlidir" her zaman ℤ / n ℤ'de gerçekleştirilmez.modulo 6, 2 × 3 ≡ 0 var, 2 veya 3 0 ile uyumlu değil.
ℤ / 6ℤ halkasının integral olmadığını söylüyoruz .
Dolayısıyla, çarpmalar söz konusu olduğunda denklemleri çözmek biraz sorunlu hale gelebilir:
Biz denklem olduğunu göstermektedir ax = b ait bilinmeyen x ℤ / de n ℤ ancak ve ancak tek bir çözümü vardır bir ve n aralarında asal bulunmaktadır.
N ve a değerlerine göre , hiçbiri, bir, iki çözüme ve hatta daha fazlasına sahip olabilen denklemin çözümlerinin araştırılması, ikinci dereceden kalıntıların incelenmesine ve yasasının ifadesine yol açar . ikinci dereceden karşılıklılık .
ℤ / inşası n bir şekilde ℤ quotiented halka , bir tarafından bir ideal ve halka ℤ / cebirsel özellikleri n ℤ maddesi “olarak ele alınmaktadır halka ℤ / n ℤ ”.
ℤ / n ℤ'deki çarpımdan, ardışık güçlerle ilgilenmek doğaldır. Yalnızca n - 1 olası kalan vardır, bu nedenle bir k için n - 1 olası değerler , bu nedenle zorunlu olarak aynı değeri birkaç kez elde ederiz. Öyleyse k ve m vardır öyle ki a k ve a m aynı modulo n kalanına sahiptir . Bir k'nin inşası bir yinelemeye dayandığından, daha önce karşılaştığımız bir kalıntıyla karşılaştığımız anda, güçler dizisinin bu güçten döngüsel hale geldiğini biliyoruz ve araştırmayı durdurabiliriz.
1 | 2 | 3 | 4 | 5 | 6 | |
---|---|---|---|---|---|---|
k = 0 | 1 | 1 | 1 | 1 | 1 | 1 |
k = 1 | 1 | 2 | 3 | 4 | 5 | 6 |
k = 2 | ... | 4 | 2 | 2 | 4 | 1 |
k = 3 | ... | 1 | 6 | 1 | 6 | ... |
k = 4 | ... | ... | 4 | ... | 2 | ... |
k = 5 | ... | ... | 5 | ... | 3 | ... |
k = 6 | 1 | 1 | 1 | 1 | 1 | 1 |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
k = 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
k = 1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
k = 2 | ... | 4 | 9 | 1 | 10 | 6 | 4 | 4 | 6 | 10 | 1 | 9 | 4 | 1 |
k = 3 | ... | 8 | 12 | ... | 5 | ... | 13 | 2 | 9 | ... | ... | 3 | 7 | ... |
k = 4 | ... | 1 | 6 | ... | ... | ... | 1 | 1 | ... | ... | ... | 6 | 1 | ... |
k = 5 | ... | ... | 3 | ... | ... | ... | ... | ... | ... | ... | ... | 12 | ... | ... |
... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... |
k = 8 | 1 | 1 | ... | 1 | ... | ... | 1 | 1 | ... | ... | 1 | ... | 1 | 1 |
ℤ / 7ℤ güçlerin ve, birinci durumda, tüm ℤ / 15ℤ gösterileri bir gözlem bir ile asal 7 (yani değil çoklu 7), biz bir 6 1 modülo 7 ve ikinci durumda uygun bir şekilde, 1'den geçen tek diziler, 15 ile asal tamsayılara karşılık gelir; 15'li 8 asal tam sayı vardır ve 15'li bir asal için 8'in 1 modulo 15 ile uyumlu olduğunu fark ederiz .
Bu iki gözlem iki teoreme karşılık gelir: