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

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

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

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/