Question: গণিতে ইউক্লিডীয় এলগরিদম ছাড়া আর কত রকমের এলগরিদম আছে ?

মৌলিক সংখ্যা

গণিতের পরিভাষায় মৌলিক সংখ্যা (অথবা মৌলিক) হল এমন প্রাকৃতিক সংখ্যা যার কেবলমাত্র দুটো পৃথক উৎপাদক আছে: ১ এবং ঐ সংখ্যাটি নিজে। ১ এর চেয়ে বড় সকল সংখ্যা যারা মৌলিক না তাদেরকে যৌগিক সংখ্যা বলে। পাটিগণিতের মৌলিক উপপাদ্য এর মাধ্যমে সংখ্যাতত্ত্বতে মৌলিকের ভূমিকা প্রকাশ করানো হয়। ১ এর উপরে যেকোনো মৌলিক সংখ্যাকে ১ বাদে তার আগ পর্যন্ত সকল মৌলিক সংখ্যার গুনফল হিসাবে প্রকাশ করা যায়। কোনো সংখ্যার মৌলিকতা নির্ণয়ের সহজ কিন্তু ধীর পদ্ধতি হচ্ছে পরীক্ষামূলক ভাগ। পরীক্ষাতে দেখতে হয় যে সংখ্যা n, ২ থেকে শুরু করে n এর বর্গমূল পর্যন্ত কোনো দুইটি সংখ্যার গুনফল কিনা। পরীক্ষামূলক ভাগের চেয়ে অনেক বেশি কার্যকরি পদ্ধতি হচ্ছে মিলার-রাবিন মৌলিকতা পরীক্ষা যা দ্রুত কিন্তু সামান্য সম্ভাবনা থাকে ভুলের এবং একেএস মৌলিকতা পরীক্ষা, যেটাতে সবসময়ে সঠিক উত্তর আসে বহুঘাত সময়ে কিন্তু অনেক ধীর। বিশেষ রুপের মৌলিক সংখ্যার জন্য দ্রুতগতির পদ্ধতি আছে, যেমন মার্সেন সংখ্যাদের জন্য। As of September2019, সর্ববৃহত মৌলিক সংখ্যাতে ২৩২৪৯২৫ টি সংখ্যা আছে। প্রথম ছাব্বিশটি মৌলিক সংখ্যা হল:
২, ৩, ৫, ৭, ১১, ১৩, ১৭, ১৯, ২৩, ২৯, ৩১, ৩৭, ৪১, ৪৩, ৪৭, ৫৩, ৫৯, ৬১, ৬৭, ৭১, ৭৩, ৭৯, ৮৩, ৮৯, ৯৭, ১০১।[1]
ইতিহাস
মৌলিক সংখ্যা অসীমসংখ্যক, যা কিনা ইউক্লিড খ্রিস্টপূর্ব ৩০০ সালের দিকে প্রমাণ করেন।[2] সংজ্ঞানুসারে ১ সংখ্যাটি মৌলিক নয়। পাটীগণিতের মৌলিক উপপাদ্য সংখ্যাতত্ত্বে মৌলিক সংখ্যার কেন্দ্রীয় ভূমিকা প্রতিষ্ঠা করে: যে কোন অশূণ্য প্রাকৃতিক সংখ্যা n কে মৌলিক সংখ্যা উৎপাদকে বিশ্লেষণ করা যায়, যা মৌলিক সংখ্যার গুণফল বা তাদের বিভিন্ন ঘাতের গুণফল হিসাবে (যার মধ্যে শূণ্য ঘাতও রয়েছে)। আরও উল্লেখ্য, এই মৌলিক উৎপাদকে বিশ্লেষণের কাজটি কেবল একভাবেই করা যেতে পারে।
মৌলিকত্ব
মৌলিক সংখ্যা হবার ধর্মকে মৌলিকত্ব বা মৌলিকতা বলা বলা হয়। কোন সংখ্যা n এর মৌলিকতা সাধারণ ভাগ করেই নির্ধারণ করা যায়, যেমন কোন সংখ্যা n কে এর চেয়ে ছোট সকল পূর্ণ সংখ্যা m দিয়ে ভাগ করলে যদি দেখা যায় n হল m এর গুণিতক, তাহলে বলা যায় তা মৌলিক নয়, বরং যৌগিক। বড় বড় মৌলিক সংখ্যা হিসেব করার জন্যে নানারকম জটিল ও সূক্ষ্ম এলগরিদম তৈরি করা হয়েছে, যাদের মাধ্যমে এই ভাগ করার কৌশল হতে দ্রুততর উপায়ে মৌলিকতা নির্ধারণ করা যায়।
মৌলিক সংখ্যা বের করার কোন সূত্র নেই। তবে মৌলিক সংখ্যার বন্টন, অর্থাৎ পরিসাংখ্যিক দিক থেকে মৌলিক সংখ্যার আচরণ হিসেব করা যায়। এ ধরণের ফলাফল প্রথম পাওয়া যায় মৌলিক সংখ্যা উপপাদ্য থেকে, যে তত্ত্ব অনুসারে দৈবভাবে বাছাই করা কোন সংখ্যা n এর মৌলিক হবার সম্ভাবনা তার অঙ্কসমূহের সংখ্যার সাথে ব্যস্তভাবে সম্পর্কিত, অথবা n এর লগারিদমের সাথে সম্পর্কিত। এ বিবৃতিটি ১৯'শ শতাব্দীর শেষভাগে প্রমাণ করা হয়েছে। ১৮৫৯ সালে প্রদত্ত রীমান হাইপোথিসিস মৌলিক সংখ্যার বণ্টন নিয়ে আরও সুনির্ধারিত অনুমান করতে পারে, তবে এ তত্ত্বটি এখনও প্রমাণিত হয়নি।
মৌলিক ধর্ম
মৌলিক সংখ্যা নিয়ে বিস্তর গবেষণা হলেও এর অনেক মৌলিক ধর্ম নিয়ে আজও অনেক অজানা প্রশ্ন রয়ে গেছে। যেমন গোল্ডবাখের অনুমান - যা অনুযায়ী যে কোন স্বাভাবিক জোড় সংখ্যাকে দুটি মৌলিক সংখ্যার যোগফল আকারে লেখা যাবে, অথবা জমজ মৌলিক অনুমান যা বলে জমজ মৌলিক সংখ্যা অসীমসংখ্যক (জমজ মৌলিকের মধ্যে ২ এর ব্যবধান থাকে, যেমন ১১ ও ১৩) ইত্যাদি শতাব্দীরও অধিক সময় ধরে অপ্রমাণিতই রয়ে গেছে, যদিও এদের বর্ণনা অত্যন্ত সহজ সরল।
মৌলিক সংখ্যার ধারণার প্রয়োগ
তথ্যপ্রযুক্তিতে বেশ কিছু শাখায় মৌলিক সংখ্যার ধারণার প্রয়োগ আছে, যেমন পাবলিক-কি ক্রিপ্টোগ্রাফি, যা বড় সংখ্যাকে মৌলিক উৎপাদকে বিশ্লেষিত করার জটিলতার সুযোগ নেয়। আবার কম্পিউটারে যৌথভাবে মৌলিক সংখ্যা খুঁজে বের করার প্রকল্প বিশেষ ধরণের মৌলিক সংখ্যা নিয়ে গবেষণা উস্কে দিয়েছে, এর মধ্যে উল্লেখযোগ্য হল মার্সেন প্রাইম, যার মৌলিকতা নির্ধারণ তুলনামূলকভাবে সহজতর। ২০০৯ সালের হিসাব অনুযায়ী জ্ঞাত সর্ববৃহৎ মৌলিক সংখ্যায় ১৩০ লক্ষ অঙ্ক আছে।[3]
পাটিগণিতের মৌলিক উপপাদ্য
১ এর থেকে বড় যে কোন প্রাকৃতিক সংখ্যা সংখ্যাকে ক্রমবর্ধমান মৌলিক সংখ্যার গুণফল হিসেবে কেবলমাত্র এক ভাবেই প্রকাশ করা যায়। যেমনঃ ৫২ = ২



×


{\displaystyle \times }

২



×


{\displaystyle \times }

১৩
রীমানের ফাংশন
রীমানের ফাংশনকে লেখা যায় 



ζ
(
s
)
=

∑

n
=
1


∞




1

n

s




=

∏

p




1

1
−

p

−
s







{\displaystyle \zeta (s)=\sum _{n=1}^{\infty }{\frac {1}{n^{s}}}=\prod _{p}{\frac {1}{1-p^{-s}}}}

 যেখানে 



p


{\displaystyle p}

 ক্রমান্বয়ে সব কয়টি মৌলিক সংখ্যা।
ইরাটস্থেনেসের ছাকনি

ইরাটস্থেনেস (২৭৬ খ্রিষ্টপূর্ব - ১৯৪ খ্রিষ্টপূর্ব) মৌলিক সংখ্যাগুলো বের করার একটা সহজ অ্যালগরিদম দিয়েছেন, সব সংখ্যাগুলোকে ছকে সাজিয়ে তার পর এক এক করে প্রথম সংখ্যাটিকে মৌলিক সংখ্যা হিসেবে চিহ্নিত করে তার সব গুণিতকগুলো কেটে দিতে হবে। উল্লেখ্য যে যদি ছকের কোন সর্বোচ্চ সংখ্যা নির্দিষ্ট করে দেয়া না থাকে তবে অ্যালগরিদমটি অনন্তকাল ধরে চলতে থাকবে (কারণ যে কোন সংখ্যার অসীম সংখ্যক গুণিতক থাকে)।
তথ্যসূত্র



বিষয়শ্রেণী:পূর্ণ সংখ্যার ধারা
বিষয়শ্রেণী:মৌলিক সংখ্যা