ফারমেটস লিটল থিওরেম (Fermat's Little Theorem)
ফারমেটস লিটল থিওরেম মৌলিক সংখ্যা তত্ত্বের একটি মৌলিক থিওরেম যা ইন্টিজারের মডুলো প্রাইম নম্বর পাওয়ার গণনা করতে সাহায্য করে। এটি অয়লারের থিওরেমের একটি বিশেষ কেস, এবং প্রাইম্যালিটি টেস্টিং ও পাবলিক-কী ক্রিপ্টোগ্রাফি যেমন প্রয়োগে অপরিহার্য।
থিওরেমের স্টেটমেন্ট
যদি P একটি প্রাইম সংখ্যা হয় এবং a একটি পজিটিভ ইন্টিজার যা P দ্বারা বিভাজ্য নয়, তবে:
aP-1 ≡ 1 (mod P)
দ্বিতীয় শর্ত: যদি P প্রাইম এবং a ইন্টিজার হয়, তবে aP ≡ a (mod P)।
প্রুফ (Proof)
Zp = {0, 1, ..., P-1} ইন্টিজার সেট। a দিয়ে মডুলো P গুণ করলে রেজাল্টে Zp-এর সব এলিমেন্ট কিছু অর্ডারে পাওয়া যায়, আরও a × 0 ≡ 0 (mod P)।
তাহলে (P-1) সংখ্যা {a mod P, 2a mod P, ..., (P-1)a mod P} হলো {1, 2, ..., P-1} সেটের একটি পারমিউটেশন।
দুটি সেটের এলিমেন্টগুলো গুণ করে মডুলো P নিলে:
a × 2a × ... × (P-1)a ≡ [1 × 2 × ... × (P-1)] (mod P) (P-1)! aP-1 ≡ (P-1)! (mod P) aP-1 ≡ 1 (mod P) [যেহেতু (P-1)! এবং P রিলেটিভলি প্রাইম]
উদাহরণ
- উদাহরণ ১: 6¹⁰ mod 11 = 1 (এখানে p=11, ফারমেটস লিটল থিওরেমের প্রথম সংস্করণ)।
- উদাহরণ ২: 3¹² mod 11 = ?
3¹² mod 11 = (3¹¹ × 3) mod 11 = (3¹¹ mod 11) × (3 mod 11) = (3 × 3) mod 11 = 9
ব্যবহারিক প্রয়োগ
ফারমেটস লিটল থিওরেম কখনও কখনও এক্সপোনেনশিয়েশন সমস্যা দ্রুত সমাধান করতে সাহায্য করে। প্রাইম্যালিটি টেস্টিং, RSA ক্রিপ্টোগ্রাফি, মডুলার এক্সপোনেনশিয়েশন অপ্টিমাইজেশনে এটি ব্যাপকভাবে ব্যবহৃত হয়।
