রৈখিক সর্বসমতা ইকুয়েশন#
এই ইকুয়েশনটি নিচের আকারের:
$$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$ অজানা পূর্ণসংখ্যা।
এই ইকুয়েশন সমাধানের পদ্ধতি সংশ্লিষ্ট আর্টিকেল রৈখিক ডায়োফ্যান্টাইন ইকুয়েশন-তে বর্ণনা করা হয়েছে এবং এটা এক্সটেন্ডেড ইউক্লিডিয়ান অ্যালগরিদম প্রয়োগের উপর ভিত্তি করে।
এটা একটি পাওয়া সমাধান থেকে এই ইকুয়েশনের সকল সমাধান পাওয়ার পদ্ধতিও বর্ণনা করে, এবং এই পদ্ধতিটি, সতর্কভাবে কনসিডার করলে, আগের বিভাগে বর্ণিত পদ্ধতির সম্পূর্ণ সমতুল্য।