Modular Inverse in Bigmod

প্রথমেই আসি মডুলার ইনভার্স কি?

দুটি সংখ্যার যোগ, বিয়োগ, গুনের ক্ষেত্রে আমরা নিচের রুলস গুলো অ্যাপ্লাই করতে পারি।

1. (a+b) mod m = ((a mod m) + (b mod m)) mod m 

2. (a-b) mod m = ((a mod m) - (b mod m)) mod m 

3. (a*b) mod m =((a mod m) * (b mod m)) mod m

কিন্ত ভাগের ক্ষেত্রে এই রুলস এপ্লিকেবল না। 

 

তার মানে তুমি (a/b) mod m = ((a mod m) / (b mod m)) mod m লিখতে পারবা না।

উদাহরনঃ

(12/3) mod 3 = 4 mod 3 = 1 

But, ((12 mod 3)/(3 mod 3)) mod 3 = (0/0) mod 3 = undefined!! 

Clearly they aren't same.

 

b এবং m যদি পরস্পর সহমৌলিক হয়, অর্থাৎ GCD(b,m)=1 হয় তবে তুমি মডুলার ইনভার্স ব্যাবহার করে (a/b) mod m বের করতে পারবে।

খেয়াল কর, (a/b) mod m = (a*(b^-1)) mod m = ((a mod m)* ((b^-1) mod m)) mod m 

এখন তোমার দরকার (b^-1) mod m এর মান। এই মানটা পেয়ে গেলে জাস্ট Big Mod ইউজ করে (a mod m) এর সাথে গুন করে দিলেই হলো। কিভাবে (b^-1) mod m এর মান বের করবে?

ফার্মার লিটল থিওরেম অনুসারে b এবং m যদি পরস্পর সহমৌলিক হয় তাহলে,

b^m mod m = b mod m 

or, b^(m-1) mod m = 1 mod m [dividing both side by b]

or, b^(m-2) mod m = b^(-1) mod m [again dividing both side by b]

তাহলে আমরা দেখছি যে m মৌলিক সংখ্যা হলে b^(-1) mod m = b^(m-2) mod m 

কন্টেস্টে সাধারনত m = 1000000007 দেয়া থাকে যা একটি মৌলিক সংখ্যা। তাই এক্ষেত্রে তোমরা উপরের সূত্রটি অ্যাপ্লাই করতে পার।