Eulear phi function

Relative prime:

 দুইটি number কে তখন relative prime number বলা হবে যখন তাদের মধ্যে ১ ব্যতিত অন্য কোন ফ্যাক্টর থাকবে না।
Example:
           5 এবং 7 এদের মধ্যে 1  ব্যতিত অন্য কোন ফ্যাক্টর নেই।
    সুতরাং ,আমরা বলতে পারি 5 এবং 7 relative prime number.
আজকে আমরা এমন একটি algorithm নিয়ে আলোচনা করব যা হলো একটি number পর্যন্ত কতগুলি relative prime number আছে ,তা বের করা।
আগে আমরা একটা example দেখি...
 Explanation: 
        আমরা 10 পর্যন্ত কতটি relative prime number আছে তা বের করব।
   প্রথমে আমরা 1 থেকে start করব...
          ১. 1 এবং 10 এর মধ্যে ১ ব্যতিত অন্য কোন ফ্যাক্টর নেই। তাহলে আমরা এখানে একটা relative prime number পেলাম।
        ২.  2 এবং 10 এর মধ্যে   ১ ব্যতিত অন্য  ফ্যাক্টর 2 রয়েছে ।তাই তারা realtive prime number নয়।
        ৩.  3 এবং 10 এর মধ্যে ১ ব্যতিত অন্য কোন ফ্যাক্টর নেই। তাহলে আমরা এখানে একটা relative prime number পেলাম।
       ৪. 4 এবং 10 এর মধ্যে   ১ ব্যতিত অন্য  ফ্যাক্টর 2 রয়েছে ।তাই তারা realtive prime number নয়।
     ..................................................................................................................................
..............................................................................
এইভাবে দেখা যায় যে , 10 এর মধ্যে relative prime number গুলো হলো...
1,3,7,9
এখন আমরা যে law ব্যবহার করব তা হলোঃ

   f(a^k)=a^(k-1)*(a-1).
          N.B: f(ab)=f(a)*f(b).

  এখানে a^k =number(আমরা যে number পর্যন্ত relative prme number করব)=10(কারন আমি এখন 10 নিয়ে বিবেচনা করছি)

আমরা 10 কে (2*5) দ্বারা লিখতে পারি।  

  f(2*5)=f(2)*f(5).

         f(2)=f(2^1)=2^0(2-1)=1

           and f(5)=f(5^1)=5^0(5-1)=4.
f(10)=f(2*5)=f(2)*f(5)=1*4=4
তাহলে আমরা আমাদের result পেয়েছি 4.

using this formula you can solve the following problem::
1.Uva problem number theory(11064)

2.uva problem Relative