উইলসনের উপপাদ্য

সংখ্যা তত্ত্ব ও বীজগণিতে **উইলসনের উপপাদ্য** একটি গুরুত্বপূর্ণ উপপাদ্য। উইলসনের উপপাদ্য অনুযায়ী, সকল স্বাভাবিক সংখ্যা n > 1 এর জন্য (n - 1)! + 1 \equiv 0 \pmod{n} হবে কেবল এবং কেবল যদি n একটি মৌলিক সংখ্যা হয়। অর্থাৎ, যদি p একটি মৌলিক সংখ্যা হয়, কেবল তখনই (p-1)!+1 এর মান p দ্বারা নিঃশেষে বিভাজ্য হবে ।

## ইতিহাস

আনু. খ্রিস্টীয় ১০০০ সালের দিকে উইলসনের উপপাদ্য সর্বপ্রথম আলোকপাত করেছিলেন মুসলিম বিজ্ঞানী হাসান ইবনুল হায়সাম। ১৭৭০ সালে এডওয়ার্ড ওয়ারিং এই উপপাদ্যটি বিবৃত করেন কিন্তু কোনো প্রমাণ দেননি। তিনি এই আবিষ্কারের কৃতিত্ব তার ছাত্র জন উইলসনকে দেন। ১৭৭১ সালে প্রথমবার জোসেফ লুই ল্যাগ্রাঞ্জ এই উপপাদ্যের প্রমাণ দেন। এর প্রায় এক শতাব্দী আগে লিবনিজও এই ফলাফল সম্পর্কে জানতেন বলে প্রমাণ রয়েছে, কিন্তু তিনি এটি কখনো প্রকাশ করেননি।

## উদাহরণ
প্রতিটি n-এর জন্য (2 থেকে 30 পর্যন্ত), নিম্নলিখিত সারণী (n - 1)! এর মান এবং (n - 1)!-কে n দ্বারা ভাগ করার পর ভাগশেষ প্রদর্শন করে। (মডুলার পাটিগণিতের নোটেশনে, m-কে n দ্বারা ভাগ করার পর ভাগশেষ *<math>m\pmod{n}</math>* দ্বারা লেখা হয়।)

সারণীর ব্যাকগ্রাউন্ডের রঙ এখানে নীল, মৌলিক মানের জন্য এবং সোনালী, যৌগিক মানের জন্য।

## প্রমাণ
### বিপরীত অনুমানের মাধ্যমে প্রমাণ

ধরি, n একটি যৌগিক সংখ্যা।

যেহেতু যৌগিক সংখ্যার দুইয়ের বেশি উৎপাদক থাকে, n = n_1 \cdot n_2 আকারে, যেখানে 1 .

এখন, (n - 1)! = (n - 1)(n - 2)(n - 3)\cdots3 \cdot 2 \cdot 1

আবার, n_1 n_2 

সুতরাং, 1 

এখন, n_1 এবং n_2 হল (n - 1)! এর যেকোনো দুটি উৎপাদক যা n_1n_2 দ্বারা বিভাজ্য।

তাই, (n - 1)! \equiv 0 \pmod{n_1n_2}
যেহেতু n = n_1 n_2, (n - 1)! \equiv 0 \pmod{n}.....(i)

দেওয়া আছে যে (n - 1)! \equiv -1 \pmod{n}.....(ii)

এর অর্থ 0 \equiv -1 \pmod{n}

এটি বোঝায় যে 0 + 1 \equiv 0 \pmod{n}

তাই, 1 \equiv 0 \pmod{n} যার অর্থ 1 কে n দিয়ে ভাগ করলে ভাগশেষ 0 হবে।

এটি বোঝায় যে n|1, যা বিরোধিতা সৃষ্টি করে কারণ n একটি যৌগিক সংখ্যা (আমাদের অনুমান অনুযায়ী), এবং 1 কোনো যৌগিক সংখ্যা দ্বারা বিভাজ্য হতে পারে না।

আবার, n_1 n_2 > 1 হওয়াটাও একটি কারণ যে n = n_1 n_2, 1 কে ভাগ করতে পারে না।

সুতরাং, আমাদের অনুমান ভুল। n অবশ্যই একটি মৌলিক সংখ্যা হবে।

### বীজগাণিতিক প্রমাণ

ধরি, n একটি মৌলিক সংখ্যা।

মডুলো n-এ পূর্ণসংখ্যার ক্ষেত্রটি বিবেচনা করে, ফার্মার লিটল থিওরেম থেকে আমরা জানি:

উক্ত ক্ষেত্রের প্রতিটি অশূন্য উপাদান f(x) = x^{n-1} - 1 বহুপদীর একটি মূল।

যেহেতু ক্ষেত্রটিতে মাত্র (n - 1) টি অশূন্য উপাদান আছে, তাই হয় n = 2 অথবা n - 1 জোড় সংখ্যা।

n = 2 হলে, যেকোনো পূর্ণসংখ্যা a এর জন্য, a \equiv -a \pmod{2}
n - 1 এর জন্য, (-1)^{n-1} \equiv 1 \pmod{n}

সুতরাং, x^{n-1}-1=\prod ^{n-1}_{r=1}\left( x-r\right) =\prod ^{n-1}_{r=1}\left(-x+r\right)

x=0 বসালে, আমরা পাই (n - 1)! \equiv -1 \pmod{n}

### এলিমেন্টারি বা প্রাথমিক প্রমাণ

ধরি, n একটি মৌলিক সংখ্যা।

ক্ষুদ্রতম মৌলিক সংখ্যার জন্য, n = 2: 1! \equiv -1 \pmod{2}। (সত্য)

যদি n > 2 হয়, তবে যেকোনো a \in [1, n - 1] এর জন্য, এমন একটি b \in [1, n - 1] আছে, যেখানে ab \equiv 1 \pmod{n}

সেট \{1, \ldots, n - 1\} এর প্রতিটি পূর্ণসংখ্যা a এর মডুলো n-এ একটি গৌণিক বিপরীত সংখ্যা আছে।

এই গৌণিক বিপরীত সংখ্যাটি অনন্য এবং এটিকে a^{-1}\pmod{n} দ্বারা প্রকাশ করা হয়।

যদি a \equiv a^{-1}\pmod{n} হয়, তবে a^2 - 1 \equiv 0 \pmod{n}

তারপর (a - 1)(a + 1) \equiv 0 \pmod{n}, যার মডুলো n-এ দুটি মূল আছে: a \equiv 1 \pmod{n} এবং a \equiv -1 \pmod{n}

এটি বোঝায় যে a = 1 অথবা a = n - 1

আমরা 1 থেকে n - 1 পর্যন্ত সকল পূর্ণসংখ্যাকে, 1 এবং n - 1 বাদে, \{a, b\} জোড়ায় সাজাতে পারি, যেখানে ab \equiv 1 \pmod{n}, শুধুমাত্র 1 এবং n - 1 বাদে যাদের গুণফল -1 \pmod{n}।

সুতরাং, (n - 1)! \equiv 1 \cdot (n - 1) \equiv -1 \pmod{n}।

উদাহরণস্বরূপ, p = 11 হলে:

10! = [(1\cdot10)]\cdot[(2\cdot6)(3\cdot4)(5\cdot9)(7\cdot8)]  \equiv [-1]\cdot[1\cdot1\cdot1\cdot1]  \equiv -1 \pmod{11}.

### ফার্মার লিটল থিওরেম দ্বারা প্রমাণ

আবার, ফলাফলটি p = 2 এর জন্য প্রমাণিত, তাই ধরে নেই p একটি বিজোড় মৌলিক সংখ্যা, p \geq 3।

g(x) = (x-1)(x-2)\cdots (x-(p-1)) বহুপদীটি বিবেচনা করি ।

এখানে g-এর ডিগ্রী p - 1, প্রধান পদ x^{p-1}, এবং ধ্রুবক পদ (p-1)!। এর (p - 1)টি মূল হল 1, 2, \ldots, p - 1 ।

এখন বিবেচনা করি:

h(x)=x^{p-1}-1

h-এরও ডিগ্রী p - 1 এবং প্রধান পদ x^{p-1} মডুলো p। ফার্মার লিটল থিওরেম বলে যে, এটিতেও একই (p - 1)টি মূল আছে: 1, 2, \ldots, p - 1।

অবশেষে, বিবেচনা করি:

f(x) = g(x) - h(x)
f-এর ডিগ্রী সর্বাধিক p - 2 (যেহেতু প্রধান পদগুলি বাতিল হয়ে যায়), এবং মডুলো p-এরও একই (p - 1)টি মূল আছে: 1, 2, \ldots, p - 1।

কিন্তু লাগ্রাঞ্জের উপপাদ্য বলে যে এটির সর্বাধিক (p - 2)টি মূল থাকতে পারে। অতএব, f অবশ্যই মডুলো p আইডেন্টিক্যালি শূন্য হতে হবে, তাই এর ধ্রুবক পদ হল (p - 1)! + 1 \equiv 0 \pmod{p}। এটি উইলসনের উপপাদ্য।

### সাইলোর উপপাদ্যের মাধ্যমে প্রমাণ
উইলসনের উপপাদ্যকে সাইলোর উপপাদ্যের একটি নির্দিষ্ট প্রয়োগ থেকে নির্ণয় করা সম্ভব।

ধরা যাক, p একটি মৌলিক সংখ্যা।

সহজেই দেখা যায় যে, p-এর জন্য S_p (সমমিতিক গ্রুপ) এ p-ক্রম বিশিষ্ট (p - 1)! সংখ্যক উপাদান রয়েছে, যেগুলো p-চক্রগুলোর সমষ্টি, অর্থাৎ C_p।

অন্যদিকে, S_p-এ প্রতিটি সাইলো p-উপগ্রুপ আসলে C_p-এর একটি অনুলিপি । ফলে, সাইলো p-উপগ্রুপের সংখ্যা n_p = (p - 2)!

তৃতীয় সাইলো উপপাদ্য থেকে পাই:

(p - 2)! \equiv 1 \pmod{p}

এখন উভয় পাশকে (p - 1) দ্বারা গুণ করলে পাওয়া যায়:

(p - 1)! \equiv (p - 1) \equiv -1 \pmod{p}

## প্রয়োগ
### মৌলিকত্ব পরীক্ষণ

উইলসনের উপপাদ্যের একটি গুরুত্বপূর্ণ বৈশিষ্ট্য হল এটি একটি দ্বি-মুখী শর্ত প্রদান করে - অর্থাৎ একটি সংখ্যা মৌলিক হলেই কেবল এই শর্ত পূরণ করবে এবং শর্তটি পূরণ করলে সংখ্যাটি অবশ্যই মৌলিক হবে। এই বৈশিষ্ট্যটি অন্যান্য মৌলিকত্ব পরীক্ষার পদ্ধতিগুলোতে সেভাবে পাওয়া যায় না। উদাহরণস্বরূপ, ফার্মার বা লুকাস-লেহমার পরীক্ষাগুলি শুধুমাত্র নির্দিষ্ট ধরনের সংখ্যার জন্য প্রযোজ্য।

তবে উইলসনের উপপাদ্যের কিছু গুরুতর সীমাবদ্ধতাও রয়েছে। প্রথমত, বড় সংখ্যার ক্ষেত্রে (p-1)! গণনা করা অত্যন্ত কঠিন এবং সময়সাপেক্ষ। দ্বিতীয়ত, কম্পিউটারে বড় ফ্যাক্টোরিয়াল মান সংরক্ষণ করা কঠিন, কারণ এই মান দ্রুত বৃদ্ধি পায়। এছাড়া, মডুলার পাটীগণিত ব্যবহার করেও বড় সংখ্যার জন্য গণনা করা কঠিন হয়ে পড়ে।

বাস্তব প্রয়োগের ক্ষেত্রে, উইলসনের উপপাদ্য মূলত ছোট মৌলিক সংখ্যা পরীক্ষার জন্য ব্যবহার করা হয়। বড় সংখ্যার মৌলিকত্ব পরীক্ষার জন্য আধুনিক ক্রিপ্টোগ্রাফিতে মিলার-রাবিন বা সোলোভে-স্ট্রাসেন পরীক্ষার মতো সম্ভাব্যতামূলক পদ্ধতিগুলি ব্যবহার করা হয়। তবে তাত্ত্বিক দৃষ্টিকোণ থেকে, উইলসনের উপপাদ্য মৌলিকত্ব পরীক্ষার একটি নির্ভুল ও সুন্দর পদ্ধতি হিসেবে বিবেচিত হয়।

### কোয়াড্রাটিক রেসিডিউ

উইলসনের উপপাদ্য ব্যবহার করে, যেকোনো বিজোড় মৌলিক সংখ্যা p = 2m + 1 এর জন্য, আমরা 1\cdot 2\cdots (p-1)\ \equiv\ -1\ \pmod{p} সমীকরণের বাম পাশটি পুনর্বিন্যস্ত করতে পারি ।

এই সমীকরণটি পাওয়া যায়:

1\cdot (p-1)\cdot 2\cdot (p-2)\cdots m\cdot (p-m)\ \equiv\ 1\cdot (-1)\cdot 2\cdot (-2)\cdots m\cdot (-m)\ \equiv\ -1 \pmod{p}.

অতএব,
\prod_{j=1}^m\ j^2\ \equiv(-1)^{m+1} \pmod{p}
অথবা

(m!)^2 \equiv(-1)^{m+1} \pmod{p}

আমরা এই তথ্যটি ব্যবহার করে একটি বিখ্যাত ফলাফলের একটি অংশ প্রমাণ করতে পারি: যেকোনো মৌলিক সংখ্যা p এর জন্য, যেখানে p \equiv 1 \pmod{4}, অর্থাৎ কোনো পূর্ণসংখ্যা k এর জন্য p = 4k + 1। সুতরাং m = 2k নিলে হয়:
(m!)^2 \equiv -1 \pmod{p}।

### মৌলিক সংখ্যা নির্ণয়ের সূত্র

উইলসনের উপপাদ্য ব্যবহার করে মৌলিক সংখ্যা নির্ণয়ের সূত্র]] তৈরি করা হয়েছে, তবে সেগুলো ব্যবহারিক দৃষ্টিকোণ থেকে খুবই ধীর। যেমন:

১৯৬৪ সালে, সি.পি. উইলিয়ানস নিম্নলিখিত সূত্রটি প্রদান করেন:
p_n = 1 + \sum_{i=1}^{2^n} \left\lfloor \left(\frac{n}{\sum_{j=1}^i \left\lfloor\left(\cos \frac{(j-1)! + 1}{j} \pi\right)^2\right\rfloor }\right)^{1/n} \right\rfloor
যেখানে p_n হলো n-তম মৌলিক সংখ্যা।

### p-অ্যাডিক গামা ফাংশন
 
উইলসনের উপপাদ্য p-অ্যাডিক গামা ফাংশন সংজ্ঞায়িত করতে সহায়তা করে।

## গাউস সরলীকরণ
গাউস প্রমাণ করেছিলেন যে 
\prod_{k = 1 \atop \gcd(k,m)=1}^m \!\!k \ \equiv
\begin{cases}
-1      \pmod{m}  & \text{if } m=4,\;p^\alpha,\;2p^\alpha \\
\;\;\,1 \pmod{m}  & \text{otherwise}
\end{cases}

যেখানে *p* একটি বিজোড় মৌলিক সংখ্যা এবং \alpha একটি ধনাত্মক পূর্ণ সংখ্যা ।

## আরো দেখুন
* ফার্মার লিটল থিওরেম
* মডুলার পাটীগণিত
* ফার্মার শেষ উপপাদ্য
* ব্রোকার্ডের অনুমান

## টীকা

## তথ্যসূত্র

*[[Disquisitiones Arithmeticae]]* গাউসের সিসেরোনিয়ান ল্যাটিন থেকে ইংরেজি এবং জার্মান ভাষায় অনূদিত হয়েছে। জার্মান সংস্করণে সংখ্যা তত্ত্বের উপর তার সমস্ত কাজ অন্তর্ভুক্ত রয়েছে: কোয়াড্রাটিক রিসিপ্রোসিটির সমস্ত প্রমাণ, গাউসের যোগফলের চিহ্ন নির্ধারণ, বাইকোয়াড্রাটিক রিসিপ্রোসিটি ইনভেস্টিগেশন, এবং প্রকাশিত না হওয়া নোটগুলি।
* .
* .
* .
* 

## বহিঃসংযোগ

* 
* 
* Mizar system proof: http://mizar.org/version/current/html/nat_5.html#T22
*