The Phi Function

Date: 11/21/98 at 07:33:45
From: Patrick Browne
Subject: The Phi Function

I think you are really great for running this service. My question is 
on the Phi Function:

   For any positive integer n, the phi function phi(n) is defined as 
   the number of positive integers less than n which have no factor 
   (other than 1) in common (are co-prime) with n.

I have to find the answer to these equations. Does phi(7*4) = 
phi(7)*phi(4)? I have to find the conditions on n and m so that 
phi(n*m) = phi(n)*phi(m). If p and q are prime, investigate 
phi(p^n * q^m). I have found that they work if co-prime and don't if 
they share common factors. Please help.

Date: 11/21/98 at 11:03:51
From: Doctor Anthony
Subject: Re: The Phi Function

Remember that 1 is always counted as prime to every other number, so 
for example, phi(2) = 1, phi(13) = 12, phi(18) = 6.

The rules concerning phi(n) are as follows:

If the numbers a,b,c,d,... are prime to each other (have no factors in
common) then:

 phi(abcd...) = phi(a) * phi(b) * phi(c) * phi(d) ...

and so you will find that phi(7*4) = phi(7)*phi(4) because 7 and 4 are
co-prime.

Since we have phi(28) = 12, phi(7) = 6, and phi(4) = 2, 
phi(7*4) = phi(7)*phi(4).

The general rule for phi(n*m) = phi(n)*phi(m) is as stated above. Thus, 
the expression is true if n and m are co-prime (relatively prime). The 
proof is not difficult but rather wordy. Most textbooks on intermediate 
algebra will give the proof. You could demonstrate its truth with 
examples where n and m are co-prime and when they are not co-prime.

If you want the method for calculating the value of phi(N) for any N 
we proceed as follows:

First express the number N in its prime factors in the form:

   N = a^p b^q c^r ... 

where a, b, c, ... are different prime numbers and p, q, r, ... are 
positive integers.

Then the number of positive integers less than N and prime to it is:

   phi(N) = N(1 - 1/a)(1 - 1/b)(1 - 1/c).......

Example: Find phi(12). We express 12 in its prime factors as 2^2 * 3. 
Then:

   phi(12) = 12(1 - 1/2)(1 - 1/3)
           = 12(1/2)(2/3)
           = 4

and the four numbers co-prime to and less than 12 are:

   1, 5, 7, 11

We can also show that phi(a^p) = a^p - a^(p-1) where a is prime.
Consider the natural numbers 1, 2, 3, ....(a^p - 1), a^p. The only ones 
amongst these not prime to a are:

   a, 2a, 3a, .... (a^(p-1) - 1)a, a^(p-1)a

and the number of these numbers is a^(p-1). So the number that are 
prime to a^p is  a^p - a^(p-1).

Then we know phi(a^p) = a^p - a^(p-1) = a^p[1 - 1/a].

- Doctor Anthony, The Math Forum
  http://mathforum.org/dr.math/   

Date: 11/21/98 at 11:21:37
From: Patrick Browne
Subject: Re: The Phi Function

I want to know why the above formulas work only sometimes. For example, 
4 and 8 don't work. Why? 

Date: 11/21/98 at 16:50:17
From: Doctor Anthony
Subject: Re: The Phi Function

Since you have had trouble understanding the method when applied to a 
general case phi(ab), I will deal with actual numbers and leave it to 
you to see that the argument is general and could be extended to any 
values for 'a' and 'b'. Let us look again in detail at the situation 
where a = 7 and b = 4.

Example: a = 7, b = 4, ab = 28 

    1  2  3  4  5  6  7 
    8  9 10 11 12 13 14 
   15 16 17 18 19 20 21 
   22 23 24 25 26 27 28 

We lay out the numbers 1 to 28 in 4 rows of 7 as shown above.

There are 6 numbers prime to 'a' (= 7) and so every column except the 
last one will be headed by a number prime to 'a'. The numbers in any 
column are 7 greater than the one above them in that column, so if the 
first item in the column is prime to 7 then so is every other number in 
that column prime to 7. So there are 6 columns in the table in which 
every number in the column is prime to 7. Altogether there are 24 
numbers out of the original 28 that are prime to 7. They are:

    1  2  3  4  5  6   
    8  9 10 11 12 13 
   15 16 17 18 19 20 
   22 23 24 25 26 27 

We must now consider how many of these are also prime to 4.

Take for example the column headed by the number 3. We need to find out 
how many numbers in that column are prime to 4. The four numbers in the 
column are  3, 10, 17, 24  and it is easy to see that two numbers are 
even and so not prime to 4, so that in this column there are 2 numbers 
that are prime to 4.  If you look at any of the other 6 columns you 
will see that each has two even numbers and two odd numbers, meaning 
that each has two numbers prime to 4. With 6 columns each containing 
2 numbers prime to 4 there are 12 numbers in the table that are prime 
to both 7 and 4 and hence prime to 28. So we get phi(28) = 6 * 2 = 
phi(7) * phi(4).

The justification for the number of numbers in any column that are 
prime to 4 is to note that the remainders when the numbers in any 
column are divided by 4 will always be 0, 1, 2, 3, (not necessarily in 
that order). In general terms the remainders will always be 
0, 1, 2, ..., (b-1) and the number of these that are prime to b is 
exactly phi(b). Why, I hear you ask, will the remainders always be 0, 
1, 2, 3?  This is because the numbers in say the column 3, 10, 17, 24 
form an arithmetic progression (the difference between successive 
numbers is a constant 7).

Suppose that two of the remainders are the same = r (e.g. for 10 and 
24):

   24 = 3 + (3*7) = 4 q1 + r  and 
   10 = 3 + (1*7) = 4 q2 + r 
   -------------------------  subtracting
        7(3 - 1) = 4(q1 - q2)

Now  7(3-1) must be divisible by 4, but 7 is prime to 4 so this 
requires that (3-1) be divisible by 4. But that is impossible because 
both 3 and 1 are less than 4. It follows that no two remainders can be 
the same, and so the remainders must be 0, 1, 2, 3 in some order.  

If you try to find phi(32) from phi(8) and phi(4) the method breaks 
down completely, as the remainders when numbers in any column are 
divided by 4 instead of being all different are all the same. For any 
composite number like 32 you must first factorize into prime factors:

   32 = 2^5  

and then:

  phi(32) = 32(1-1/2) = 32 * 1/2 = 16

- Doctor Anthony, The Math Forum
  http://mathforum.org/dr.math/