Euler's Totient Function (phi function)

Euler's Totient Function (also Euler's Phi Function)

Euler continued to investigate the properties of numbers –

specifically the distribution of prime numbers.

One important function he defined

is called the 'phi function.'

It measures the breakability of a number.

So, given a number, say, 'n,'

it outputs how many integers are less than or equal to n

that do not share any common factors with n.

For example, if we want to find the phi of 8,

we look at all values from 1 to 8,

and then we count how many integers

8 does not share a factor greater than 1 with.

Notice, 6 is not counted,

because 6 and 8 share the factor 2,

while 1, 3, 5 and 7 are all counted,

because they only share the factor 1.

Therefore, phi(8) = 4.

What's interesting is that

calculating the Phi function is hard, except in one case.

Look at this graph.

It is a plot of values of phi over integers from 1 to 1000.

Now, notice any predictable pattern?

The straight line of points along the top

represents all the prime numbers.

Since prime numbers have no factors greater than 1,

the phi of any prime number, 'p,' is simply p-1.

To calculate phi of 7 – a prime number –

we count all integers except 7 –

since none of them share a factor with 7.

Phi of 7 = 6.

So if you are asked to find phi of 21,377, a prime number,

you would only need to subtract 1 to get the solution –

21,376.

phi of any prime is easy to compute.

This leads to an interesting result, based on the fact that

the phi function is also 'multiplicative.'

That is, phi(A x B)=phi(A) x Phi(B).

If we know some number, N,

is the product of two primes, P1 and P2,

then phi of N is just the value of

phi for each prime multiplied together, –

or (P1 - 1) x (P2 - 1).