মূল বিষয়বস্তু
কোর্স: কম্পিউটার বিজ্ঞান > অধ্যায় 2
পাঠ 5: মডুলার পাটিগণিতইউক্লিডীয় অ্যালগোরিদম
লক্ষ্য করি, দুইটি পূর্ণসংখ্যা A এবং B এর গরিষ্ঠ সাধারণ গুণনীয়ক (গসাগু.) হল সবচেয়ে বৃহত্তম পূর্ণসংখ্যা যা দিয়ে A এবং B উভয়কে ভাগ করা যায়।
দুটি পূর্ণসংখার গসাগু. নির্ণয় করার দ্রুত পদ্ধতি হল ইউক্লিডীয় অ্যালগোরিদম।
অ্যালগোরিদম
নিম্নে ইউক্লিডীয় অ্যালগোরিদম ব্যবহার করে A,B এর গসাগু নির্ণয় করার পদ্ধতি দেওয়া হল:
- যদি A = 0 হয়, তাহলে গসাগু(A,B)=B হয়, যেহেতু গসাগু(0,B)=B এবং আমরা এবার থামতে পারি।
- যদি B = 0 হয়, তাহলে গসাগু(A,B)=A হয়, যেহেতু গসাগু(A,0)=A এবং আমরা এবার থামতে পারি।
- A কে ভাগফল ভাগশেষ গঠনে লেখ (A = B⋅Q + R)
- ইউক্লিডীয় অ্যালগোরিদম ব্যবহার করে B,R এর গসাগু নির্ণয় কর যেহেতু গসাগু(A,B) = গসাগু(B,R)
উদাহরণ:
270 এবং 192 এর গসাগু নির্ণয় কর
- A=270, B=192
- A ≠0
- B ≠0
- দীর্ঘ প্রক্রিয়ার ভাগ দিয়ে নির্ণয় কর 270/192 = 1 যার ভাগশেষ 78। এটিকে এমনভাবে লেখা যায়: 270 = 192 * 1 +78
- গসাগু(192,78) নির্ণয় কর, যেহেতু গসাগু(270,192)=গসাগু(192,78)
A=192, B=78
- A ≠0
- B ≠0
- দীর্ঘ প্রক্রিয়ার ভাগ দিয়ে নির্ণয় কর 192/78 = 2 যার ভাগশেষ 36। এটিকে এমনভাবে লেখা যায়:
- 192 = 78 * 2 + 36
- গসাগু(78,36) নির্ণয় কর, যেহেতু গসাগু(192,78)=গসাগু(78,36)
A=78, B=36
- A ≠0
- B ≠0
- দীর্ঘ প্রক্রিয়ার ভাগ দিয়ে নির্ণয় কর 78/36 = 2 যার ভাগশেষ 6। এটিকে এমনভাবে লেখা যায়:
- 78 = 36 * 2 + 6
- গসাগু(36,6) নির্ণয় কর, যেহেতু গসাগু(78,36)=গসাগু(36,6)
A=36, B=6
- A ≠0
- B ≠0
- দীর্ঘ প্রক্রিয়ার ভাগ দিয়ে নির্ণয় কর 36/6 = 6 যার ভাগশেষ 0। এটিকে এমনভাবে লেখা যায়:
- 36 = 6 * 6 + 0
- গসাগু(6,0) নির্ণয় কর, যেহেতু গসাগু(36,6)=গসাগু(6,0)
A=6, B=0
- A ≠0
- B =0, গসাগু(6,0)=6
তাহলে দেখানো হয়েছে:
গসাগু(270,192) = গসাগু(192,78) = গসাগু(78,36) = গসাগু(36,6) = গসাগু(6,0) = 6
গসাগু(270,192) = 6
ইউক্লিডীয় অ্যালগোরিদম বোঝা
ইউক্লিডীয় অ্যালগোরিদম পরীক্ষা করলে নিচের বৈশিষ্ট্যগুলো দেখা যায়ঃ
- গসাগু(A,0) = A
- গসাগু(0,B) = B
- যদি A = B⋅Q + R এবং B≠0 হয়, তাহলে গসাগু(A,B) = গসাগু(B,R) যেখানে Q হল একটি পূর্ণসংখ্যা, R হল 0 এবং B-1 এর মধ্যে একটি পূর্ণসংখ্যা।
প্রথম দুইটি বৈশিষ্ট্য আমাদের গসাগু নির্ণয় করায় সহায়তা করে যদি কোন একটি সংখ্যা 0 হয়। তৃতীয় বৈশিষ্ট্য দিয়ে অনেক জটিল এবং বড় সমস্যা নিয়ে এটিকে ছোট, সহজ সমস্যায় পরিণত করা হয়।
ইউক্লিডীয় অ্যালগোরিদম এই সকল বৈশিষ্ট্য ব্যবহার করে সমস্যাকে ক্ষুদ্র থেকে ক্ষুদ্রতর সহজ সমস্যায় পরিণত করে (তৃতীয় বৈশিষ্ট্য দ্বারা) এবং তারপর যখন সবচেয়ে সরল পর্যায়ে এটি উপনীত হয়, তখন প্রথম দুইটি বৈশিষ্ট্যের যে কোন একটি কাজে লাগিয়ে সমস্যার সমাধান করে।
আমরা এই বৈশিষ্ট্যগুলোর প্রমাণ দিয়ে এগুলোর কার্যপ্রক্রিয়া সম্পর্কে বুঝতে পারি।
নিম্নে গসাগু(A,0)=A এর প্রমাণ দেওয়া হল:
- সবচেয়ে বড় যে পূর্ণসংখ্যা দিয়ে A কে ভাগ করা যায় সেটি হল A।
- সকল পূর্ণসংখ্যা 0 কে সমভাবে ভাগ করে, তাই কোন পূর্ণসংখ্যার জন্য, C, আমরা লেখতে পারি C ⋅ 0 = 0। তাহলে বলা যায় যে A অবশ্যই 0 কে সমভাবে ভাগ করবে।
- সবচেয়ে বৃহত্তম সংখ্যা যা উভয় A এবং 0 কে ভাগ করে, সেটি হল A।
গসাগু(0,B)=B এর প্রমাণও একই রকম। (একই প্রমাণ, কিন্তু শুধু A এর স্থানে B হয়)।
গসাগু(A,B)=গসাগু(B,R) প্রমাণ করার জন্য প্রথমে দেখাতে হবে যে, গসাগু(A,B)=গসাগু(B,A-B)।
মনে করা যাক আমাদের তিনটি পূর্ণসংখ্যা A,B এবং C এভাবে দেওয়া আছে A-B=C।
গসাগু(A,B) এর C কে সমভাবে ভাগ করার প্রমাণ
গসাগু(A,B), সংজ্ঞানুসারে, A কে সমভাবে ভাগ করে। ফলশ্রুতিতে, A অবশ্যই গসাগু(A,B) এর গুণিতক। যেমন: X⋅গসাগু(A,B)=A যেখানে X একটি পূর্ণসংখ্যা
গসাগু(A,B), সংজ্ঞানুসারে, B কে সমভাবে ভাগ করে। ফলশ্রুতিতে, B অবশ্যই গসাগু(A,B) এর গুণিতক। যেমন: Y⋅গসাগু(A,B)=B যেখানে Y একটি পূর্ণসংখ্যা
A-B=C হয়:
- X⋅গসাগু(A,B) - Y⋅গসাগু(A,B) = C
- (X - Y)⋅গসাগু(A,B) = C
তাহলে দেখা যায় যে, গসাগু(A,B) দিয়ে C কে সমভাবে ভাগ করা যায়।
এটির প্রমাণ চিত্রে বামপক্ষে দেখানো হল:
প্রমাণ কর যে, গসাগু(B,C), A কে সমানভাবে ভাগ করে
গসাগু(B,C), সংজ্ঞানুসারে, B কে সমভাবে ভাগ করে। ফলশ্রুতিতে, B অবশ্যই গসাগু(B,C) এর গুণিতক। যেমন: M⋅গসাগু(B,C)=B যেখানে M একটি পূর্ণসংখ্যা
গসাগু(B,C), সংজ্ঞানুসারে, C কে সমভাবে ভাগ করে। ফলশ্রুতিতে, C অবশ্যই গসাগু(B,C) এর গুণিতক। যেমন: N⋅গসাগু(B,C)=C যেখানে N একটি পূর্ণসংখ্যা
A-B=C হয়:
- B+C=A
- M⋅গসাগু(B,C) + N⋅গসাগু(B,C) = A
- (M + N)⋅গসাগু(B,C) = A
তাহলে দেখা যায় যে, গসাগু(B,C) দিয়ে A কে সমভাবে ভাগ করা যায়।
এটির প্রমাণ নিচের চিত্রে দেখানো হল:
প্রমাণ কর যে, GCD(A,B)=GCD(A,A-B)
- গসাগু(A,B) সংজ্ঞানুসারে, B কে সমভাবে ভাগ করে।
- আমরা প্রমাণ করেছি যে, গসাগু(A,B) দিয়ে C কে সমভাবে ভাগ করা যায়।
- যেহেতু গসাগু(A,B) উভয় B এবং C কে সমভাবে ভাগ করে। সুতরাং, এটি হল B এবং C এর সাধারণ গুণনীয়ক।
গসাগু(A,B) কে অবশ্যই গসাগু(B,C) থেকে ছোট অথবা সমান হতে হবে, কারণ গসাগু(B,C) হল B এবং C এর “গরিষ্ঠ” সাধারণ গুণনীয়ক।
- গসাগু(A,B) সংজ্ঞানুসারে, B কে সমভাবে ভাগ করে।
- আমরা প্রমাণ করেছি যে, গসাগু(B,C) দিয়ে A কে সমভাবে ভাগ করা যায়।
- যেহেতু গসাগু(B,C) উভয় A এবং B কে সমভাবে ভাগ করে। সুতরাং, এটি হল A এবং B এর সাধারণ গুণনীয়ক।
গসাগু(B,C) কে অবশ্যই গসাগু(A,B) থেকে ছোট অথবা সমান হতে হবে, কারণ গসাগু(A,B) হল A এবং B এর “গরিষ্ঠ” সাধারণ গুণনীয়ক।
দেওয়া আছে, গসাগু(A,B)≤গসাগু(B,C) এবং গসাগু(B,C)≤গসাগু(A,B) । সুতরাং বলা যায়:
গসাগু(A,B)=গসাগু(B,C)
যা সমান হল:
গসাগু(A,B)=গসাগু(B,A-B)
এটির প্রমাণ চিত্রে ডানপক্ষে দেখানো হল:
প্রমাণ কর যে, GCD(A,B) = GCD(B,R)
আমরা প্রমাণ করেছি যে, গসাগু(A,B)=গসাগু(B,A-B)
পদের ক্রমের উপর ভিত্তি করা হয় না, তাই বলা যায় গসাগু(A,B)=গসাগু(A-B,B)
আমরা বারবার গসাগু(A,B)=গসাগু(A-B,B) প্রয়োগ করে পাই:
গসাগু(A,B)=গসাগু(A-B,B)=গসাগু(A-2B,B)=গসাগু(A-3B,B)=...=গসাগু(A-Q⋅B,B)
কিন্তু A= B⋅Q + R ,এজন্য A-Q⋅B=R
সুতরাং গসাগু(A,B)=গসাগু(R,B)
পদের ক্রমের উপর নির্ভর করে না, সুতরাং:
গসাগু(A,B)=গসাগু(B,R)
আলোচনায় অংশ নিতে চাও?
কোন আলাপচারিতা নেই।