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 যদি পরস্পর সহমৌলিক হ...