# Euler phi function

## Main Question or Discussion Point

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?

Related Linear and Abstract Algebra News on Phys.org
CRGreathouse
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:
CRGreathouse
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:
(11:09)eulerphi(10^50+35)
time = 375 ms.
%10 = 52844036689487355925892416914616365612135546307584

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!

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

Code:
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))".