Kekongruenan dan Aritmetika Modular

Aritmetika modular mempelajari bilangan bulat hingga keterbagian oleh modulus tetap, mengubah bilangan bulat menjadi gelanggang hingga Z/nZ dan memberikan teori bilangan alat komputasi yang paling fleksibel.

Definition

Dua bilangan bulat kongruen modulo n jika selisihnya habis dibagi n. Aritmetika modular adalah aritmetika dari kelas residu yang dihasilkan, yang membentuk gelanggang komutatif Z/nZ.

Scope

Topik ini mencakup relasi kekongruenan dan kelas residu, aritmetika dalam Z/nZ, kekongruenan linear dan polinomial, teorema sisa Tiongkok, teorema kecil Fermat dan teorema Euler, struktur grup unit, akar primitif, dan orde elemen. Ini adalah bahasa di mana sebagian besar teori bilangan elementer dan komputasi diekspresikan.

Core questions

• Kapan kekongruenan linear ax kongruen dengan b mod n memiliki solusi, dan berapa banyak?
• Bagaimana teorema sisa Tiongkok menguraikan Z/nZ menjadi produk di atas modulus pangkat prima?
• Mengapa teorema kecil Fermat dan teorema Euler berlaku, dan apa yang mereka katakan tentang orde unit?
• Untuk modulus mana akar primitif ada, membuat grup unit siklik?

Key theories

Teorema sisa Tiongkok

Jika modulus-modulusnya koprima berpasangan, sistem kekongruenan simultan memiliki solusi unik modulo produk; secara ekuivalen Z/nZ isomorfik dengan produk Z di atas faktor-faktor pangkat primanya.

Teorema kecil Fermat dan teorema Euler

Untuk a koprima dengan n, a dipangkatkan totient dari n kongruen dengan satu modulo n; kasus prima (Fermat) mendasari uji primalitas dan kasus umum mendasari RSA.

Akar primitif dan struktur grup

Grup perkalian unit mod n siklik tepat ketika n adalah satu, dua, empat, pangkat prima ganjil, atau dua kali lipat dari salah satunya; generator adalah akar primitif, memberikan logaritma diskrit.

Clinical relevance

Aritmetika modular adalah mesin komputasi kriptografi (RSA, Diffie-Hellman, skema kurva eliptik), checksum dan deteksi kesalahan (ISBN, fungsi hash), dan pembangkitan bilangan pseudorandom, menjadikannya bagian teori bilangan yang paling banyak digunakan.

History

Meskipun kasus-kasus khusus muncul dalam matematika Tiongkok dan India kuno (masalah sisa yang dinamai dari yang pertama), teori kekongruenan yang sistematis diperkenalkan oleh Gauss dalam Disquisitiones Arithmeticae (1801), di mana ia menetapkan notasi dan membuktikan hasil struktural utama.

Key figures

• Carl Friedrich Gauss
• Pierre de Fermat
• Leonhard Euler

Seminal works

• irelandRosen1990

Frequently asked questions

Apa arti notasi a kongruen dengan b mod n?

Ini berarti n membagi selisih a dikurangi b, secara ekuivalen a dan b meninggalkan sisa yang sama pada pembagian oleh n.

Mengapa RSA mengandalkan teorema Euler?

Enkripsi dan dekripsi RSA adalah eksponensiasi modular yang komposisinya mengembalikan pesan asli justru karena teorema Euler menjamin eksponen yang relevan bertindak sebagai identitas modulo kunci.