Invers Modular melalui Fermat

Penjumlahan, pengurangan, dan perkalian bekerja dengan baik menggunakan modulus, tetapi pembagian biasa tidak. Anda tidak dapat begitu saja membagi lalu mengambil sisanya. ⚠️

Solusinya adalah invers modulo: pembagian dengan x diubah menjadi perkalian dengan invers x. Jadi, a / b modulo m berubah menjadi a dikalikan invers b.

Invers dari x adalah bilangan yang menghasilkan 1 ketika dikalikan dengan x menggunakan modulus. Invers berperan seperti 1/x dalam aritmetika biasa.

Invers hanya ada jika x tidak memiliki faktor persekutuan dengan m. Menggunakan modulus prima seperti 1e9+7 menjamin setiap x yang bukan nol memiliki invers.

Teorema kecil Fermat menyatakan bahwa untuk bilangan prima p, x pangkat p dikurangi 1 kongruen dengan 1, selama x bukan kelipatan p.

Pisahkan satu faktor x, dan bagian sisanya pasti merupakan inversnya. Jadi, invers x adalah x yang dipangkatkan dengan p dikurangi 2, lalu diambil modulo p.

Eksponen tersebut sangat besar, jadi gunakan perpangkatan cepat dari pelajaran sebelumnya. Di Python, satu pemanggilan pow melakukan semuanya untuk Anda.

Untuk menghitung a dibagi b menggunakan modulo, kalikan a dengan invers b. Sisanya tepat sama dengan hasil bagi sebenarnya modulo p.

Tidak ada invers dari 0 karena tidak ada bilangan yang jika dikalikan dengan nol menghasilkan satu. Pastikan Anda tidak membagi dengan nilai yang menjadi nol setelah menggunakan modulus.

Setiap invers Fermat adalah satu perpangkatan cepat, sehingga membutuhkan waktu O(log p). Ini murah untuk beberapa pembagian, tetapi dapat menjadi besar jika dilakukan jutaan kali.

Saat Anda memerlukan banyak invers, lakukan praperhitungan dengan satu lintasan linear yang cerdas, bukan dengan satu pow untuk setiap elemen. Anda akan mengandalkan teknik ini untuk nCr berikutnya.

Sekarang Anda dapat melakukan pembagian menggunakan modulus prima dengan mengalikan invers modulo, yang diperoleh sebagai x pangkat p dikurangi 2 melalui pow. Ingat, jangan pernah mencari invers dari nol. ✅