Pertanyaan menemukan mod a / b c


Saya tahu ini mungkin tampak seperti pertanyaan matematika tetapi saya hanya melihat ini dalam sebuah kontes dan saya benar-benar ingin tahu bagaimana menyelesaikannya.

Kita punya

a (mod c)

dan

b (mod c)

dan kami mencari nilai hasil bagi

(a / b) (mod c)

Ada ide?


5
2017-08-20 12:03


asal


Jawaban:


Dalam cincin modul integer C, persamaan ini setara:

A / B (mod C)
A * (1/B) (mod C)
A * B-1(mod C).

Dengan demikian Anda perlu mencari B-1, invers perkalian dari B modulo C. Anda dapat menemukannya menggunakan mis. Algoritma Euclidian diperpanjang.

Perhatikan bahwa tidak setiap angka memiliki invers perkalian untuk modulus yang diberikan.

Secara khusus, B-1 ada jika dan hanya jika gcd(B, C) = 1 (yaitu. B dan C adalah coprime).

Lihat juga


Modular multiplicative inverse: Contoh

Misalkan kita ingin menemukan invers perkalian dari 3 modulo 11.

Artinya, kami ingin mencari

x = 3-1(mod 11)
x = 1/3 (mod 11)
3x = 1 (mod 11)

Dengan menggunakan algoritma Euclidian yang diperluas, Anda akan menemukan bahwa:

x = 4 (mod 11)

Jadi, invers perkalian modular 3 modulo 11 adalah 4. Dengan kata lain:

A / 3 == A * 4 (mod 11) 


Algoritma naive: pencarian brute force

Salah satu cara untuk memecahkan ini:

3x = 1 (mod 11)

Apakah hanya mencoba x untuk semua nilai 0..11, dan lihat apakah persamaannya benar. Untuk modulus kecil, algoritma ini dapat diterima, tetapi algoritma Euclidian diperpanjang jauh lebih baik secara asimtotik.


18
2017-08-20 12:05



Ada banyak jawaban potensial. Ketika semua yang Anda miliki adalah k = B mod C, maka B dapat berupa k + CN untuk semua bilangan bulat N.

Ini berarti B berpotensi sangat besar. Sangat besar, pada kenyataannya, untuk membuat A / B mendekati nol.

Namun, itu hanya satu cara untuk merespons.


-1
2017-08-20 12:10



Saya pikir itu bisa ditulis sebagai (Tapi tidak yakin)

(a/b)%c = ((a)%(b*c))/b

-4
2017-10-01 16:43