রৈখিক সর্বসমতা সমীকরণ#
এই সমীকরণটি নিম্নলিখিত আকারের:
$$a \cdot x \equiv b \pmod n,$$যেখানে $a$, $b$ ও $n$ প্রদত্ত পূর্ণসংখ্যা এবং $x$ একটি অজানা পূর্ণসংখ্যা।
$[0, n-1]$ ব্যবধান থেকে $x$-এর মান নির্ণয় করতে হবে (স্পষ্টতই, সম্পূর্ণ সংখ্যারেখায় অসীম সংখ্যক সমাধান থাকতে পারে যারা পরস্পর থেকে $n \cdot k$ পার্থক্যে থাকবে, যেখানে $k$ যেকোনো পূর্ণসংখ্যা)। যদি সমাধান অনন্য না হয়, তাহলে আমরা দেখব কিভাবে সকল সমাধান পাওয়া যায়।
বিপরীত উপাদান নির্ণয়ের মাধ্যমে সমাধান#
প্রথমে একটি সরল ক্ষেত্র বিবেচনা করি যেখানে $a$ ও $n$ সহমৌলিক ($\gcd(a, n) = 1$)। তখন $a$-এর ইনভার্স বের করা যায়, এবং সমীকরণের উভয় পক্ষকে ইনভার্স দিয়ে গুণ করলে একটি অনন্য সমাধান পাওয়া যায়।
$$x \equiv b \cdot a ^ {- 1} \pmod n$$এখন সেই ক্ষেত্রটি বিবেচনা করি যেখানে $a$ ও $n$ সহমৌলিক নয় ($\gcd(a, n) \ne 1$)। তখন সমাধান সবসময় বিদ্যমান থাকবে না (উদাহরণস্বরূপ $2 \cdot x \equiv 1 \pmod 4$ এর কোনো সমাধান নেই)।
মনে করি $g = \gcd(a, n)$, অর্থাৎ $a$ ও $n$-এর গসাগু (যা এই ক্ষেত্রে একের চেয়ে বড়)।
তখন, যদি $b$, $g$ দ্বারা বিভাজ্য না হয়, তাহলে কোনো সমাধান নেই। প্রকৃতপক্ষে, যেকোনো $x$-এর জন্য সমীকরণের বাম পক্ষ $a \cdot x \pmod n$ সবসময় $g$ দ্বারা বিভাজ্য, অথচ ডান পক্ষ তা দ্বারা বিভাজ্য নয়, অতএব কোনো সমাধান নেই।
যদি $g$, $b$-কে ভাগ করে, তাহলে সমীকরণের উভয় পক্ষকে $g$ দিয়ে ভাগ করে (অর্থাৎ $a$, $b$ ও $n$-কে $g$ দিয়ে ভাগ করে), আমরা একটি নতুন সমীকরণ পাই:
$$a^\prime \cdot x \equiv b^\prime \pmod{n^\prime}$$যেখানে $a^\prime$ ও $n^\prime$ ইতোমধ্যেই পরস্পর সহমৌলিক, এবং এরকম সমীকরণ সমাধান করা আমরা ইতোমধ্যে শিখেছি। আমরা $x$-এর সমাধান হিসেবে $x^\prime$ পাই।
এটি স্পষ্ট যে এই $x^\prime$ মূল সমীকরণেরও একটি সমাধান হবে। তবে এটি একমাত্র সমাধান হবে না। দেখানো যায় যে মূল সমীকরণে ঠিক $g$টি সমাধান আছে, এবং সেগুলো এরকম দেখতে:
$$x_i \equiv (x^\prime + i\cdot n^\prime) \pmod n \quad \text{for } i = 0 \ldots g-1$$সংক্ষেপে বলা যায়, রৈখিক সর্বসমতা সমীকরণের সমাধানের সংখ্যা হয় $g = \gcd(a, n)$ অথবা শূন্য।
এক্সটেন্ডেড ইউক্লিডিয়ান অ্যালগরিদম দিয়ে সমাধান#
আমরা রৈখিক সর্বসমতাটিকে নিম্নলিখিত ডায়োফ্যান্টাইন সমীকরণে পুনর্লিখন করতে পারি:
$$a \cdot x + n \cdot k = b,$$যেখানে $x$ ও $k$ অজানা পূর্ণসংখ্যা।
এই সমীকরণ সমাধানের পদ্ধতি সংশ্লিষ্ট নিবন্ধ রৈখিক ডায়োফ্যান্টাইন সমীকরণ-তে বর্ণনা করা হয়েছে এবং এটি এক্সটেন্ডেড ইউক্লিডিয়ান অ্যালগরিদম প্রয়োগের উপর ভিত্তি করে।
এটি একটি পাওয়া সমাধান থেকে এই সমীকরণের সকল সমাধান পাওয়ার পদ্ধতিও বর্ণনা করে, এবং এই পদ্ধতিটি, সতর্কভাবে বিবেচনা করলে, পূর্ববর্তী বিভাগে বর্ণিত পদ্ধতির সম্পূর্ণ সমতুল্য।