Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Properties of the Phi Function


Date: 01/19/99 at 14:06:27
From: Hugo Joyce
Subject: The 'PHI' function.

Dear Dr. Math,

Could you inform me of any possible links between Phi of a number and 
the number? For example I know that Phi of any prime number p can be 
found by subtracting 1 from the number: 

   Phi(p) = p - 1

We have also been given things like: Is phi(7*4) = phi(7)*phi(4) 
true or false?

Thank you,
Hugo


Date: 01/19/99 at 14:38:41
From: Doctor Rob
Subject: Re: The 'PHI' function.

Thanks for writing to Ask Dr. Math!

The things you need to know are:

(1) phi(n) is the number of integers x with 0 < x <= n such that
    GCD(x,n) = 1. This implies that if n > 1, phi(n) < n.

(2) If GCD(n,m) = 1, then phi(n*m) = phi(n)*phi(m).
    [This tells you that to compute phi(n) for any n, you need only
    be able to compute phi applied to prime powers.]

(3) If p is prime and k >= 2, then phi(p^k) = p*phi(p^[k-1]).
    [This tells you that to compute phi applied to prime powers,
    you need only compute phi applied to primes.]

(4) If p is prime, phi(p) = p - 1.
    [This is the last piece, telling you what phi(p) is.]

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/   
    
Associated Topics:
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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/