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