The Euler ϕ function

I. Cnop
Vrije Universiteit Brussel
icnop@vub.ac.be

Introduction

The Euler Phi function counts for each natural number   n  the number of natural numbers relatively prime and smaller  than  n  .  
This important function from number theory is included in the standard  Mathematica commands.

EulerPhi[20]

In order to get more insight we want to program our own. 
It shows programming style in  Mathematica and therefore is a useful exercise. Programming will involve lists such as

Range[10]

and operations on them: making their product

Times @@ %

or generating a set of special fractions

Map[(1 - 1/#) &, Range[10]]

As a bonus we will be able to obtain a symbolic result by our programming.

Writing our own program

Start by reasoning from an example

n = 30

FactorInteger[n]

Being relatively prime only depends on (not) having a prime factor in common with  n .

primes[n_] := First[Transpose[FactorInteger[n]]]

relPrime[k_] :=  GCD[k, n] == 1

Select[Range[n], relPrime]

commonPrime[k_] :=  GCD[k, n] != 1

Select[Range[n], commonPrime]

We write out all prime factor of  n  and for each prime factor  p  , we delete all multiples  j p   of this prime factor. 
The amount of numbers we delete for  p  is  (n/p) .
Taking into account doubles (multiples of two different   p ), triples (multiples of three different   p ), ....  , we obtain by the inclusion-exclusion principle a formula where the ratio of not deleted numbers for all  p  is  the product of all  (1 - (1/p)). 
[If you do not know this inclusion-exclusion principle, do this by reasoning on sets of multiples obtained by]

Table[primes[n][[j]] Range[n/primes[n][[j]]], {j, 
          Length[primes[n]]}] // TableForm

So finally:

FactorInteger[n]

First[Transpose[%]]

(1 - 1/#) &[%]

n Times @@ %

Collect these last lines into a program

primes[n_] := 
        First[Transpose[FactorInteger[n]]];
mult[n_] := 
        Map[(1 - 1/#) &, primes[n]];
ourPhi[n_] := n Times @@ mult[n]

Testing

n = 96

primes[n]

mult[n]

ourPhi[n]

EulerPhi[n]

The case  n  is prime

Question: what is the  ϕ(n) for a prime number n?

The case  n   is a product of different primes

First answer the following questions:

Question: what is the ϕ(n) for   n = p q    (both prime numbers)?

Question: what is the  ϕ(n) for   n = p q r   (all prime numbers)?

This can be handled symbolically too:

If we tell the computer what are the different primes involved - how could it know the factorisation of an unspecified number

primes = {p, q, r}

and tell it   n   is their product

n =  Times @@ %

Map[(1 - 1/#) &, primes]

n Times @@ %

Expand[Together[%]]

A correct answer!

Questions

Try this for two and four primes as well.
Next try it for   n = (p^3) (q^2) r  and check your result for   n  =   360.

Other issues

Plotting  ϕ

Plotting  ϕ   for related numbers also yields some unexpected results. Perform

ListPlot[Table[ourPhi[k], {k, 2, 120}]]

ListPlot[Table[ourPhi[k], {k, 10, 600, 5}]]

Question

For which entries  n  does   ϕ(n)  correspond to    5 ϕ(5n).
To see this, animate both graphs after correctly aligning them.

Efficiency

It is remarkable that our program is not significantly slower than the one built-in in  Mathematica . 
The  main reason is that they both use FactorInteger and this amounts for most of the processor usage.

Timing[EulerPhi[10^20 - 3]]

Timing[ourPhi[10^20 - 3]]

Conclusion

Programming in Mathematica is simple, transparant and fast