Fermat–Euler Theorem

এই নোটে আমরা সংখ্যাতত্ত্বের দুটি অত্যন্ত পরিচিত,জনপ্রিয় ও গুরুত্বপূর্ণ উপপাদ্য নিয়ে বিস্তারিত আলোচনা করব এবং শেষে কয়েকটি সমস্যা সমাধান করব। ফার্মা (Pierre De Fermat) এবং অয়লার (Leonhard Euler) দুজনেই অত্যন্ত বড় (আকারে নন,প্রতিভায় :p) গণিতবিদ ছিলেন। তো তাঁদের প্রচুর উপপাদ্য রয়েছে। কিন্তু এখানে আমরা দুটি বিশেষ উপপাদ্য নিয়ে আলোচনা করব।প্রথমটির একটি মিষ্টি নাম আছে : ফার্মার ছোট্ট উপপাদ্য (ইংরেজিতে বলে Fermat’s Little Theorem) এবং দ্বিতীয়টি অয়লারের উপপাদ্য (Euler’s Theorem)। দ্বিতীয়টি আসলে প্রথমটিরই বর্ধিত রূপ। সেটি আমরা একটু পরেই দেখব। এবার শুরু করা যাক।

এই নোটের সবকিছু বোঝার জন্য কিছু জিনিস জানতে হবে। সেগুলো হল:

(১)একটি সেট $S$ কে $\text {Reduced complete set of residue classes modulo m}$ বলা হবে যদি প্রত্যেকটি $i$ ($0 \leq i \leq m-1$ এবং $i$ আর $m$ এর গ.সা.গু $1$) এর জন্য $S$ এ কেবল একটি মাত্র উপাদান $s$ থাকে যেন $i \equiv s$ $\text {mod m}$.

(২)$\phi (n)$ (‘$\phi$’ এই চিহ্নটির নাম ‘ফাই’) হচ্ছে $n$ এর চেয়ে ছোট এবং $n$ এর সাথে সহমৌলিক সংখ্যার সংখ্যা। অর্থাৎ $\phi (n)$={$x:0 \leq x \leq n-1,(x,n)=1$}.($(a,b)=d$ দ্বারা বোঝায় $a$ এবং $b$ এর গ.সা.গু $d$).

(৩)$1$ থেকে $n$ পর্যন্ত সংখ্যাগুলোর গুণফলকে সংক্ষেপে $n!$ দ্বারা প্রকাশ করা হয়।

এবার কিছু প্রশ্নের উত্তর দাও।বল তো,$\phi (p)=?$

একটু চিন্তা কর।

$\phi (p)=p-1$। কারণ $1$ থেকে $p-1$ পর্যন্ত সকল সংখ্যাই $p$ এর সাথে সহমৌলিক।

এবার বল $\text {Reduced complete set of residue classes modulo n}$ এর উপাদান সংখ্যা কত?

চিন্তা কর।

$\phi (n)$

তো এবার মূল আলোচনায় আসা যাক। প্রথমেই 'বড়' ফার্মার 'ছোট্ট' উপপাদ্য দিয়ে শুরু করি। মডুলার অ্যারিথমেটিকে হিসেব নিকেশের সময় সূচক (Exponent) নিয়ে কাজ করতে গেলে ফার্মার থিওরেম খুবই কাজের জিনিস। এর মূল কথা হচ্ছে : $a^{p}$ কে $p$ দ্বারা ভাগ করলে কত অবশিষ্ট থাকে? যদি $a$,$p$ দ্বারা নিঃশেষে বিভাজ্য হয়, তাহলে $a^{p}$ ও নিঃশেষে বিভাজ্য হবে। অর্থাৎ $a^{p}$ কে $p$ দ্বারা ভাগ করলে $0$ অবশিষ্ট থাকে। কিন্তু যদি $a$,$p$ দ্বারা নিঃশেষে বিভাজ্য না হয়, তাহলে $a^{p}$ কে $p$ দ্বারা ভাগ করলে কত অবশিষ্ট থাকবে? ফার্মার উপপাদ্য আসলে এটা নিয়েই। ফার্মার ছোট্ট উপপাদ্যটি হচ্ছে :$a^{p} \equiv a$ $\text {(mod p)}$.

প্রমাণ: এর প্রমাণের কৌশলটা খুবই চমৎকার এবং অনেক সমস্যা সমাধানে এই কৌশলটা অনেক কাজে আসে।

প্রথমে আমরা একটা সংখ্যা $a$ এবং $p$ নেব যেন $a$,$p$ দিয়ে বিভাজ্য না হয়। এখন $p$ এর একটি $\text {Reduced complete set of residue class}$ ($p$ এর সাথে সহমৌলিক সংখ্যাগুলোর সেট) $R$ নেই যেন $R={1, 2, …, p-1}$.আমরা দেখাবো $S={a, 2a, …, (p-1)a}$ ও $p$ এর একটি $\text {Reduced complete set of residue class}$.

$S$ সেটে উপাদান আছে মোট $p-1$ টি। আবার,$p$ দ্বারা বিভাজ্য নয় এমন কোনো সংখ্যাকে $p$ দ্বারা ভাগ করলেও মোট $p-1$ টি ভাগশেষ ($1$ থেকে $p-1$) থাকতে পারে। তাহলে আমরা যদি দেখাতে পারি $S$ এর প্রতিটি উপাদানকে $p$ দ্বারা ভাগ দিলে ভিন্ন ভিন্ন ভাগশেষ থাকে, তাহলে $S$ অবশ্যই $p$ এর একটি $\text {Reduced complete set of residue class}$ হবে। এটা দেখানো আসলে কঠিন কিছু না। আমরা বৈপরীত্যের মাধ্যমে এটা প্রমাণ করব (Proof by contradiction)

ধরে নেই $S$ এর দুইটি উপাদান $ax$ এবং $ay$ আছে যেন $p$ দ্বারা তাদেরকে ভাগ দিলে ভাগশেষ একই থাকে অর্থাৎ $ax \equiv ay$ $\text{(mod p)}$ $\Rightarrow$ $ax-ay \equiv 0$ $\text{(mod p)}$ $\Rightarrow$ $a(x-y) \equiv 0$ $\text{(mod p)}$.এখন যেহেতু $a$ এবং $p$ এর গ.সা.গু $1$,সুতরাং,$x \equiv y$ $\text {(mod p)}$ ।

কিন্তু যেহেতু $x,y$ $\in$ {$1, 2, …, p-1$}, সুতরাং তারা $p$ এর চেয়ে ছোট। তাই $\text {mod p}$ তে এরা সমান হলে এদের নিজেদের পরস্পর সমান হতে হবে। কিন্তু এটি সম্ভব নয়। কারণ আমরা এদের ভিন্ন ধরে নিয়েছি। তাহলে দাঁড়াচ্ছে যে,$S$ এর কোন দুইটি ভিন্ন উপাদানই $\text {mod p}$ তে সমান না। এখন, যেহেতু $\text {mod p}$ তে $R=S$, তাহলে এদের উপাদানগুলোর গুণফলও $\text {mod p}$ তে সমান হবে। অর্থাৎ,

$$(a\cdot 1)\times (a\cdot 2)... \times (a\cdot (p-1)) \equiv 1 \times 2 \times ... \times (p-1) \pmod p$$ $$\underbrace{a \times a \times a \times a ... a}_{\text{p-1 times}} \times 1 \times 2 \times 3... \times (p-1) \equiv 1 \times 2 \times ... \times (p-1) \pmod p$$ $$a^{p-1} (p-1)! \equiv (p-1)! \pmod p$$

($1$ থেকে $n$ পর্যন্ত সংখ্যাগুলোর গুণফলকে সংক্ষেপে $n!$ দ্বারা প্রকাশ করা হয়।).

এখন যেহেতু $(p,(p-1)!)=1$, সুতরাং, উভয়পক্ষকে $(p-1)!$ দ্বারা ভাগ করে পাই, $a^{p-1} \equiv 1$ $\text {mod p}$ । এবার উভয়পক্ষকে $a$ দ্বারা গুণ করে পাই, $$a^{p} \equiv a \pmod p$$

এই হচ্ছে ফার্মার থিওরেমের প্রমাণ। দেখ,প্রমাণে আমরা পেয়েছি যে, $a^{p-1} \equiv 1$ $\text {mod p}$। এটিই সবচেয়ে বেশি ব্যবহৃত হয়।

যদিও ফার্মার এই উপপাদ্যটি অনেক কাজে দেয়, কিন্তু তবুও এর একটা বড় রকমের সীমাবদ্ধতা রয়ে গেছে। সেটা হচ্ছে এটা প্রয়োগ করতে হলে আমরা যে সংখ্যা দিয়ে ভাগ করব সেটা অবশ্যই কোনো মৌলিক সংখ্যা হতে হবে। মৌলিক সংখ্যা না হলে যে এটা কাজ করবেনা তার উদাহরণ পাওয়া খুবই সহজ। যেমন $3^{3} \not\equiv 1$ $\text {(mod 4)}$. কিন্তু আমাদের তো শুধু মৌলিক সংখ্যার ভিত্তি নিয়ে কাজ করলেই হবেনা। অয়লারের থিওরেম ঠিক এই সমস্যাটাকেই দূর করে। এখন কথা হচ্ছে ফার্মার উপপাদ্যটির প্রমাণে $\text {mod p}$ (অর্থাৎ mod prime) কাজে আসল কোথায়?

একটু চিন্তা কর।

$R$ সেটটা নেয়ার সময় $\text {mod p}$ নেয়া দরকার হয়। কারণ যৌগিক যেকোনো সংখ্যা $n$ এর জন্য ${1, 2, …, n-1}$ সেটের কোনো না কোনো উপাদান $n$ কে নিঃশেষে ভাগ করবে, ফলে সেটটা আর $n$ এর $\text {Reduced complete set of residue class}$ হবেনা। তাহলে আমরা $R$ কে কীভাবে নিতে পারি?

আমরা $R$ সেটটিতে শুধু $n$ এর সাথে সহমৌলিক সংখ্যাগুলো রাখতে পারি। ধরি,$R={r_{1},r_{2},…, r_{\phi (n)}}$,যেখানে $\phi (n)$ হচ্ছে $1$ থেকে $n$ এর মধ্যে $n$ এর সাথে সহমৌলিক সংখ্যার সংখ্যা এবং $r_{i}$ হচ্ছে $i$ তম সহমৌলিক সংখ্যা। এবার ধরি,$S={ar_{1},ar_{2}, … , ar_{\phi (n)}}$ যেখানে $(a,n)=1$ । এবার ফার্মার উপপাদ্যের ন্যায় একইভাবে প্রমাণ করতে পারি যে, $S$,$n$ এর একটি $\text {Reduced complete set of residue class}$ ।

একইরকম। আগে নিজে চেষ্টা কর। তারপরে নিচে দেখ

ধরে নেই $S$ এর দুইটি উপাদান $ax$ এবং $ay$ আছে যেন $n$ দ্বারা তাদেরকে ভাগ দিলে ভাগশেষ একই থাকে অর্থাৎ $ax \equiv ay$ $\text{(mod n)}$ $\Rightarrow$ $ax-ay \equiv 0$ $\text{(mod n)}$ $\Rightarrow$ $a(x-y) \equiv 0$ $\text{(mod n)}$.এখন যেহেতু $a$ এবং $n$ এর গ.সা.গু $1$, সুতরাং, $x \equiv y$ $\text {(mod p)}$.কিন্তু যেহেতু $x,y \in {1, 2, …, n-1}$, সুতরাং তারা $p$ এর চেয়ে ছোট। তাই $\text {mod n}$ এ এরা সমান হলে এদের নিজেদের পরস্পর সমান হতে হবে। কিন্তু এটি সম্ভব নয়। কারণ আমরা এদের ভিন্ন ধরে নিয়েছি। তাহলে দাঁড়াচ্ছে যে,$S$ এর কোন দুইটি ভিন্ন উপাদানই $\text {mod n}$ এ সমান না।

এখন, যেহেতু $\text {mod n}$ এ $R=S$, তাহলে এদের উপাদানগুলোর গুনফলও $\text {mod n}$ এ সমান হবে। অর্থাৎ,

$$ar_{1}ar_{2} ... ar_{\phi (n)} \equiv r_{1}r_{2} ... r_{\phi (n)} \pmod n$$

এখন সকল $r_{k}$ (যেখানে $k=1,2…..,\phi (n)$) এবং $n$ এর গ.সা.গু $1$.সুতরাং, $(r_{1}r_{2} ... r_{\phi (n)},n)=1$ । এখন,উভয়পক্ষকে $r_{1}r_{2} ... r_{\phi (n)}$ দ্বারা ভাগ করে পাই,

$$a^{\phi (n)} \equiv 1\pmod n$$

এটিই অয়লারের উপপাদ্য।

দেখ,আমরা অয়লারের উপপাদ্য থেকেও ফার্মার উপপাদ্যটি প্রমাণ করতে পারি। অয়লারের উপপাদ্য থেকে আমরা জানি, $a^{\phi (n)} \equiv 1$ $\text {mod n}$ । এখন,$n$ এর জায়গায় $p$ (একটি মৌলিক সংখ্যা) বসিয়ে পাই, $a^{\phi (p)} \equiv 1$ $\text {mod p}$। আমরা পূর্বেই দেখেছি যে, $\phi (p)=p-1$। সুতরাং, $a^{p-1} \equiv 1$ $\text {(mod p)}$.

তাহলে এতক্ষণ যা শিখলাম তার সারাংশ হচ্ছে :

(১)যদি $a$ একটি ধনাত্মক পূর্ণসংখ্যা হয় এবং $p$ একটি মৌলিক সংখ্যা হয়,তাহলে $a^{p} \equiv a$ $\text {(mod p)}$.এটিই ফার্মার ছোট্ট উপপাদ্য।

(২)যদি $a$ এবং $n$ ধনাত্মক পূর্ণসংখ্যা হয় এবং তারা সহমৌলিক হয়,তাহলে $a^{\phi (n)} \equiv 1$ $\text {mod n}$.এটিই অয়লারের উপপাদ্য।

এবার কিছু সমস্যা সমাধান করা যাক।অবশ্যই প্রথমে সমস্যাগুলো নিজে অনেকক্ষণ চেষ্টা করবে।তারপরে সমাধান দেখবে

সমস্যা ১: $5^{10}$ কে $16$ দ্বারা ভাগ করলে কত ভাগশেষ থাকে?

** সমস্যা ২:** $6^{100}$ কে $101$ দ্বারা ভাগ করলে কত ভাগশেষ থাকে?($101$ একটি মৌলিক সংখ্যা)

সমস্যা ৩: ধর, $p$ একটি মৌলিক সংখ্যা। প্রমাণ কর যে, সকল পূর্ণসংখ্যা $a,b$ এর জন্য $p$, $ab^{p}-ba^{p}$ কে নিঃশেষে ভাগ করে।

সমাধান:

(১) সমাধান: অয়লারের উপপাদ্য ব্যবহার কর।

যেহেতু $(5,16)=1$, সুতরাং, অয়লারের উপপাদ্য ব্যবহার করে আমরা বলতে পারি, $5^{\phi (16)} \equiv 1$ $\text {(mod 16)}$ $\Rightarrow$ $5^{8} \equiv 1$ $\text {(mod 16)}$ ($1$ থেকে $16$ পর্যন্ত সকল বিজোড় সংখ্যাই শুধুমাত্র $16$ এর সাথে সহমৌলিক। তাই $\phi (16)=8$) এখন উভয়পক্ষে $5^{2}$ দ্বারা গুণ করে পাই, $5^{10} \equiv 5^{2} \equiv 25 \equiv 9$ $\text {(mod 16)}$

(২)সমাধান: ফার্মার উপপাদ্য ব্যবহার কর।

ফার্মার উপপাদ্য সরাসরি ব্যবহার করে আমরা পাই, $6^{100} \equiv 1$ $\text {(mod 101)}$.(ফার্মার উপপাদ্যে $a$ এর জায়গায় $6$ এবং $p$ এর জায়গায় $101$ বসাও)

(৩)সমাধান: ফার্মার উপপাদ্য ব্যবহার কর।

$ab^{p}-ba^{p}=ab(b^{p-1}-a^{p-1})$ । এখন $a$ অথবা $b$ যদি $p$ দ্বারা নিঃশেষে বিভাজ্য হয়, তাহলে $ab^{p}-ba^{p}$ সংখ্যাটিও $p$ দ্বারা নিঃশেষে বিভাজ্য হবে। তাই ধরি, $(a,p)=(b,p)=1$.তাহলে ফার্মার উপপাদ্য ব্যবহার করে পাই, $b^{p-1} \equiv a^{p-1} \equiv 1$ $\text {(mod p)}$ $\Rightarrow$ $b^{p-1}-a^{p-1} \equiv 1-1 \equiv 0$ $\text {(mod p)}$. এক্ষেত্রেও $ab^{p}-ba^{p}$ সংখ্যাটি $p$ দ্বারা নিঃশেষে বিভাজ্য। অর্থাৎ সকল পূর্ণসংখ্যা $a,b$ এর জন্য $p$, $ab^{p}-ba^{p}$ কে নিঃশেষে ভাগ করে।

Fermat's Little Theorem (FLT) is an incredibly useful theorem in its own right. However, it only applies to prime bases, and "most" integers are certainly not prime. How can we generalize FLT to any integer base?

It is clear that simply stating $a^{n-1} \equiv 1 \pmod{n}$ if $(a,n)=1$ will not work here. As a simple counterexample, take $a=-1$ and $n=12$. Looking at why this doesn't work will give us a clue regarding how we should generalize FLT.

Recall the proof of FLT. If you trace through it, you will find that it works in almost exactly the same way ... until the very end: $$a^{p-1}(p-1)!\equiv (p-1)! \pmod{p}$$ In the very last step, we divide both sides of the congruence by $(p-1)!$ to obtain our final result: $$a^{p-1}\equiv 1 \pmod{p}$$ But if $n$ is not prime, then this no longer works! Think about why not before moving on.

For $n$ not prime, $(n-1)!\equiv 0 \pmod{n}$, meaning that $(n-1)!$ is definitely not relatively prime to $n$. Remember that, in general, you cannot divide in congruences unless the factor being removed on both sides is relatively prime to the base. For example, $$4\times 3\equiv 4\times 5\pmod{8}\rightarrow 3\equiv 5\pmod{8}$$ is not valid, because $4$ and $8$ are not relatively prime, but $$4\times 3\equiv 4\times 10\pmod{7}\rightarrow 3\equiv 10\pmod{7}$$ is valid, because $4$ and $7$ are relatively prime.

This gives us the clue we need. Instead of taking the set ${a, 2a, 3a, ..., (p-1)a}$, we need to take a set with all numbers relatively prime to $n$. How many positive integers less than or equal to $n$ are relatively prime to $n$? It's our familiar friend: Euler's totient function, $\phi(n)$! We are now ready to state Euler's Theorem:

If $(a,n)=1$, then: $$a^{\phi(n)}\equiv 1\pmod{n}$$

Our proof of Euler's Theorem will mimic that of FLT very closely. Let $x_1, x_2, ..., x_{\phi(n)}$ be all of the integers between $1$ and $n$, inclusive, that are relatively prime to $n$. Now, consider the set ${x_1a, x_2a, x_3a, ..., x_{\phi(n)}a}$. We will prove that this set is an abbreviated residue class modulo $n$, meaning that it contains every remainder relatively prime to $n$ exactly once.

It is clear that all of the elements in the set are relatively prime to $n$. Assume, for the sake of contradiction, that $ax_i\equiv ax_j \pmod{n}$ for $0\lt j\lt i\lt \phi(n)$. Then, $a(i-j)\equiv 0 \pmod{n}$, which is a contradiction, since $i-j$ is not a multiple of $n$. Therefore, all of the elements ${x_1a, x_2a, x_3a, ..., x_{\phi(n)}a}$ are distinct modulo $n$. Thus, since these $\phi(n)$ elements can only occupy $\phi(n)$ residue classes, each residue class must be occupied exactly once.

Since ${x_1a, x_2a, x_3a, ..., x_{\phi(n)}a}$ is an abbreviated residue class, it follows that: $$x_1a \times x_2a \times x_3a \times ... \times x_{\phi(n)}a \equiv x_1\times x_2\times x_3\times ... \times x_{\phi(n)} \pmod{p}$$ $$a^{\phi(n)}\prod_{i=1}^{\phi(n)}x_i\equiv \prod_{i=1}^{\phi(n)}x_i \pmod{p}$$ Since $\prod_{i=1}^{\phi(n)}x_i$ is relatively prime to $p$, we may divide by $\prod_{i=1}^{\phi(n)}x_i$ in the above congruence to obtain: $$a^{\phi(n)}\equiv 1 \pmod{n}$$ Thus, we have proved Euler's Theorem.