پرش به محتویات

معادله همنهشتی خطی

این معادله به شکل زیر است:

$$a \cdot x \equiv b \pmod n,$$

که در آن $a$، $b$ و $n$ اعداد صحیح داده شده و $x$ یک عدد صحیح نامعلوم است.

لازم است مقدار $x$ را در بازه $[0, n-1]$ پیدا کنیم (بدیهی است که در کل خط اعداد، بی‌نهایت جواب می‌تواند وجود داشته باشد که با یکدیگر به اندازه $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$ را بشمارد (b بر g بخش‌پذیر باشد)، آنگاه با تقسیم طرفین معادله بر $g$ (یعنی تقسیم $a$، $b$ و $n$ بر $g$)، به معادله جدیدی می‌رسیم:

$$a^\prime \cdot x \equiv b^\prime \pmod{n^\prime}$$

که در آن $a^\prime$ و $n^\prime$ نسبت به هم اول هستند، و ما قبلاً یاد گرفته‌ایم که چگونه با چنین معادله‌ای برخورد کنیم. ما $x^\prime$ را به عنوان جواب برای $x$ به دست می‌آوریم.

واضح است که این $x^\prime$ جوابی برای معادله اصلی نیز خواهد بود. اما این تنها جواب نخواهد بود. می‌توان نشان داد که معادله اصلی دقیقاً $g$ جواب دارد، و آنها به این شکل خواهند بود:

$$x_i \equiv (x^\prime + i\cdot n^\prime) \pmod n \quad \text{برای } i = 0 \ldots g-1$$

به طور خلاصه، می‌توان گفت که تعداد جواب‌های معادله همنهشتی خطی برابر با $g = \gcd(a, n)$ یا صفر است.

حل با استفاده از الگوریتم تعمیم‌یافته اقلیدسی

می‌توانیم همنهشتی خطی را به صورت معادله سیاله (Diophantine) زیر بازنویسی کنیم:

$$a \cdot x + n \cdot k = b,$$

که در آن $x$ و $k$ اعداد صحیح نامعلوم هستند.

روش حل این معادله در مقاله مربوطه معادلات سیاله خطی توضیح داده شده است و شامل به کارگیری الگوریتم تعمیم‌یافته اقلیدسی است.

همچنین روش به دست آوردن تمام جواب‌های این معادله از روی یک جواب پیدا شده را توصیف می‌کند، و اتفاقاً این روش، با بررسی دقیق، کاملاً معادل روشی است که در بخش قبل توضیح داده شد.