Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
High School Analysis

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search