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

### Formula for phi(n)

```Date: 05/09/2003 at 11:36:49
From: Jay Brandon
Subject: Phi Function

I am investigating the phi function and am stuck at one point.

Ultimately my aim is to get a formula for phi(n) where n is any
positive integer. I would appreciate it if you could explain in
detail how you get from the above to the phi(n) formula, and any
proofs that would help me understand along the way.

phi((m^p)(n^q))=((m^p)-(m^(p-1))((n^q)-(n^(q-1)), where p and q are
positive integers and m and n are prime numbers. I have also applied
this from the solution to phi(p^n) where p is a prime number and n is
a positive integer.
```

```
Date: 05/09/2003 at 12:46:50
From: Doctor Luis
Subject: Re: Phi Function

Hi Jay,

You pretty much have it. You know, from the Fundamental Theorem of
Arithmetic, that any number n can be decomposed into prime factors
(suppose it has k unique prime factors):

n = (p_1 ^ r_1) * (p_2 ^ r_2) * ... * (p_k ^ r_k)

where all the r_j > 0.

You also know that phi(n) is multiplicative, that is, for m,n
relatively prime, you have phi(m*n) = phi(m)*phi(n)

Applying this property of phi to phi(n), you get

phi(n) = phi(p_1 ^ r_1) * phi(p_2 ^ r_2) * ... * phi(p_k ^ r_k)

You have already worked out the formula for phi(p^r)

phi(p^r) = (p^r - p^(r-1)) = p^r(1 - 1/p)

Therefore,

phi(n) = (p_1^r_1)(1-1/p_1) * ... * (p_k^r_k)(1-1/p_k)

= (p_1^r_1 * ... * p_k^r_k) * ((1-1/p_1) * ... * (1-1/p_k))

phi(n) = n * (1 - 1/p_1)*(1 - 1/p_2)*...*(1 - 1/p_k)

So there you have it. A formula for phi(n). You just have to know how
many prime divisors it has.

You can find out more about phi(n), also known as the Totient
Function, or Euler's Phi Function, in Eric Weisstein's World of
Mathematics:

Totient Function
http://mathworld.wolfram.com/TotientFunction.html

I hope this helped. Let us know if you have any more questions.

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

```
Date: 05/09/2003 at 15:01:42
From: Jay Brandon
Subject: Phi Function

Can you go through why...

(p^r - p^(r-1)) = p^r(1 - 1/p)

I would really appreciate a step-by-step method.

```

```
Date: 05/09/2003 at 15:10:41
From: Doctor Luis
Subject: Re: Phi Function

Hi Jay,

I'll start from the right side of the equation:

p^r * (1 - 1/p) = p^r - (p^r / p)
= p^r - (p^r / p^1)
= p^r - p^(r-1)

Is it pretty clear now?

Alternatively, you could start from the left side,

p^r - p^(r-1) = p^r * 1 - p^r * p^(-1)
= p^r * (1 - p^(-1))
= p^r (1 - 1/p)

Does this help?

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

```
Date: 05/10/2003 at 11:30:49
From: Jay Brandon
Subject: Thank you (Phi Function)

I would like to thank all the doctors who have really been an
inspiration to me and do hope that they continue the great job that
they do. I am indebted to you guys. Once again, many thanks.
```
Associated Topics:
College 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