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


    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


    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):
    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


    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):
      f = factor(n);
      t = 1;
      for(i=1, #f[,1],
        t *= f[i, 1] - 1;
        t *= f[i, 1]^(f[i, 2] - 1);
    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);
    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

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)