জিসিডি ও এলসিএম ক্যালকুলেটর

সম্পূর্ণ ইউক্লিডীয় অ্যালগরিদমের ধাপসহ গরিষ্ঠ সাধারণ গুণনীয়ক (গসাগু / GCD) এবং লঘিষ্ঠ সাধারণ গুণিতক (লসাগু / LCM) গণনা করুন। দুই বা ততধিক সংখ্যা সমর্থন করে।

জিসিডি ও এলসিএম ক্যালকুলেটর কী?

গরিষ্ঠ সাধারণ গুণনীয়ক (গসাগু / GCD) এবং লঘিষ্ঠ সাধারণ গুণিতক (লসাগু / LCM) হলো প্রাথমিক সংখ্যাতত্ত্বের (number theory) দুটি অত্যন্ত গুরুত্বপূর্ণ ধারণা, যার ব্যবহার মাধ্যমিক বিদ্যালয়ের ভগ্নাংশ সহজীকরণ থেকে শুরু করে ইন্টারনেট সুরক্ষিত রাখার ক্রিপ্টোগ্রাফিক অ্যালগরিদম পর্যন্ত বিস্তৃত।

খ্রিস্টপূর্ব ৩০০ অব্দের দিকে ইউক্লিড দ্বারা বর্ণিত 'ইউক্লিডীয় অ্যালগরিদম' হলো গণিতের অন্যতম প্রাচীন এবং সবচেয়ে দক্ষ অ্যালগরিদম। এটি অত্যন্ত দ্রুতগতিতে $O(\log(\min(a,b)))$ ধাপে গসাগু গণনা করে, এমনকি অনেক বড় সংখ্যার ক্ষেত্রেও দ্রুত ফলাফল দেয়। এই অ্যালগরিদমটি ভাগশেষ শূন্য না হওয়া পর্যন্ত বারবার এই সূত্রটি প্রয়োগ করে: $\text{GCD}(a, b) = \text{GCD}(b, a \bmod b)$।

এই ক্যালকুলেটরটি দুটি সংখ্যার জন্য সম্পূর্ণ ইউক্লিডীয় অ্যালগরিদম ধাপে ধাপে দেখায় এবং সাধারণীকৃত সূত্র $\text{GCD}(a, b, c) = \text{GCD}(\text{GCD}(a, b), c)$ ব্যবহার করে একাধিক সংখ্যার তালিকার জন্যও গসাগু ও লসাগু গণনা করে।

সূত্র

ইউক্লিডীয় অ্যালগরিদম:

$\text{GCD}(a, b) = \text{GCD}(b, a \bmod b)$ (যতক্ষণ না $b = 0$ হয়)

গসাগু থেকে লসাগু:

$\text{LCM}(a, b) = \frac{|a \times b|}{\text{GCD}(a, b)}$

একাধিক সংখ্যার ক্ষেত্রে:

$\text{GCD}(a, b, c) = \text{GCD}(\text{GCD}(a, b), c)$

$\text{LCM}(a, b, c) = \text{LCM}(\text{LCM}(a, b), c)$

কীভাবে গণনা করবেন

দুটি ধনাত্মক পূর্ণসংখ্যা a এবং b লিখুন।
পূর্ণসংখ্যার ভাগ প্রক্রিয়া প্রয়োগ করুন: a = q×b + r।
a-কে b দ্বারা এবং b-কে r দ্বারা প্রতিস্থাপন করুন। r = 0 না হওয়া পর্যন্ত এর পুনরাবৃত্তি করুন।
সর্বশেষ অ-শূণ্য (non-zero) ভাগশেষটিই হলো গসাগু (GCD)।
মৌলিক সূত্রটি ব্যবহার করে লসাগু বা $\text{LCM} = \frac{|a \times b|}{\text{GCD}}$ গণনা করুন।
তিনটি বা তার বেশি সংখ্যার জন্য 'একাধিক সংখ্যা' (Multiple Numbers) মোড ব্যবহার করুন।

উদাহরণ

গসাগু বা GCD(48, 18) নির্ণয়: 48 = 2×18 + 12 → 18 = 1×12 + 6 → 12 = 2×6 + 0। সুতরাং গসাগু = 6। লসাগু বা LCM = |48×18|/6 = 864/6 = 144। যাচাইকরণ: 144/48 = 3 ✓, 144/18 = 8 ✓।

মূল শব্দ ব্যাখ্যা

GCD / গসাগু: সবচেয়ে বড় পূর্ণসংখ্যা যা দ্বারা উভয় সংখ্যাকেই ভাগশেষ ছাড়া ভাগ করা যায়
LCM / লসাগু: সবচেয়ে ছোট ধনাত্মক পূর্ণসংখ্যা যা উভয় সংখ্যা দ্বারাই বিভাজ্য
Co-prime / সহ-মৌলিক: এমন দুটি সংখ্যা যাদের গসাগু = ১, অর্থাৎ যাদের মধ্যে কোনো সাধারণ মৌলিক উৎপাদক নেই
Euclidean algorithm / ইউক্লিডীয় অ্যালগরিদম: বারবার ভাগ প্রক্রিয়ার মাধ্যমে গসাগু গণনা করার একটি প্রাচীন অ্যালগরিদম
Modulo operation / মডুলো অপারেশন: a mod b হলো a-কে b দ্বারা ভাগ করলে প্রাপ্ত ভাগশেষ
Divisibility / বিভাজ্যতা: a দ্বারা b বিভাজ্য হবে যদি b/a-এর কোনো ভাগশেষ না থাকে

সাধারণ ব্যবহারের ক্ষেত্র

ভগ্নাংশ সহজীকরণ: লব ও হর উভয়কে তাদের গসাগু বা GCD(a, b) দ্বারা ভাগ করে a/b-কে ছোট করা
ভিন্ন হর বিশিষ্ট ভগ্নাংশের যোগ: হরগুলোর লসাগু (LCM) বের করা
সময়সূচী বা শিডিউলিং: দুটি পুনরাবৃত্তিমূলক ঘটনা পরবর্তীকালে কখন একসাথে ঘটবে তা নির্ণয় করা
RSA কী জেনারেশন: এক্সপোনেন্ট e যেন φ(n)-এর সাথে সহ-মৌলিক (co-prime) হয় তা যাচাই করা
মেকানিক্যাল ইঞ্জিনিয়ারিংয়ে গিয়ার রেশিও (gear ratio) সংক্রান্ত সমস্যা সমাধান
টাইলসের প্যাটার্ন ডিজাইন: সবচেয়ে ছোট পুনরাবৃত্তিমূলক একক বা অংশটি খুঁজে বের করা

সচরাচর জিজ্ঞাসিত প্রশ্ন

গসাগু (GCD) কী এবং এটি কীভাবে গণনা করা হয়?

GCD (Greatest Common Divisor) বা গসাগু হলো সবচেয়ে বড় ধনাত্মক পূর্ণসংখ্যা যা দ্বারা কোনো ভাগশেষ ছাড়া a এবং b উভয় সংখ্যাকেই ভাগ করা যায়। ইউক্লিডীয় অ্যালগরিদম এটি দক্ষতার সাথে গণনা করে: b = 0 না হওয়া পর্যন্ত বারবার (a, b)-কে (b, a mod b) দ্বারা প্রতিস্থাপন করতে হয়। সর্বশেষ অ-শূন্য মানটিই হলো গসাগু।

লসাগু (LCM) কী এবং এটি কী কাজে ব্যবহৃত হয়?

LCM (Least Common Multiple) বা লসাগু হলো সবচেয়ে ছোট ধনাত্মক পূর্ণসংখ্যা যা a এবং b উভয় সংখ্যা দ্বারাই বিভাজ্য। এটি ভিন্ন হর বিশিষ্ট ভগ্নাংশের যোগফল নির্ণয়, সময়সূচী বা শিডিউলিং সংক্রান্ত সমস্যা সমাধান এবং সঙ্গীত তত্ত্বের (music theory) ক্ষেত্রে ব্যবহৃত হয়।

গসাগু (GCD) এবং লসাগুর (LCM) মধ্যে সম্পর্ক কী?

$\text{GCD}(a, b) \times \text{LCM}(a, b) = |a \times b|$। আপনি একবার গসাগু জেনে গেলে, লসাগু হবে কেবল $\frac{|a \times b|}{\text{GCD}(a, b)}$। গুণিতকগুলোর তালিকা তৈরি করার চেয়ে এই পদ্ধতিটি অনেক বেশি দক্ষ।

সহ-মৌলিক (co-prime) বলতে কী বোঝায়?

দুটি সংখ্যার গসাগু (GCD) ১ হলে তাদের সহ-মৌলিক (co-prime বা relatively prime) বলা হয়—অর্থাৎ তাদের মধ্যে কোনো সাধারণ মৌলিক উৎপাদক থাকে না। মডুলার অ্যারিথমেটিক, ক্রিপ্টোগ্রাফি এবং চাইনিজ রিমেইন্ডার থিওরেমের (Chinese Remainder Theorem) ক্ষেত্রে সহ-মৌলিকতার ধারণাটি অত্যন্ত মৌলিক ও গুরুত্বপূর্ণ।

জিসিডি ও এলসিএম ক্যালকুলেটর