# Euler totient function

• Mar 25th 2007, 04:56 AM
jedoob
Euler totient function
Hi,

Can someone please tell me how to compute the Euler totient function for large values of n?

e.g n=3800.
• Mar 25th 2007, 05:07 AM
ThePerfectHacker
Quote:

Originally Posted by jedoob
Hi,

Can someone please tell me how to compute the Euler totient function for large values of n?

e.g n=3800.

If n>1
Factorize,
n=p_1^a_1 p_2^a_2 *...* p_n ^ a_n

Then,

phi(n) = n*(1-1/p_1)(1-1/p_2)*...*(1-1/p_n)
• Mar 25th 2007, 07:10 AM
CaptainBlack
Quote:

Originally Posted by jedoob
Hi,

Can someone please tell me how to compute the Euler totient function for large values of n?

e.g n=3800.

Me I fire up Euler and type:

Code:

```>load "C:\Documents and Settings\CB\My Programs\Euler23\Euler Utils\number theory.e"; > > >EulerTotient(3800)         1440 >```
Where EulerTotient is defined as:

Code:

``` function EulerTotient(n) ## ## Function to calculate the Euler Totient ## function of its argument ## ## The Euler Totient function of N returns the number ## of integers coprime to N and less than N (counting 1) ## ## Abromowitz and Stegun Section 24.3.2 gives: ## ## phi(N)=N.prod[(1-1/p),p|N] ## ## that is it is N times the product over primes p which divide ## N of (1-1/p). ## ## This is used in Eulers extension to Fermat's little ## theorem: ## ## if gcd(a,n)=1, a^phi(n) = 1 (mod n). ## ## CaptainBlack 2003 ##   fctrs=factor1(n); ..gives the prime factorisation of n with muliplicities   fctrs=fctrs(:,1)'; ..just keep the distinct primes     product=n*prod(1-1/fctrs);     return round(product,0)  ..round to nearest integer incase or rounding errors in float calculations endfunction;```
Note the comments are longer than the code!

RonL