ad720-90

সংখ্যাতত্ত্বঃ অয়লার টসেন্ট ফাংশন


ইন্টারনেটের নিরাপত্তা নিশ্চিত করা আর গোপনীয়তা রক্ষার জন্য অনেক সময় বড় বড় প্রাইম সংখ্যা বের করতে হয়। শুধু তাই নয়, মৌলিক নয় এমন সংখ্যার উপর হিসাব-নিকাশ চালানোর প্রয়োজনও হয় কখনো কখনো। ছোটবেলায় করা গ.সা.গু আর ল.সা.গুর সমস্যারও প্রয়োগ আছে অনেক। এ সব মিলিয়ে ১৭৬৩ সালে গণিতবিদ কার্ল ফ্রিডরিখ গাউস একটা সমস্যার সমাধান করে ফেলেন, সমস্যাটি হলো:

“তোমাকে যদি একটি সংখ্যা N দেওয়া থাকে, তাহলে বলতে হবে ১ থেকে শুরু করে N এর থেকে ছোট কয়টি সংখ্যা আছে যাদের সাথে N এর গরিষ্ঠ সাধারণ গুণণীয়ক হবে ১”

আমরা পরবর্তীতে দেখতে পাবো যে, গাউসের সমস্যাটির সমাধানকে আমরা Φ(N)  হিসেবে লিখতে পারি। আমরা সিভ অফ ইরাতোসথেনিসের পদ্ধতি আর এই টিউটোরিয়ালের শিক্ষা থেকে আজকে গাউসের প্রায় আড়াইশো বছরের পুরনো এই সমস্যাটি সমাধান করবো।

সহমৌলিক
সংখ্যা:
তোমাকে যদি দুটি সংখ্যা x আর y দেওয়া থাকে, তাহলে তাদের সাধারণ গুণণীয়ক হচ্ছে এমন একটি সংখ্যা z, যা x এবং y উভয়কেই ভাগ করে। আর গ.সা.গু হচ্ছে x আর y এর যত সাধারণ গুণণীয়ক আছে তার মধ্যে বৃহত্তম সংখ্যাটি। যদি তোমাকে ৮ আর ১২ দেওয়া হয়, তাহলে তাদের সাধারণ গুণণীয়ক হচ্ছে ১, ২ ও ৪। ১, ২ আর ৪ এর মধ্যে ৪ সব থেকে বড়, তাই ৪ই হচ্ছে ৮ আর ১২ র গ.সা.গু।

এখন যদি এমন হয় যে x আর y এর গ.সা.গু ১, তাহলে x আর y কে বলা হয় সহমৌলিক সংখ্যা। যেমন: ৯ আর ১৪ এবং ২১ আর ৫২ হচ্ছে সহমৌলিক সংখ্যা বা কো-প্রাইম।

তাহলে গাউসের সমস্যাটার ক্ষেত্রে N যদি একটি মৌলিক সংখ্যা হয়, তাহলে উত্তর কত হবে? ধরি N এর মান ৭, যা একটি মৌলিক সংখ্যা। তাহলে ৭ এর সহমৌলিক সংখ্যাগুলো কি কি? একটু চিন্তা করলে দেখা যাবে, ১ থেকে ৬ পর্যন্ত সবগুলো সংখ্যাই ৭ এর সাথে সহমৌলিক। শুধু ৭ কেন, যে কোন মৌলিক সংখ্যা N এর জন্যই ১ থেকে N – ১ পর্যন্ত সকল সংখ্যাই N এর সাথে সহমৌলিক হবে। সেক্ষেত্রে, আমরা গাউসের সমস্যাটির আংশিক সমাধান পেলাম যেখানে N সর্বদা মৌলিক হবে।

 আংশিক সমাধান: N যদি মৌলিক সংখ্যা হয়, তাহলে,
                                                            Φ(N)=N-

প্রাইম সংখ্যার সূচক: 

এবারে আসা যাক, প্রাইম সংখ্যার সূচকের বেলায়। ধরি, N যদি প্রাইম সংখ্যার একটি সূচক হয়, তবে কয়টা সংখ্যা আছে যারা N থেকে ছোট এবং N এর সাথে সহমৌলিক? উদাহরণ হিসেবে নিলাম ১২৫, যা মৌলিক সংখ্যা ৫ এর একটি সূচক। সমস্যাটা সরাসরি সমাধান করা একটু কঠিন। তাই সমস্যাটিকে যদি একটু উল্টোভাবে চিন্তা করি, ১২৫ থেকে ছোট কয়টা সংখ্যা আছে যারা ১২৫ এর সাথে সহমৌলিক নয়? ১২৫ থেকে ছোট যে সব সংখ্যার সাথে ১২৫ এর গ.সা.গু ১ এর বেশি হবে এমন কিছু সংখ্যা হলো ৫, ১০, ১৫, ২০, ২৫ ইত্যাদি। আমাদেরকে বলতে হবে, এরকম কয়টা সংখ্যা আছে। সাধারণভাবে বললে, দুইটা সংখ্যার গ.সা.গু যদি ১ থেকে বড় হয়, তাহলে নিশ্চয়ই তাদের মধ্যে একটি সাধারণ মৌলিক উৎপাদক থাকতে হবে। কোন সংখ্যা X এর মৌলিক উৎপাদক হচ্ছে এমন মৌলিক সংখ্যা, যেটি X কে নিঃশেষে ভাগ করে। যেমন: ৫০ ও ১২৫ এর ক্ষেত্রে যদি এদেরকে মৌলিক উৎপাদকে বিশ্লেষণ করি তাহলে দেখবো:

১২৫ = ৫ * ৫ * ৫
৫০ = ২ * ৫ * ৫

এখানে দেখা যাচ্ছে, উভয় সংখ্যার মধ্যেই সাধারণ মৌলিক উৎপাদক হিসেবে ৫ আছে। তাই তাদের গ.সা.গু অবশ্যই ১ থেকে বড় হবে। এখন ১২৫ এর মত কোন মৌলিক সংখ্যার সূচককে মৌলিক উৎপাদকে বিশ্লেষণ করলে কেবল একটি মৌলিক সংখ্যাই পওয়া যাবে। যেমন: ১২৫ কে আকারে লেখা যায় যেখানে ৫ একটি মৌলিক সংখ্যা এবং ৩ তার সূচক।

সুতরাং ১২৫ এর সাথে যদি কারো গ.সা.গু ১ এর বেশি হয়, তবে তাদের মৌলিক উৎপাদকেও ৫ কে থাকতেই হবে। গুছিয়ে বললে, যদি N = P*x হয়, যেখানে P একটি মৌলিক সংখ্যা এবং x তার একটি ধনাত্মক সূচক। তাহলে যে সকল সংখ্যার সাথে N এর গসাগু ১ এর চেয়ে বড় হবে, তাদের মৌলিক উৎপাদকের বিশ্লেষণ করলে সেখানে P কে থাকতেই হবে। এখন প্রশ্ন হচ্ছে, ১২৫ পর্যন্ত কতগুলো সংখ্যা আছে, যাদের মৌলিক উৎপাদক হিসেবে অন্তত একবার হলেও ৫ থাকবে? উত্তর হচ্ছে, কেবলমাত্র ৫ এর গুণিতকগুলোতেই ৫ উৎপাদক হিসেবে থাকবে।

আলোচনা সামনে আগানোর আগে একটি ধাঁধা। ধাঁধাটি হলো, ১ থেকে N পর্যন্ত কয়টি সংখ্যা আছে যারা k দ্বারা বিভাজ্য? উত্তর হবে, N কে k দিয়ে ভাগ করলে যে ভাগফলটি পাবো সেটাই, অর্থাৎ N / k এর ভাগফল। উত্তরটা সহজ হলেও এটা কেন হলো সেটা চিন্তা করে দেখো।

তাহলে ১২৫ পর্যন্ত ৫ এর গুণিতক কয়টা আছে? কয়টি সেটি বের করা খুব সহজ, ১২৫ কে ৫ দিয়ে ভাগ করলেই আমরা সেই সংখ্যাটা পাবো, সেটা হলো ২৫। তাহলে, ১২৫ পর্যন্ত ধনাত্মক সংখ্যা আছে ১২৫টি, এর মধ্যে সহমৌলিক নয়, এমন সংখ্যা ২৫টি, তাহলে ১২৫ এর সহমৌলিক সংখ্যা হলো সর্বমোট ১২৫ – ২৫ = ১০০ টি। এ তো গেলো কেবল ১২৫ এর ক্ষেত্রে, কিন্তু যে কোন প্রাইমের সূচকের সময়ে কি একই রকম কিছু করা যাবে?

টসেন্ট ফাংশন বা ফাই ফাংশন

অয়লারের ফাই ফাংশন বা টসেন্ট ফাংশনটি একটি ধনাত্মক পূর্ণ সংখ্যা N এর জন্য N থেকে ছোট তার সব সহমৌলিক সংখ্যার গণণা দেয়। এর মধ্যে আমরা ফাই ফাংশনের কিছু উদাহরণ দেখেছি। কয়েকটি উদাহরণ হলো:

 Φ(২)=১
     Φ(৭১)=৭০
        Φ(১২৫)=১০০

একটু আগের আলোচনা থেকে আমরা বলতে পারি, যে কোন সংখ্যা যদি N = px আকারের হয়, তবে

Φ(N)=px-px/p
        =px-px-1
                                           
=p* (1-1/p) (pকমন নিযে )
                =p* (p-1/p) 

এতগুলো হিসাব-নিকাশ দেখে চিন্তিত হওয়ার কিছু নেই, ভেঙ্গে বলছি। ১ থেকে px পর্যন্ত সর্বমোট পূর্ণসংখ্যা হলো  pটি। এর মধ্যে আবার px/p টি সংখ্যাকে N এর সাথে গ.সা.গু করলে হয় ১ এর থেকে বড়। তাহলে, মোট সংখ্যা থেকে ১ এর বড় গ.সা.গু ওয়ালা সংখ্যা গুলোকে বাদ করে দিলেই আমরা আমাদের উত্তর পেয়ে গেলাম।

কিন্ত কথা হচ্ছে, সব সংখ্যাই তো আর একটি প্রাইম সংখ্যার সূচক নয়। সেক্ষেত্রে আমরা কি করতে পারি? আমরা পরের ধাপে যাই। এমন একটি সংখ্যা নিই, যেটা দুটি প্রাইম সংখ্যার গুণফলের সমান। ৩৫ ও ৫৫ হচ্ছে এমন দুটি সংখ্যা:     

Φ(৫ *৭)=২৪ 
Φ(৫ *১১)=৪০
এখন প্রশ্ন হচ্ছে, এই সংখ্যাগুলোর জন্য ফাই ফাংশনের মান আমরা পেলাম কি করে। ধরি, দুইটা প্রাইম সংখ্যা p ও q আছে, তাহলে আমাদের বের করতে হবে Φ( p * q ) কত। একটা জিনিস খেয়াল করো, যদি এমন একটা সংখ্যা x থাকে যাতে (p*q,x) > ১ হয় অর্থাৎ p * q ও x এর গ.সা.গু ১ এর বড় হয়, তাহলে x এর মৌলিক উৎপাদকে অবশ্যই p বা q থাকতেই হবে। এটা কেন সত্যি হবে সেটা কিছুক্ষণ নিজে নিজে চিন্তা করে দেখো। এখন x যদি p * q এর থেকে ছোট হয়, তাহলে x এর মৌলিক উৎপাদকে p ও q কখনোই একসাথে থাকতে পারবে না। এটাও কেন হয় একটু ভাবো।

 

তাহলে নিচের কথা গুলো এখন আমরা বলতে পারি: 

১. ১ থেকে p*q পর্যন্ত p দিয়ে ভাগ যায় এমন সংখ্যা p*q/p =q  টি।

২. ১ থেকে p*q পর্যন্ত q দিয়ে ভাগ যায় এমন সংখ্যা  p*q/q=p টি।

৩. ১ থেকে p*q পর্যন্ত p ও q উভয় দিয়ে ভাগ যায় এমন সংখ্যা ১ টি।

৪. ১ থেকে p*q পর্যন্ত সর্বমোট সংখ্যা p*q টি।

৫. ১ থেকে p*q পর্যন্ত p ও q এর অন্তত একটি সংখ্যা দিয়ে ভাগ যায় এমন সংখ্যা p + q – ১ টি। এক বিয়োগ দেওয়ার কারণ হলো, আমরা p*q সংখ্যাটি দুইবার নিয়ে ফেলেছিলাম, কারণ তারা p ও q উভয় দিয়েই ভাগ যায়।

সুতরাং,

       Φ ( p*q ) = ( p* q)-p-q+1
                       =p(q-1)-1(q-1)
                      =(p-1)(q-1)

কিন্ত p আর q উভয়েই যেহেতু প্রাইম সংখ্যা সেহেতু আমরা আগে থেকেই জানি যে:

                  Φ ( p)=p-1
                  Φ ( q )=q-1

তাহলে,              

                   Φ ( p*q) = (p-1) (q-1)
                                 =Φ ( p ) * Φ ( q )

লক্ষ করো যে, দুইটা সংখ্যা যদি প্রাইম হয়, তবে তারা নিজেদের মধ্যে অবশ্যই সহমৌলিকও হবে। কিন্ত যদি এমন হয়, যে p ও q এর অন্তত একটি সংখ্যা প্রাইম নয়, কিন্ত তাও তারা সহমৌলিক, সেক্ষেত্রেও কি  Φ ( p*q) =Φ ( p ) * Φ ( q )  সত্যি হবে? এই প্রশ্নের উত্তরও হ্যাঁ। তবে, কেন এটি সত্যি হবে, সেটা আমরা চাইনিজ রিমাইন্ডার থিওরেম নিয়ে আলোচনা করার সময়ে দেখবো। এখন আমরা আসল হাতিয়ার হাতে পেয়ে গেছি, যেটা দিয়ে যে কোন সংখ্যার ফাই ফাংশনের মান আমরা বের করতে পারবো।

শেষ ধাপ: 

১ ব্যতীত অন্য যে কোন পূর্ণ সংখ্যাকে এক বা একাধিক প্রাইম সংখ্যার সূচকের গুণফল হিসেবে প্রকাশ করা যায়। এভাবে একটি সংখ্যাকে লিখলে সেই রূপটাকে বলা হয় সংখ্যাটির মৌলিক উৎপাদকে বিশ্লেষণ। আমরা ছোটবেলায় সবাই খাতা-কলমে এই কাজটি করেছি। ৭২০ কে মৌলিক উৎপাদকে বিশ্লেষণ এমন হবে:

 ৭২০ = ২+ ৩ + ৫  

 সাধারণভাবে, একটি সংখ্যা N কে মৌলিক উৎপাদকে বিশ্লেষণ করলে নিচের মতো হবে:
01এখানে, থেকে  হচ্ছে বিভিন্ন আলাদা মৌলিক সংখ্যা এবং থেকে হচ্ছে ক্রমানূসারে তাদের সূচক।
মনে করি, তাহলে, N কে S * T আকারে লেখা যায়। এখন লক্ষ করি যে, S আর T এর মাঝে কোন সাধারণ মৌলিক সংখ্যা নাই। সুতরাং, S ও T এর গ.সা.গু ১ বা তারা সহমৌলিক। কিন্ত সহমৌলিক সংখ্যার ক্ষেত্রে আমরা জানি যে:যেহেতু S প্রাইম সংখ্যা P1 এর একটি সূচক, তাই 
তাহলে  Φ(N) এখন নিচের মত করে লেখা যায়, 
05একইভাবে, T কে ভেঙ্গে নিচের মত করে লেখা যায়:
এখানে U ও V সহমৌলিক হবে। তাহলে, Φ(T)  হবে
07এই অবস্থায় Φ(N)  হবে:
08এভাবে করে আগাতে থাকলে শেষমেষ এই অবস্থা এসে দাঁড়াবে:
কিন্তু আমরা জানি,  তাহলে,যদি আমরা একটি সংখ্যা N এর মৌলিক উৎপাদকগুলো জানতে পারি, তাহলে এভাবে করে আমরা সহজেই ফাই এর মান বের করতে পারবো। তোমরা যদি সিভের মাধ্যমে মৌলিক সংখ্যা বের করে থাকো, তাহলে প্রায় একই পদ্ধতি অবলম্বন করে ১ থেকে N পর্যন্ত সকল সংখ্যার ফাই এর মান বের করতে পারবে।
ফাই ফাংশনের একটা সি এর কোড:  https://go.toph.co/2mjffci

অনুশীলনী:

https://go.toph.co/2lQvuxl

https://go.toph.co/2lSazd6

https://go.toph.co/2lY7HLC

https://go.toph.co/2kigzLK

https://go.toph.co/2md33cT

*তারিফ এজাজ:  সফটওয়্যার প্রকৌশলী, অবিচল আইটি





সর্বপ্রথম প্রকাশিত

Sharing is caring!

Comments

So empty here ... leave a comment!

Leave a Reply

Sidebar