GCD, LCM ও ইউক্লিডিয়ান অ্যালগরিদম

GCD, LCM & the Euclidean algorithm

৮ মিনিট পড়া মাঝারি · Intermediate Python কোডসহ সম্পূর্ণ বাংলায়

এক নজরে · TL;DR

GCD$(a,b)$ — দুটি সংখ্যাকে ভাগ করে এমন সবচেয়ে বড় সংখ্যা। LCM$(a,b)$ — দুটি সংখ্যা দ্বারা বিভাজ্য সবচেয়ে ছোট পজিটিভ সংখ্যা। এদের মধ্যে সম্পর্ক: $\gcd(a,b)\cdot\text{lcm}(a,b)=a\cdot b$।
ইউক্লিডিয়ান অ্যালগরিদম — $\gcd(a,b)=\gcd(b, a \bmod b)$, base case $\gcd(a,0)=a$। মাত্র কয়েক ধাপে GCD বের করে, ফ্যাক্টরাইজেশনের দরকার নেই।
Extended Euclidean Algorithm — শুধু GCD নয়, এমন পূর্ণসংখ্যা $x,y$ও খুঁজে দেয় যেন $ax+by=\gcd(a,b)$ (Bézout's identity) — এটাই L28-এ RSA-এর modular inverse বের করার হাতিয়ার।

এই পাঠে যা শিখবেন

GCD ও LCM-এর সংজ্ঞা এবং তাদের মধ্যকার $\gcd \cdot \text{lcm} = a \cdot b$ অভেদ
ইউক্লিডিয়ান অ্যালগরিদম — কীভাবে ও কেন এটি কাজ করে
Extended Euclidean Algorithm ও Bézout's Identity-এর পরিচিতি
Python দিয়ে iterative GCD/LCM বাস্তবায়ন ও math.gcd-এর সাথে যাচাই

১ · GCD ও LCM-এর সংজ্ঞা

দুটি পূর্ণসংখ্যার GCDGreatest Common Divisorদুটি (বা তার বেশি) সংখ্যাকে একইসাথে ভাগ করে এমন সবচেয়ে বড় পজিটিভ সংখ্যা। (গরিষ্ঠ সাধারণ গুণনীয়ক) হলো $a$ এবং $b$ উভয়কেই ভাগ করে এমন সবচেয়ে বড় পজিটিভ সংখ্যা। আর LCMLeast Common Multipleদুটি (বা তার বেশি) সংখ্যা দ্বারা একইসাথে বিভাজ্য সবচেয়ে ছোট পজিটিভ সংখ্যা। (লঘিষ্ঠ সাধারণ গুণিতক) হলো $a$ ও $b$ উভয় দ্বারাই বিভাজ্য সবচেয়ে ছোট পজিটিভ সংখ্যা।

এই দুইয়ের মধ্যে একটি সুন্দর সম্পর্ক আছে —

$$\gcd(a,b) \cdot \text{lcm}(a,b) = a \cdot b$$

কেন এই অভেদ সত্য

প্রাইম ফ্যাক্টরাইজেশন দিয়ে ভাবলে সহজ হয়। প্রতিটি প্রাইমের জন্য, $\gcd$-এ তার ঘাত হলো $a$ ও $b$-এর ঘাতের ন্যূনতম (min), আর $\text{lcm}$-এ তার ঘাত হলো সর্বোচ্চ (max)। যেহেতু যেকোনো দুটি সংখ্যা $m,n$-এর জন্য $\min(m,n)+\max(m,n)=m+n$, তাই $\gcd$ ও $\text{lcm}$-এর ঘাতগুলো যোগ করলে ঠিক $a$ ও $b$-এর ঘাতের যোগফলই পাওয়া যায় — যা $a \cdot b$-এর সমতুল্য।

২ · ইউক্লিডিয়ান অ্যালগরিদম

ফ্যাক্টরাইজেশন করে GCD বের করা বড় সংখ্যার জন্য ধীরগতির। প্রায় ২৩০০ বছর আগে ইউক্লিড একটি চমৎকার দ্রুত পদ্ধতি দিয়েছিলেন, যা এই পুনরাবৃত্তিমূলক (recursive) সূত্রের উপর ভিত্তি করে —

$$\gcd(a,b) = \gcd(b,\ a \bmod b), \qquad \gcd(a,0) = a$$

ওয়ার্কড উদাহরণ — $\gcd(252, 105)$:

ধাপ	$a$	$b$	$a \bmod b$
১	252	105	42
২	105	42	21
৩	42	21	0

যখন ভাগশেষ $0$ হয়ে যায়, তখনকার $b$ (এখানে $21$) হলো উত্তর। তাই $\gcd(252,105)=21$। মাত্র তিন ধাপে — $252$-কে ফ্যাক্টরাইজ করার চেয়ে অনেক দ্রুত।

Python

import math

def gcd_euclid(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd_euclid(a, b)

result = gcd_euclid(252, 105)
print("gcd_euclid(252, 105) =", result)
print("math.gcd(252, 105)  =", math.gcd(252, 105))
print("gcd মিলে গেছে?", result == math.gcd(252, 105))

l = lcm(252, 105)
print("lcm(252, 105) =", l)
print("যাচাই gcd × lcm == a × b?", result * l == 252 * 105)

প্রতিটি ধাপে জোড়া $(a,b)$ থেকে $(b,\ a\bmod b)$-তে যাওয়া হয়, যতক্ষণ না ভাগশেষ শূন্য হয়।

৩ · Extended Euclidean Algorithm ও Bézout's Identity

সাধারণ ইউক্লিডিয়ান অ্যালগরিদম শুধু $\gcd(a,b)$-এর মান বের করে। কিন্তু Extended Euclidean Algorithm আরও এক ধাপ এগিয়ে — এটি এমন দুটি পূর্ণসংখ্যা $x, y$ (ঋণাত্মকও হতে পারে) খুঁজে দেয় যেন —

$$ax + by = \gcd(a,b)$$

একে বলা হয় Bézout's Identity। এই $x, y$ পাওয়া যায় ইউক্লিডিয়ান অ্যালগরিদমের ধাপগুলো উল্টো দিকে (back-substitution) প্রয়োগ করে। আমাদের $\gcd(252,105)=21$ উদাহরণের জন্য —

ওয়ার্কড উদাহরণ — Back-substitution

ইউক্লিডিয়ান ধাপ থেকে জানি: $21 = 105 - 2(42)$ এবং $42 = 252 - 2(105)$। দ্বিতীয়টি প্রথমটিতে বসিয়ে —

$21 = 105 - 2(252 - 2 \times 105) = 105 - 2(252) + 4(105) = 5(105) - 2(252)$

অর্থাৎ $252(-2) + 105(5) = 21$। যাচাই: $252 \times (-2) = -504$, এবং $105 \times 5 = 525$; যোগফল $-504+525=21$ ✓। তাই $x=-2, y=5$।

এই কৌশলটিই L28-এ RSA-এর জন্য modular inverse বের করতে ব্যবহৃত হবে — কোনো সংখ্যা $a$-এর মডুলার ইনভার্স খুঁজতে হলে আমাদের এমন $x$ চাই যেন $ax \equiv 1 \pmod{n}$, এবং সেটা ঠিক Bézout's Identity-রই একটি রূপ যখন $\gcd(a,n)=1$।

ভাবনার প্রশ্ন

প্রতিটি প্রশ্ন নিজে কিছুক্ষণ ভাবুন — তারপর "→ উত্তর" চাপুন।

প্র ০১ ইউক্লিডিয়ান অ্যালগরিদম কেন সঠিক — $\gcd(a,b) = \gcd(b, a \bmod b)$ কেন সত্য?

মূল যুক্তি: $r = a \bmod b$ হলে $a = qb + r$ কোনো পূর্ণসংখ্যা $q$-এর জন্য। এখন যদি কোনো সংখ্যা $d$ একইসাথে $a$ ও $b$-কে ভাগ করে, তাহলে $d$ অবশ্যই $r = a - qb$-কেও ভাগ করবে (বিভাজ্যতার যোগ-ও-গুণের ধর্ম, L24 থেকে)। উল্টোভাবে, যদি $d$ একইসাথে $b$ ও $r$-কে ভাগ করে, তাহলে $d$ অবশ্যই $a = qb+r$-কেও ভাগ করবে। তাই $(a,b)$-এর সাধারণ ডিভাইজরের সেট ঠিক $(b,r)$-এর সাধারণ ডিভাইজরের সেটের সমান — ফলে তাদের গরিষ্ঠ সাধারণ গুণনীয়কও সমান হতে বাধ্য।

প্র ০২ দুটি সংখ্যা "সহমৌলিক" বা "coprime" হওয়া মানে কী, এবং $\gcd$-এর সাথে এর সম্পর্ক কী?

দুটি পূর্ণসংখ্যা $a,b$ coprime (বা relatively prime) হয় যদি $\gcd(a,b)=1$ হয় — অর্থাৎ তাদের মধ্যে $1$ ছাড়া আর কোনো সাধারণ ধনাত্মক গুণনীয়ক না থাকে। লক্ষণীয়, coprime হওয়ার জন্য $a$ বা $b$ প্রাইম হতে হবে এমন কোনো শর্ত নেই — যেমন $8$ ও $15$ কেউই প্রাইম নয় কিন্তু $\gcd(8,15)=1$, তাই তারা coprime। এই ধারণাটি L26-এ modular inverse-এর অস্তিত্ব নির্ধারণে এবং L27-L28-এ RSA-তে $e$ নির্বাচনের সময় সরাসরি ব্যবহৃত হবে।

প্র ০৩ Extended Euclidean Algorithm সরাসরি RSA-এর সাথে কীভাবে যুক্ত — এটি ছাড়া কি RSA কাজ করতে পারত?

না — RSA-এর private key $d$ বের করতে হয় এমন একটি সংখ্যা হিসেবে যেন $ed \equiv 1 \pmod{\varphi(n)}$ (L28-এ পুরোটা দেখব)। এটি ঠিক modular inverse বের করার সমস্যা, এবং Extended Euclidean Algorithm-ই সেই টুল যা দ্রুততম উপায়ে $e \cdot d + \varphi(n) \cdot k = 1$-এর সমাধান $d$ বের করে দেয় (Bézout's Identity-এর প্রয়োগ, $\gcd(e,\varphi(n))=1$ ধরে নিয়ে)। এই অ্যালগরিদম ছাড়া RSA-এর কী-জেনারেশন ধাপটিই সম্ভব হতো না।

অনুশীলন

হাতে হিসাব করুন: ইউক্লিডিয়ান অ্যালগরিদম দিয়ে হাতে-কলমে $\gcd(120, 45)$ বের করুন (প্রতিটি ধাপ লিখুন), তারপর উপরের কোড সেলে gcd_euclid(120, 45) চালিয়ে মিলিয়ে দেখুন।

$\gcd(120,45)$: $120 = 2(45)+30$ → $\gcd(45,30)$; $45=1(30)+15$ → $\gcd(30,15)$; $30=2(15)+0$ → থেমে যায়। উত্তর $\gcd(120,45)=15$।
যাচাই করুন: $\gcd(120,45)=15$ ব্যবহার করে $\text{lcm}(120,45)$ বের করুন সূত্র $\gcd \cdot \text{lcm} = a \cdot b$ দিয়ে, তারপর কোড সেলে lcm(120, 45) চালিয়ে যাচাই করুন।

$\text{lcm}(120,45) = \dfrac{120 \times 45}{15} = \dfrac{5400}{15} = 360$। কোড সেলের আউটপুটও $360$ দেখাবে।