বিপরীত কি?

কোন সংখ্যাকে তার বিপরীত সংখ্যা দ্বারা গুণ করলে ফলাফল 1 হয়। আমরা সাধারণ পাটিগণিত থেকে জানি:
  • The inverse of a number A is 1/A since A * 1/A = 1 
    e.g. the inverse of 5 is 1/5
  • All real numbers other than 0 have an inverse
  • Multiplying a number by the inverse of A is equivalent to dividing by A
    e.g. 10/5 is the same as 10* 1/5

বিপরীত মডুলার কি?

মডুলার পাটিগণিতে ভাগ করার কোন প্রক্রিয়া নেই। কিন্তু, বিপরীত মডুলার রয়েছে।
  • The modular inverse of A (mod C) is A^-1
  • (A * A^-1) ≡ 1 (mod C) or equivalently (A * A^-1) mod C = 1
  • Only the numbers coprime to C (numbers that share no prime factors with C) have a modular inverse (mod C)

বিপরীত মডুলার কিভাবে নির্ণয় করতে হয়

বিপরীত মডুলার A (mod C) নির্ণয়ের একটি সরল পদ্ধতি হল:
ধাপ ১. B এর 0 থেকে C-1 মানের জন্য A * B mod C নির্ণয় কর
ধাপ ২. A mod C এর বিপরীত মডুলার হল B এর মান যেখানে A * B mod C = 1
লক্ষণীয় যে, B mod C পদের শুধুমাত্র 0 থেকে C-1 পর্যন্ত পূর্ণসংখ্যা রয়েছে, এজন্য B এর বড় মান যাচাই করা অনাবশ্যক।

উদাহরণ: A=3 C=7

ধাপ ১. B এর 0 থেকে C-1 মানের জন্য A * B mod C নির্ণয় কর

3 * 0 ≡ 0 (mod 7)
3 * 1 ≡ 3 (mod 7)
3 * 2 ≡ 6 (mod 7)
3 * 3 ≡ 9 ≡ 2 (mod 7)
3 * 4 ≡ 12 ≡ 5 (mod 7)
3 * 5 ≡ 15 (mod 7) ≡ 1 (mod 7)   <------ ​বিপরীত পাওয়া গেছে!
3 * 6 ≡ 18 (mod 7) ≡ 4 (mod 7)

ধাপ ২. A mod C এর বিপরীত মডুলার হল B এর মান যেখানে A * B mod C = 1

5 হল 3 mod 7 এর বিপরীত মডুলার যেহেতু 5*3 mod 7 = 1
সাধারণ!
এসো আরেকটি উদাহরণ করি যেখানে বিপরীত পাওয়া যায় না।

উদাহরণ: A=2 C=6

ধাপ ১. B এর 0 থেকে C-1 মানের জন্য A * B mod C নির্ণয় কর

2 * 0 ≡ 0 (mod 6)
2 * 1 ≡ 2 (mod 6)
2 * 2 ≡ 4 (mod 6)
2 * 3 ≡ 6 ≡ 0 (mod 6)
2 * 4 ≡ 8 ≡ 2 (mod 6)
2 * 5 ≡ 10 ≡ 4 (mod 6)

ধাপ ২. A mod C এর বিপরীত মডুলার হল B এর মান যেখানে A * B mod C = 1

B এর কোন মানের জন্য A * B mod C = 1 হয় না। সুতরাং, A এর কোন বিপরীত মডুলার নেই (mod 6)।
কারণ 2 এবং 6 এর মৌলিক উৎপাদক একই (এটি হল 2)।

এই পদ্ধতিটি ধীর গতির...

A (mod C) এর বিপরীত মডুলার নির্ণয় করার অনেক দ্রুত একটি উপায় রয়েছে যা আমরা পরবর্তী প্রবন্ধে আলোচনা করবো। বর্ধিত ইউক্লিডীয় অ্যালগোরিদম। প্রথমে, এসো কিছু অনুশীলনী করা যাক!