ফার্মার লিটল থিওরেম ও অয়লার'স থিওরেম
এই পাঠে যা শিখবেন
- Fermat's Little Theorem-এর বিবৃতি ও একটি সংখ্যাগত উদাহরণে যাচাই
- Euler's Totient Function $\varphi(n)$-এর সংজ্ঞা ও প্রাইম-সম্পর্কিত সূত্র
- Euler's Theorem কীভাবে Fermat-এর থিওরেমকে সাধারণীকরণ করে
- কেন এই দুটি থিওরেম সরাসরি RSA-এর ভিত্তি — L28-এর প্রস্তুতি
- Python দিয়ে উভয় থিওরেম সংখ্যাগতভাবে যাচাই
১ · Fermat's Little Theorem
Fermat's Little TheoremFermat's Little Theoremযদি $p$ একটি প্রাইম সংখ্যা এবং $a$ এমন একটি পূর্ণসংখ্যা যেন $\gcd(a,p)=1$, তাহলে $a^{p-1} \equiv 1 \pmod p$। ১৭ শতকে পিয়ের দ্য ফার্মা আবিষ্কার করেন। নাম্বার থিওরির অন্যতম সুন্দর ফলাফল —
$$\text{যদি } p \text{ প্রাইম এবং } \gcd(a,p)=1, \text{ তাহলে } a^{p-1} \equiv 1 \pmod{p}$$
ওয়ার্কড উদাহরণ: $a=2, p=7$। $2^6 = 64$। এবং $64 = 9 \times 7 + 1$ — তাই $64 \equiv 1 \pmod 7$। যাচাই সম্পন্ন: $2^{7-1} \equiv 1 \pmod 7$ ✓।
এই থিওরেম বলছে — একটি প্রাইম মডুলাসে, coprime সংখ্যার ঘাত একটি নির্দিষ্ট বিন্দুতে (ঠিক $p-1$ ঘাতে) "চক্র সম্পূর্ণ করে" $1$-এ ফিরে আসে। এই "পর্যাবৃত্তি (periodicity)"-ই মডুলার এক্সপোনেনশিয়েশনের পুরো আচরণ নিয়ন্ত্রণ করে, এবং এখান থেকেই RSA-এর কী-জেনারেশনের গাণিতিক নিশ্চয়তা আসে।
২ · Euler's Totient Function φ(n)
Fermat-এর থিওরেম শুধু প্রাইম মডুলাসের জন্য কাজ করে। সাধারণ (কম্পোজিটসহ) যেকোনো মডুলাসের জন্য সাধারণীকরণ করতে অয়লার একটি নতুন ফাংশন সংজ্ঞায়িত করেন —
$\varphi(n)$Euler's Totient Function$1$ থেকে $n$ পর্যন্ত সংখ্যাগুলোর মধ্যে কতগুলো $n$-এর সাথে coprime (অর্থাৎ $\gcd=1$) তার গণনা। হলো $\{1, 2, \ldots, n\}$-এর মধ্যে $n$-এর সাথে coprime সংখ্যার গণনা।
- যদি $p$ প্রাইম হয়: $\varphi(p) = p - 1$ (কারণ $1$ থেকে $p-1$ পর্যন্ত প্রতিটি সংখ্যাই $p$-এর সাথে coprime — শুধু $p$ নিজে বাদে)।
- যদি $n = pq$ হয় (দুটি ভিন্ন প্রাইম $p,q$-এর গুণফল): $\varphi(n) = (p-1)(q-1)$। এটি সত্য হয় $\varphi$-এর multiplicativity ধর্মের কারণে — coprime $m,n$-এর জন্য $\varphi(mn)=\varphi(m)\varphi(n)$ (এই ধর্মের পূর্ণ প্রমাণ এই পাঠের পরিসরের বাইরে, কিন্তু এটিই RSA-এর n=pq কাঠামোর জন্য সরাসরি প্রযোজ্য সূত্র)।
ওয়ার্কড উদাহরণ: $n=15=3\times5$। ব্রুট-ফোর্স গণনা: $1$ থেকে $15$-এর মধ্যে $3$ বা $5$ দ্বারা বিভাজ্য নয় এমন সংখ্যাগুলো হলো $\{1,2,4,7,8,11,13,14\}$ — মোট $8$টি। সূত্র থেকেও: $\varphi(15)=(3-1)(5-1)=2\times4=8$ ✓ — মিলে যায়।
৩ · Euler's Theorem — Fermat-এর সাধারণীকরণ
$$\text{যদি } \gcd(a,n)=1, \text{ তাহলে } a^{\varphi(n)} \equiv 1 \pmod{n}$$
লক্ষ করুন, যখন $n=p$ (প্রাইম), তখন $\varphi(p)=p-1$ — এবং Euler's Theorem হুবহু Fermat's Little Theorem-এ পরিণত হয়। তাই Fermat-এর থিওরেম হলো Euler's Theorem-এর একটি বিশেষ কেস, যেখানে মডুলাস প্রাইম।
import math
# Fermat's Little Theorem যাচাই — একাধিক (a, p) জোড়ার জন্য
pairs = [(2, 7), (3, 11), (5, 13)]
for a, p in pairs:
check = pow(a, p - 1, p)
print(f"{a}^{p-1} mod {p} = {check} (প্রাইম p={p}, gcd(a,p)=1)")
print()
# Euler's Totient Function — ব্রুট ফোর্স গণনা
def phi_bruteforce(n):
return sum(1 for k in range(1, n + 1) if math.gcd(k, n) == 1)
n = 15 # 15 = 3 × 5
phi_n = phi_bruteforce(n)
print(f"phi({n}) ব্রুট-ফোর্স গণনা =", phi_n)
print(f"সূত্র (3-1)(5-1) =", (3 - 1) * (5 - 1))
print("মিলে গেছে?", phi_n == (3 - 1) * (5 - 1))
# Euler's Theorem যাচাই: a^phi(n) mod n == 1 (a=2, n=15, gcd(2,15)=1)
print("2^phi(15) mod 15 =", pow(2, phi_n, 15))ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিজে কিছুক্ষণ ভাবুন — তারপর "→ উত্তর" চাপুন।
প্র ০১ Fermat's Little Theorem-এ $\gcd(a,p)=1$ শর্তটি বাদ দিলে কী সমস্যা হয় — একটি ব্যর্থ উদাহরণ দিন।
ধরুন $a=7, p=7$ (এখানে $\gcd(7,7)=7 \ne 1$, শর্ত ভঙ্গ হচ্ছে)। থিওরেম দাবি করে $7^6 \equiv 1 \pmod 7$। কিন্তু $7 \equiv 0 \pmod 7$, তাই $7^6 \equiv 0^6 = 0 \pmod 7$, যা $1$ নয়! এই ব্যর্থতাই দেখায় কেন শর্তটি অপরিহার্য — যদি $p \mid a$ হয়, তাহলে $a$-এর যেকোনো ঘাতও $p$ দ্বারা বিভাজ্য থাকবে, কখনো $1$-এর সাথে সমতুল্য হবে না।
প্র ০২ $\varphi(n)=(p-1)(q-1)$ সূত্রটি কি যেকোনো দুটি সংখ্যা $p,q$-এর জন্য কাজ করে, নাকি শুধু প্রাইমের জন্য?
শুধু যখন $p,q$ ভিন্ন প্রাইম। যদি $p,q$ প্রাইম না হয়, অথবা $p=q$ হয়, সূত্রটি ভুল ফলাফল দেবে। উদাহরণ: $n=4=2\times2$ (একই প্রাইম দুইবার) — সূত্র প্রয়োগ করলে ভুলভাবে $(2-1)(2-1)=1$ পাওয়া যেত, কিন্তু আসল $\varphi(4)=2$ (কারণ $1,3$ — এই দুটি সংখ্যা $4$-এর সাথে coprime)। RSA-তে তাই সবসময় দুটি ভিন্ন বড় প্রাইম বেছে নেওয়া হয়, এবং কখনো একই প্রাইম দুইবার ব্যবহার করা হয় না।
প্র ০৩ Fermat's Little Theorem-কে "Euler's Theorem-এর একটি বিশেষ কেস" বলা হয় কেন — সম্পর্কটি ঠিক কীভাবে কাজ করে?
Euler's Theorem বলে $a^{\varphi(n)} \equiv 1 \pmod n$ যেকোনো $n$-এর জন্য (যতক্ষণ $\gcd(a,n)=1$)। যখন $n$ নিজে একটি প্রাইম $p$ হয়, তখন $\varphi(p)=p-1$ (কারণ $1$ থেকে $p-1$ পর্যন্ত সব সংখ্যাই $p$-এর সাথে coprime)। এই মান বসিয়ে দিলে Euler's Theorem হয়ে যায় $a^{p-1} \equiv 1 \pmod p$ — যা হুবহু Fermat's Little Theorem। তাই Fermat-এর থিওরেম আসলে Euler-এর সাধারণ থিওরেমেরই একটি সংকীর্ণ (প্রাইম-মডুলাস) রূপ।
অনুশীলন
-
হাতে হিসাব করুন: Fermat's Little Theorem যাচাই করুন $a=3, p=5$-এর জন্য — $3^4$ হাতে গণনা করুন এবং দেখুন $\bmod 5$ নিলে সত্যিই $1$ পাওয়া যায় কিনা।
$3^4 = 81$। $81 = 16\times5+1$, তাই $81 \bmod 5 = 1$। যাচাই সম্পন্ন: $3^{5-1} \equiv 1 \pmod 5$ ✓।
-
ব্রুট ফোর্স গণনা করুন: $\varphi(9)$ হাতে-কলমে বের করুন ($1$ থেকে $9$-এর মধ্যে $9$-এর সাথে coprime সংখ্যাগুলো গুনে), তারপর উপরের কোড সেলের
phi_bruteforce(9)চালিয়ে মিলিয়ে দেখুন। খেয়াল করুন $9=3^2$ — একই প্রাইমের বর্গ, তাই $(p-1)(q-1)$ সূত্র এখানে সরাসরি খাটে না।$1$ থেকে $9$: $\{1,2,4,5,7,8\}$ — $3,6,9$ বাদে, কারণ এরা $3$-এর গুণিতক। মোট $6$টি, তাই $\varphi(9)=6$। এটি $p^k$ আকারের সংখ্যার জন্য ভিন্ন সূত্র $\varphi(p^k)=p^k - p^{k-1}$ দিয়ে মেলে: $\varphi(3^2)=9-3=6$ ✓।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- কোর্সের সম্পূর্ণ সিলেবাস দেখুন ৪৪টি পাঠ M5-এর শেষ পাঠ — RSA এনক্রিপশন — এখনই দেখুন।
- পাঠ ২৮ · RSA এনক্রিপশন পরবর্তী পাঠ এই পাঠের থিওরেম ব্যবহার করে সম্পূর্ণ ওয়ার্কড RSA উদাহরণ।
- পাঠ ২৬ · মডুলার এরিথমেটিক আগের পাঠ Congruence, দ্রুত এক্সপোনেনশিয়েশন ও মডুলার ইনভার্স — এই পাঠের ভিত্তি।