মূল বিষয়বস্তু
কম্পিউটার বিজ্ঞান
কোর্স: কম্পিউটার বিজ্ঞান > অধ্যায় 2
পাঠ 5: মডুলার পাটিগণিতমডুলার যোগ ও বিয়োগ
মডুলার পাটিগণিতের অতিরিক্ত বৈশিষ্ট্যগুলো খুঁজে দেখা যাক:
(A + B) mod C = (A mod C + B mod C) mod C
উদাহরণঃ
ধরি, A=14, B=17, C=5
যাচাই করে দেখা যাক: (A + B) mod C = (A mod C + B mod C) mod C
বামপক্ষ = বামদিকের সমীকরণ
ডানপক্ষ = ডানদিকের সমীকরণ
বামপক্ষ = বামদিকের সমীকরণ
ডানপক্ষ = ডানদিকের সমীকরণ
বামপক্ষ = (A + B) mod C
বামপক্ষ = (14 + 17) mod 5
বামপক্ষ = 31 mod 5
বামপক্ষ = 1
বামপক্ষ = (14 + 17) mod 5
বামপক্ষ = 31 mod 5
বামপক্ষ = 1
ডানপক্ষ = (A mod C + B mod C) mod C
ডানপক্ষ = (14 mod 5 + 17 mod 5) mod 5
ডানপক্ষ = (4 + 2) mod 5
ডানপক্ষ = 1
ডানপক্ষ = (14 mod 5 + 17 mod 5) mod 5
ডানপক্ষ = (4 + 2) mod 5
ডানপক্ষ = 1
বামপক্ষ = ডানপক্ষ = 1
মডুলার সংযুক্তকরণগুলো বিবেচনা করা যাক
নিচের আকৃতিটি লক্ষ্য কর। আমরা যদি 12+9 mod 7 গণনা করতে চাই আমরা সহজেই মডুলার চক্রটি একটি 12+9 ধাপের দক্ষিণাবর্তে ঘোরা চক্রের মাধ্যমে পার করে আসতে পারি (নিচের চক্রে যেমন দেওয়া আছে)।
মডুলার চক্রে প্রতি 7 ধাপ পর পর আমরা যে একই অবস্থানে এসে পৌঁছাচ্ছি এটা দেখার পরে আমরা একটি শর্টকাট পন্থা অবলম্বন করতে পারি। মডুলার চক্রের চারপাশে থাকা সম্পূর্ণ লুপটি আমাদের মূল অবস্থানে কোন প্রভাব ফেলবে। প্রতিটি সংখ্যাকে mod 7 দিয়ে হিসাব করার মাধ্যমে চক্রের চারপাশে থাকা এই লুপগুলো আমরা উপেক্ষা করব (উপরে থাকা দুইটি মডুলার চক্রে যেমন দেখান হয়েছে)। এটি দক্ষিণাবর্তে থাকা কিছু সংখ্যা আমাদের দিবে, তুলনামুলকভাবে এটা 0 হবে এবং এটা মডুলার চক্রের মূল অবস্থানকে প্রভাবিত করবে।
এখন, আমাদের প্রতিটি সংখ্যা মূল অবস্থানে পৌঁছাতে মোট যে সংখ্যক বার চক্রের চারপাশে ঘুরা লেগেছে সেই সংখ্যকবার চক্রের চারপাশে ঘোরা লাগবে (নিচের ডানপাশের মডুলার চক্রে যেরকম দেখান হয়েছে)। এই মেথডটি, সাধারনভাবে, যেকোন পূর্ণ সংখ্যা এবং যেকোন মডুলার চক্রের উপরে প্রয়োগ করা যায়।
মডুলার যোগের প্রমাণ
আমরা এখানে প্রমাণ করব যে (A + B) mod C = (A mod C + B mod C) mod C
এখানে অবশ্যই আমাদের দেখাতে হব বামপক্ষ=ডানপক্ষ
এখানে অবশ্যই আমাদের দেখাতে হব বামপক্ষ=ডানপক্ষ
ঘাত ভাগশেষের উপপাদ্য থেকে আমরা A এবং B কে এমনভাবেও লিখতে পারি:
A = C * Q1 + R1 যেখানে 0 ≤ R1 < C এবং Q1 হল পূর্ণসংখ্যা। A mod C = R1
B = C * Q2 + R2 যেখানে 0 ≤ R2 < C এবং Q2 হল পূর্ণসংখ্যা। B mod C = R2
(A + B) = C * (Q1 + Q2) + R1+R2
B = C * Q2 + R2 যেখানে 0 ≤ R2 < C এবং Q2 হল পূর্ণসংখ্যা। B mod C = R2
(A + B) = C * (Q1 + Q2) + R1+R2
বামপক্ষ = (A + B) mod C
বামপক্ষ = (C * (Q1 + Q2) + R1+ R2) mod C
আমরা C এর গুণ বাদ দিয়ে দিতে পার যখন আমরা mod C
বামপক্ষ = (R1 + R2) mod C নিব
বামপক্ষ = (C * (Q1 + Q2) + R1+ R2) mod C
আমরা C এর গুণ বাদ দিয়ে দিতে পার যখন আমরা mod C
বামপক্ষ = (R1 + R2) mod C নিব
ডানপক্ষ = (A mod C + B mod C) mod C
ডানপক্ষ = (R1 + R2) mod C
ডানপক্ষ = (R1 + R2) mod C
বামপক্ষ=ডানপক্ষ= (R1 + R2) mod C
মডুলার বিয়োগ
একই রকম আরও একটি প্রমাণ আছে যেটা মডুলার বিয়োগ প্রমাণ করে
(A - B) mod C = (A mod C - B mod C) mod C
আলোচনায় অংশ নিতে চাও?
কোন আলাপচারিতা নেই।