Euler phi function

  • Thread starter paton51
  • Start date
  • #1
8
0

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?
 

Answers and Replies

  • #2
CRGreathouse
Science Advisor
Homework Helper
2,820
0
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:
  • #3
CRGreathouse
Science Advisor
Homework Helper
2,820
0
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
 
  • #4
8
0
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!
 
  • #5
CRGreathouse
Science Advisor
Homework Helper
2,820
0
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.
 
  • #6
6
0
I'll reply because this thread is a top Google hit:
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))".
 

Related Threads for: Euler phi function

  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
1
Views
5K
  • Last Post
Replies
7
Views
5K
  • Last Post
Replies
11
Views
12K
Replies
4
Views
8K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
2
Views
2K
Replies
13
Views
15K
Top