Euler phi function

1. Nov 18, 2008

paton51

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. Nov 18, 2008

CRGreathouse

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
3. Nov 18, 2008

CRGreathouse

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

4. Nov 18, 2008

paton51

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!

5. Nov 18, 2008

CRGreathouse

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.

6. Jun 25, 2009