معادله همنهشتی خطی و روشهای حل آن
همنهشتی چیست؟ تعریف و نمادگذاری
دو عدد صحیح $a$ و $b$ را همنهشت به پیمانه $m$ مینامیم اگر اختلاف آنها بر $m$ بخشپذیر باشد. به عبارت دیگر:
این مفهوم توسط ریاضیدان بزرگ، کارل فریدریش گاوس1، در کتاب تحقیقات حسابی پایهگذاری شد. برای نمونه $17 \equiv 5 \pmod{6}$ زیرا $17-5=12$ بر $6$ بخشپذیر است. معادله همنهشتی خطی $ax \equiv b \pmod{m}$ به ما میگوید به دنبال عدد صحیحی مانند $x$ هستیم که پس از ضرب در $a$، با $b$ همنهشت شود.
مثال عملی فرض کنید شما میخواهید باقیمانده یک عدد بزرگ مانند $7^{100}$ را بر $5$ پیدا کنید. حل معادله $7x \equiv 1 \pmod{5}$ به شما کمک میکند از قضیه فرما2 استفاده کنید. این مثال نشان میدهد که همنهشتیها فقط یک تمرین نظری نیستند، بلکه در رمزنگاری و محاسبات باقیمانده کاربرد گسترده دارند.
شرط وجود جواب و نقش بزرگترین مقسومعلیه مشترک
همه معادلات همنهشتی خطی جواب ندارند. شرط اصلی برای وجود جواب این است که $\gcd(a,m)$ بر $b$ بخشپذیر باشد. به عبارت دقیقتر:
برای درک بهتر، معادله $2x \equiv 3 \pmod{4}$ را بررسی کنید: $\gcd(2,4)=2$ و $2 \nmid 3$، بنابراین هیچ جوابی ندارد. اما معادله $2x \equiv 2 \pmod{4}$ جواب دارد زیرا $2 \mid 2$. در این حالت جوابها عبارتند از $x \equiv 1 \pmod{2}$ که معادل دو جواب $x \equiv 1,3 \pmod{4}$ است.
روشهای حل: از آزمون و خطا تا الگوریتم اقلیدس
برای حل معادله $ax \equiv b \pmod{m}$ سه روش رایج وجود دارد:
روش اول: جایگذاری اعداد $0,1,\ldots,m-1$ به ترتیب در $x$ تا زمانی که معادله برقرار شود. این روش فقط برای پیمانههای کوچک مناسب است.
روش دوم: استفاده از وارون ضربی3. اگر $\gcd(a,m)=1$ باشد، آنگاه $a$ وارون یکتایی به پیمانه $m$ دارد. با ضرب دو طرف معادله در وارون $a$، جواب به دست میآید: $x \equiv a^{-1}b \pmod{m}$.
روش سوم: الگوریتم تعمیمیافته اقلیدس4 که برای هر حالتی (حتی زمانی که $\gcd(a,m) \neq 1$) قابل استفاده است و همزمان $\gcd$ و ضرایب ترکیب خطی را محاسبه میکند.
| نام روش | شرایط مناسب | مزایا | معایب |
|---|---|---|---|
| جایگذاری متوالی | $m$ کوچک (کمتر از $10$) | بسیار ساده و شهودی | برای پیمانههای بزرگ غیرعملی |
| وارون ضربی | $\gcd(a,m)=1$ | جواب مستقیم و سریع | فقط برای اعداد نسبتاً اول کار میکند |
| الگوریتم تعمیمیافته اقلیدس | همیشه (هر $a,m$) | جامع، تعداد جوابها را مشخص میکند | نیاز به چند مرحله محاسبه دارد |
حل گامبهگام با مثال عددی ملموس
معادله $6x \equiv 4 \pmod{10}$ را در نظر بگیرید. ابتدا شرط وجود جواب را بررسی میکنیم:
$\gcd(6,10)=2$ و $2 \mid 4$ بنابراین جواب وجود دارد و تعداد جوابهای متمایز برابر $2$ است (به پیمانه $10$).
مرحله اول: سادهسازی معادله با تقسیم بر $d=2$. یعنی معادله جدید $3x \equiv 2 \pmod{5}$ را حل میکنیم. توجه کنید پیمانه نیز بر $2$ تقسیم شده است.
مرحله دوم: چون $\gcd(3,5)=1$، وارون $3$ را به پیمانه $5$ پیدا میکنیم. آزمون و خطا نشان میدهد $3 \times 2 = 6 \equiv 1 \pmod{5}$، بنابراین وارون برابر $2$ است.
مرحله سوم: دو طرف معادله $3x \equiv 2$ را در $2$ ضرب میکنیم: $x \equiv 4 \pmod{5}$.
مرحله چهارم: بازگشت به پیمانه اصلی $10$. جوابها عبارتند از $x \equiv 4$ و $x \equiv 9 \pmod{10}$. درستی را بررسی کنید: $6\times4=24\equiv4$ و $6\times9=54\equiv4$ (باقیمانده بر $10$ برابر $4$).
کاربرد در رمزنگاری و محاسبات روزمره
یکی از مهمترین کاربردهای معادلات همنهشتی در سیستم رمزنگاری آراسا5 است. در این سیستم، فرآیند رمزگشایی به حل معادله $ed \equiv 1 \pmod{\varphi(n)}$ تبدیل میشود که در آن $e$ کلید عمومی و $d$ کلید خصوصی است. همچنین در محاسبه روز ساعت (پیمانه $12$ یا $24$) و تشخیص رقم کنترلی6 در بارکدها و شماره شبا، از همین معادلات استفاده میشود.
مثال واقعی فرض کنید میخواهیم باقیمانده $5^{2023}$ را بر $7$ بیابیم. با استفاده از قضیه کوچک فرما میدانیم $5^{6} \equiv 1 \pmod{7}$. توان $2023$ را بر $6$ تقسیم میکنیم: باقیمانده $2023 \mod 6 = 1$. بنابراین $5^{2023} \equiv 5^{1} \equiv 5 \pmod{7}$. این روش ساده، حاصل از توانایی حل معادلات همنهشتی است.
چالشهای مفهومی
۱) آیا معادله $0x \equiv 5 \pmod{7}$ جواب دارد؟
خیر، زیرا سمت چپ همیشه صفر است و معادله به $0 \equiv 5 \pmod{7}$ تبدیل میشود که نادرست است. شرط $\gcd(0,7)=7$ باید بر $5$ بخشپذیر باشد، که نیست.
۲) چرا گاهی میگوییم معادله دو جواب دارد اما هر دو جواب به پیمانه اصلی یکسان هستند؟
منظور از جوابهای متمایز، اعداد غیرهمنهشت به پیمانه $m$ هستند. مثلاً در مثال $6x \equiv 4 \pmod{10}$، اعداد $4$ و $14$ یک جواب محسوب میشوند چون $14 \equiv 4 \pmod{10}$، بنابراین فقط جوابهای $4$ و $9$ را میشماریم.
۳) آیا میتوان معادله $4x \equiv 6 \pmod{10}$ را با روش وارون ضربی حل کرد؟
خیر، زیرا $\gcd(4,10)=2 \neq 1$، بنابراین $4$ وارون ضربی به پیمانه $10$ ندارد. اما با سادهسازی (تقسیم بر $2$) به $2x \equiv 3 \pmod{5}$ میرسیم که در آن $\gcd(2,5)=1$ و میتوان از وارون ($3$) استفاده کرد: $x \equiv 4 \pmod{5}$ که معادل $x \equiv 4,9 \pmod{10}$ است.
پاورقی
1 کارل فریدریش گاوس (Carl Friedrich Gauss): ریاضیدان آلمانی که نظریه اعداد مدرن را با کتاب «تحقیقات حسابی» بنیان نهاد.
2 قضیه کوچک فرما (Fermat's Little Theorem): اگر $p$ عدد اول و $a$ بر $p$ بخشپذیر نباشد، آنگاه $a^{p-1} \equiv 1 \pmod{p}$.
3 وارون ضربی (Modular Inverse): عدد صحیح $a^{-1}$ به گونهای که $a \times a^{-1} \equiv 1 \pmod{m}$.
4 الگوریتم تعمیمیافته اقلیدس (Extended Euclidean Algorithm): روشی برای یافتن ضرایب $x,y$ در رابطه $ax + by = \gcd(a,b)$.
5 رمزنگاری آراسا (RSA Cryptography): یکی از اولین و پرکاربردترین سامانههای رمزنگاری کلید عمومی که بر پایه دشواری فاکتورگیری اعداد بزرگ استوار است.
6 رقم کنترلی (Checksum Digit): رقمی که برای تشخیص خطا در شمارههای شناسایی مانند شبا، بارکد و شماره کارت بانکی به کار میرود.
