Euler এর Totient Function ( ϕ )

                   Euler এর Totient Function ( ϕ )

প্রোগ্রামিং এ Totient Function একটা গুরুত্বপূর্ণ টপিক্স এবং অনেক মজারও।

প্রথমে জেনে নেই Totient Function টা কি...?

 Φ(n)=n এর সমান বা n থেকে ছোট এমন কতগুলো সংখ্যা যা n এর coprime.

Coprime এর অর্থ হল যাদের কোন সাধারণ গুণনীয়ক নেই।

যেমনঃ ১, ২ , ৩, ৪, ৫, ৬, ৭, ৮, ৯, ১০, ১১, ১২, ১৩, ১৪, ১৫, সংখ্যা গুলোর মধ্যে ১৫ এর সাথে (৩, ৫, ৬, ৯, ১০, ১২, ১৫) সংখ্যা গুলোর কোন না কোন সাধারণ গুণনীয়ক আছে। কিন্তু

বাকি (১,২,৪,৭,৮,১১,১৩,১৪) এই ৮ টি সংখ্যা গুলোর সাথে ১৫ এর কোন সাধারণ গুণনীয়ক নেই।সুতরাং Φ (১৫ )= ৮;

Φ(n)=n(1-1/p1)(1-1/p2)......(1-1/pk)

15 এর ক্ষেত্রে এর গুণনীয়ক   

                                   = ৩,৫ ;p1=3,p2=5;

১ম ক্ষেত্রেঃ

n(1-1/p1)=(n-n/ ৩)=( ১৫  -  ১৫/ ৩)…. এখানে  ১৫/৩ =৫ ,মানে হচ্ছে ১৫ এর ভিতর ৩ এর ৫ টি গুনিতক আছে, এবং (১৫-৫)=১০ টি সংখ্যা যাতে ৩ এর গুনতক নেই...প্রথমে এভাবে ৩ এর গুনতক বাদ দিলে থাকে ১০ টি সংখ্যা-(১,২,৪,৫,৭,৮,১০,১১,১৩,১৪)

n(1-1/p1)=১০;

২য় ক্ষেত্রেঃ

১০(1-1/p২)=(১০ - ১০ / ৫)…. এখানে  ১০/৫ =২ ,মানে হচ্ছে ১০ এর ভিতর ৫ এর ২ টি গুনিতক আছে, এবং (১০-২)=৮ টি সংখ্যা যাতে ৫ এর গুনতক নেই.. এভাবে ৫ এর গুনতক বাদ দিলে থাকে ৮ টি সংখ্যা-(১,২,৪,৭,৮,১১,১৩,১৪)

(১০-১০/৫)=৮;

সুতরাং Φ(১৫)=  ৮; এভাবে কোন একটা সংখার গুণনীয়ক গুলো বের করে আমরা সহজেই coprime বের করতে পারি। সহজে বলা যায় কোন একটা সংখ্যা ,যেমনঃ ১৫, এর সাথে ১৫ এর ছোট ঐ সংখ্যা গুলি যাদের সাথে ১৫ এর গ সা গু ১;ঐ সংখ্যা গুলি বের করার জন্য Totient Function  ব্যাবহার করা হয়।

                                        ’’ধন্যবাদ’’