1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Euler phi function

  1. Nov 18, 2008 #1
    How do i comput the euler phi function of a large interger?
    i know that if p is prime then phi(p)=p-1 and i've found a formula for computing non primes but i dont know how to implement in something like Matlab.
    Does anyone know how?
     
  2. jcsd
  3. Nov 18, 2008 #2

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    What, Matlab doesn't have that already?

    phi is a multiplicative function: phi(ab) = phi(a) * phi(b) if gcd(a, b) = 1. So to find phi(n), first factor n and then find phi(p^k) for each prime p dividing n exactly k times. Have you seen the formula for that? Can you prove it?

    As for implementing the formula, just loop through the factor vector.
     
    Last edited: Nov 18, 2008
  4. Nov 18, 2008 #3

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    By the way, I assume this is for homework. If not, I strongly recommend Pari/GP rather than Matlab for number theory! The command in Pari/GP is eulerphi:

    Code (Text):
    (11:09)eulerphi(10^50+35)
    time = 375 ms.
    %10 = 52844036689487355925892416914616365612135546307584
     
  5. Nov 18, 2008 #4
    Ok thanks i'll have a go at it. I dont have PARI/GP but i mite try and download it, i generally use matlab cus it relativly easy. Its not a homework question, a lecture mentioned it and im just trying to understand it!
    Thanks for your comments!
     
  6. Nov 18, 2008 #5

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    No problem. I think that Pari is easier to use for these sorts of problems than Matlab, that's why I suggested it.

    If you wanted to implement phi on your own in Pari (obviously it won't be quite as fast, but it'll help you understand):

    Code (Text):
    myPhi(n)={
      local(f,t);
      f = factor(n);
      t = 1;
      for(i=1, #f[,1],
        t *= f[i, 1] - 1;
        t *= f[i, 1]^(f[i, 2] - 1);
      );
      t
    }
    The code loops through each prime component p^k and multiplies the running total t by p - 1 then by p^(k-1). For large n, most of the time is spent factoring (or proving primality) and so the code isn't actually that much worse in those cases.
     
  7. Jun 25, 2009 #6
    I'll reply because this thread is a top Google hit:
    Code (Text):
    function phi = eulerphi(n)
        phi = n;
        for i = 1:length(n)
            p = unique( factor(n(i)) );
            phi(i) = phi(i) * prod(1 - 1./p);
        end
    end
    The for-loop makes the function work with vectors, which is useful for MATLAB commands like "stem(1:100,eulerphi(1:100))".
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Euler phi function
  1. Euler, phi and division (Replies: 11)

  2. Euler's phi function (Replies: 3)

  3. Euler phi function (Replies: 7)

Loading...