The Phi FunctionDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2015 The Math Forum
http://mathforum.org/dr.math/