Phi Function

Date: 07/07/99 at 15:05:17
From: steven hopkins
Subject: The phi function

I am doing some coursework and need some help with it.        

If we have n and m as the subjects, I have to investigate whether 
phi(n)*phi(m) = phi(n*m).

Can you give me any advice or formulas that involve n and m?

Steve H.

Date: 07/07/99 at 15:56:48
From: Doctor Anthony
Subject: Re: The phi function

Euler's Phi Function
---------------------
The number of positive integers less than N and relatively prime to it 
is denoted by phi(N)

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 primes
                             and p, q, r, ... are positive integers.

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

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

Remember that 1 is always counted as relatively prime to every other 
number, so 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.

phi(28) = 12  and   phi(7) = 6,  phi(4) = 2

The general rule for phi(n*m) = phi(n)*phi(m) is as stated above.  
True if n and m are co-prime.

To prove phi(ab) = phi(a).phi(b), if a and b are coprime we proceed as 
follows: 

Consider the product ab. The first ab integers can be written in b 
lines each containing a numbers. 

1       2      3       4 .....   k .       a 
a+1    a+2     a+3    a+4 .... .a+k .......a+a 
2a+1  2a+2    2a+3   2a+4 .....2a+k ......2a+a 
-------------------------------------------------- 
-------------------------------------------------- 
(b-1)a+1, -------------------(b-1)a+k-----(b-1)a+a 

Consider the vertical column that begins with k. If k is prime to 'a' 
all the terms of this column will be prime to 'a' , but if k and 'a' 
have a common factor no number in the column will be prime to a. Now 
the first row contains phi(a) numbers prime to a; therefore there are 
phi(a) vertical columns in each of which every term is prime to a.; 
let us suppose that the vertical column which begins with k is one of 
these. This column is an AP the terms of which when divided by b leave 
remainders 0, 1, 2, ....., b-1 in some order. (See example below). 
Hence the column contains phi(b) integers prime to b. 

Similarly, each of the phi(a) vertical columns in which every term is 
prime to 'a' contain phi(b) integers prime to b; hence in the table 
there are phi(a).phi(b) integers which are prime to a and also to b, 
and therefore to ab; that is phi(ab) = phi(a).phi(b) 

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 

If you consider the column with first term 5 then the numbers in this 
column are:
 
5 12 19 26  and the remainders on division by 4 are: 
1  0  3  2  which correspond to 0, 1, 2, .... (b-1) in some order as 
stated above. 

If you have 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 from 28 that are prime to 7. We must now consider how many 
of these are ALSO prime to 4.

Now 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 x 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 were the same = r (e.g. for 10 and 
24).

We suppose   24 = 3 + (3x7) = 4.q1 + r 
         and 10 = 3 + (1x7) = 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 tried 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 x 1/2 = 16
  
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

  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


To 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 among 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)

From which  phi(a^p) = a^p - a^(p-1)  

                     = a^p[1 - 1/a]

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

Date: 07/14/99 at 14:45:51
From: steven hopkins
Subject: The phi function

Can you tell me the formula for the phi function?  If I am given a 
number, I need the formula for finding the integers quickly. I know 
how to do it but I can not put it into a formula.

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

I am a bit unsure how you get the integers from that. Can you please 
send an explanation with the formula?

Date: 07/14/99 at 15:04:02
From: Doctor Anthony
Subject: Re: The phi function

If you want phi(36), for example, the method is as follows:

First express 36 in its prime factors:

   36 = 2^2 x 3^2   The numbers 2 and 3 are the important ones.  It 
does not matter what power they are raised to.

So phi(36) = 36(1 - 1/2)(1 - 1/3)

           = 36 x 1/2 x 2/3

           = 12

So there will be 12 numbers less than 36 and prime to it.  We require 
the numbers that have no factors in common with 36. We always count 1 
as being prime to every number.

So the 12 numbers that make up phi(36) are:

   1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35

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