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...