خاصیت توان همنهشتی: اگر a ≡ b (mod m)، آنگاه aⁿ ≡ bⁿ (mod m)
در این مقاله با خاصیت توان همنهشتی (Congruence) آشنا میشوید. اگر دو عدد صحیح به پیمانهٔ m همنهشت باشند، آنگاه هر توان طبیعی از آن دو عدد نیز به همان پیمانه همنهشت خواهد بود. این قاعده که با عبارت $a \equiv b \pmod{m} \Rightarrow a^n \equiv b^n \pmod{m}$ نمایش داده میشود، پایهٔ بسیاری از محاسبات باقیمانده، رمزنگاری و آزمونهای بخشپذیری است. ما با زبانی ساده و مثالهای گوناگون، از جمله جدول مقایسه و پرسشهای چالشی، این ویژگی را بررسی میکنیم.
آشنایی با مفهوم همنهشتی (همنهشتی مدولار)
پیش از بررسی خاصیت توان، لازم است بدانیم همنهشتی به چه معناست. دو عدد صحیح a و b را نسبت به پیمانهٔ m (m \gt 0) همنهشت میگوییم هرگاه اختلاف آنها بر m بخشپذیر باشد. به عبارت دیگر:
برای نمونه، 17 \equiv 5 \pmod{6} زیرا 17-5=12 و 12 بر 6 بخشپذیر است. همچنین -3 \equiv 4 \pmod{7} چون -3-4=-7 بر 7 تقسیم میشود. این مفهوم به ما اجازه میدهد اعداد بزرگ را با باقیماندهٔ کوچکتری جایگزین کنیم.
بیان و اثبات خاصیت توان همنهشتی
حال به سراغ قضیهٔ اصلی میرویم. اگر a \equiv b \pmod{m} آنگاه برای هر عدد طبیعی n داریم: $a^n \equiv b^n \pmod{m}$. اثبات این ویژگی با استفاده از استقرای ریاضی انجام میشود.
- پایهٔ استقرا: برای n=1 گزاره به صورت $a \equiv b \pmod{m}$ که طبق فرض درست است.
- گام استقرا: فرض کنیم برای n=k داشته باشیم $a^k \equiv b^k \pmod{m}$. حال میخواهیم نشان دهیم $a^{k+1} \equiv b^{k+1} \pmod{m}$.
مینویسیم: $a^{k+1} - b^{k+1} = a \cdot a^k - b \cdot b^k$. با افزودن و کم کردن $b \cdot a^k$ داریم:
از فرض $a \equiv b \pmod{m}$ نتیجه میشود $m \mid (a-b)$. همچنین طبق فرض استقرا $m \mid (a^k - b^k)$. از آنجا که ترکیب خطی مضارب m نیز بر m بخشپذیر است، $m \mid (a^{k+1} - b^{k+1})$ ثابت میشود. بنابراین $a^{k+1} \equiv b^{k+1} \pmod{m}$.
مقایسهٔ اعداد تواندار پیش و پس از سادهسازی
برای درک بهتر، جدول زیر را ببینید که مقادیر a^n و b^n را برای چند پیمانهٔ متفاوت نشان میدهد. همیشه a \equiv b \pmod{m} گرفته شده است.
| پیمانه (m) | a و b (همنهشت) | n | aⁿ (باقیمانده) | bⁿ (باقیمانده) |
|---|---|---|---|---|
| 5 | 7 \equiv 2 | 3 | 343 ≡ 3 | 8 ≡ 3 |
| 4 | 10 \equiv 2 | 4 | 10000 ≡ 0 | 16 ≡ 0 |
| 7 | 9 \equiv 2 | 5 | 59049 ≡ 4 | 32 ≡ 4 |
کاربرد عملی: محاسبهٔ باقیماندهٔ توانهای بزرگ
فرض کنید میخواهیم باقیماندهٔ $7^{100}$ را بر 5 بیابیم. محاسبهٔ مستقیم $7^{100}$ غیرممکن است. اما میدانیم $7 \equiv 2 \pmod{5}$. با استفاده از خاصیت توان همنهشتی:
اکنون به دنبال الگویی از توانهای 2 modulo 5 میگردیم: $2^1=2$، $2^2=4$، $2^3=8 \equiv 3$، $2^4=16 \equiv 1$. پس دورهٔ تناوب 4 است. از آنجا که $100 = 4 \times 25$، داریم $2^{100} \equiv 1 \pmod{5}$. در نتیجه $7^{100} \equiv 1 \pmod{5}$. این روش در رمزنگاری RSA و الگوریتمهای hash1 کاربرد گسترده دارد.
چالشهای مفهومی
خیر، عکس قضیه لزوماً درست نیست. برای نمونه، $2^2=4$ و $4^2=16$ را در نظر بگیرید. $4 \equiv 16 \pmod{6}$ (هر دو باقیماندهٔ 4) اما $2 \equiv 4 \pmod{6}$ نادرست است. بنابراین شرط توان، بازگشت به شرط پایه را تضمین نمیکند.
بله، خاصیت توان همنهشتی برای هر پیمانهٔ صحیح m \gt 0 (چه اول، چه مرکب) برقرار است. اثباتی که ارائه شد تنها بر پایهٔ بخشپذیری بود و به اول بودن m نیازی ندارد.
خیر. خاصیت توان همنهشتی تنها روی پایه اعمال میشود، نه روی نما. برای کاهش نما باید از قضیهٔ اویلر2 یا قضیهٔ فرما3 استفاده کرد. مثلاً میدانیم $a^{\phi(m)} \equiv 1 \pmod{m}$ اگر $\gcd(a,m)=1$، آنگاه نما را میتوان مدول $\phi(m)$ کاهش داد.
جمعبندی
پاورقی
1 تابع درهمساز (Hash function): تابعی که دادهای با اندازه دلخواه را به رشتهای با طول ثابت تبدیل میکند و در امنیت اطلاعات کاربرد دارد.
2 قضیهٔ اویلر (Euler's theorem): اگر $\gcd(a,m)=1$ آنگاه $a^{\phi(m)} \equiv 1 \pmod{m}$ که $\phi(m)$ تابع اویلر است.
3 قضیهٔ کوچک فرما (Fermat's little theorem): اگر $p$ عدد اول و $a$ بر $p$ بخشپذیر نباشد، آنگاه $a^{p-1} \equiv 1 \pmod{p}$.