MATHS INVESTIGATION
THE PHI-FUNCTION
Luke Meredith 11 Yellow
The Problem
With any positive integer (n), the Phi Function of n is ?(n). The Phi number of n is the amount of numbers from 1to n (not including 1 or n) that do no share any common factors with n. If the two or more numbers share no common factor, then the numbers are co-prime.
So to put this into practice, the ?(8) = 4. This is because the positive integers less than 8, which have no common factors other than 1 with 8 are 1,3,5,7. This shows 4 of them, which is how the phi number is worked out.
Another example is ?(15) = 8. The numbers, which do not have any common factors with 8, from numbers 1 to 8 (excluding 1 and 8), are 1,2,4,6,7,8,11,13,14 = 8 of them.
What I am trying to find out is a formula, which will enable me to find the Phi of any number, without going through the painstakingly process of working out the phi for every number. However, you could say that it is not too hard working the phi out for numbers say 1 to a 100. Yet what would happen of you needed to know the phi of 30,041.
To complete my goal I will have to follow many different stages to finally work out the formula.
So the first stage I will do is to find out the numbers from say 1 to 36.
n
The
?(n)
The numbers with no common factors with n.
0
0.
2
.
3
2
-.2
4
2
,3.
5
4
-4.
6
2
,5.
7
6
-6.
8
4
,3,5,7,8.
9
6
,2,4,5,7,8.
0
4
,3,7,9.
1
0
-10.
2
4
,5,7,13.
3
2
-12.
4
6
,3,5,9,11,13.
5
8
,2,4,7,8,11,13,14.
6
8
,3,5,7,9,11,13,15.
7
6
-16.
8
6
,5,7,11,13,17,19.
9
8
-18.
20
8
1,3,7,911,13,17,19.
21
2
1,2,4,5,8,10,11,13,16,17,19,20.
22
0
,3,5,7,9,11,13,15,17,19,21.
23
22
-22.
24
8
,57,11,13,17,19,23.
25
20
,2,3,4,6,7,8,9,11,12,13,14,16,17,18,19,21,22,23,24.
26
2
,3,5,7,9,11,15,17,19,21,23,25.
27
8
,2,4,5,7,8,10,11,13,14,16,17,19,20,22,23,25,26.
28
2
,3,5,9,11,13,15,17,19,23,25,27.
29
28
-28.
30
8
,7,11,13,17,19,23,29.
31
30
-30.
32
6
,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31.
33
22
,2,4,5,7,8,10,12,13,14,16,17,19,20,22,23,25,26,28,29,31,32.
34
6
,3,5,7,9,11,13,15,19,21,23,25,27,29,31,33.
35
26
,2,3,4,6,8,9,11,12,13,14,16,17,18,19,21,22,23,24,26,27,29,31,32,33,34.
36
2
,5,7,11,13,17,19,23,25,29,31,35.
The ...
This is a preview of the whole essay
21
2
1,2,4,5,8,10,11,13,16,17,19,20.
22
0
,3,5,7,9,11,13,15,17,19,21.
23
22
-22.
24
8
,57,11,13,17,19,23.
25
20
,2,3,4,6,7,8,9,11,12,13,14,16,17,18,19,21,22,23,24.
26
2
,3,5,7,9,11,15,17,19,21,23,25.
27
8
,2,4,5,7,8,10,11,13,14,16,17,19,20,22,23,25,26.
28
2
,3,5,9,11,13,15,17,19,23,25,27.
29
28
-28.
30
8
,7,11,13,17,19,23,29.
31
30
-30.
32
6
,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31.
33
22
,2,4,5,7,8,10,12,13,14,16,17,19,20,22,23,25,26,28,29,31,32.
34
6
,3,5,7,9,11,13,15,19,21,23,25,27,29,31,33.
35
26
,2,3,4,6,8,9,11,12,13,14,16,17,18,19,21,22,23,24,26,27,29,31,32,33,34.
36
2
,5,7,11,13,17,19,23,25,29,31,35.
The blue numbers represent the prime numbers!
Once I had drawn the above Phi Function table, I could then look to see if there were any straightforward patterns. The pattern that I first came to notice is that some numbers had no common factors. This pattern is explained due to the fact that all the numbers this occurs with are prime numbers. The prime numbers are highlighted in the table. Now from this I decided to try and find an expression or formula, which I would be able to use to figure out the Phi of a larger prime number which, is not on my table.
When p is a prime number, the expression used for ?(p) is...
?(p) = p-1
This works in all cases, for example...
Prime number = p.
?(p) = p-1
?(23) = p-1 = 22
or,
?(17) = p-1 = 16 (These works as you can check by looking on the table).
After this I was asked to investigate weather or not ?(m x n) = ?(m) x ?(n).
To check this formula we took variation of ? to see if this equation worked.
Example 1.
)?(7 x 4)
? (28) = 12
2) ?7 x ? 4 same answer =
= 6 x 2 = 12
In this case, the equation works as the ?(28) is equal to ?7 x ?4. This is because they both come out with the same answer of 12.
Off course though we need to try this more than once as for all we know, this could be just a coincidence.
) ?(6 x4)
? (24) = 8
2) ?6 x ?4 not same =
2 x 2 = 4
In this case the equation failed to work. Below I have continued with this...
For the next two, I investigated I decided to take two numbers in each case that multiplied to 12.
Example 3.
) ?(6 x 2)
?12 = 4
2) ?6 x ?2 not same.
= 2 x 1 = 2
Example 4
) ?(4 x 3)
?12 = 4
3) ?4 x ?3 answers are the same. =
= 2 x 2 = 4
Once I had done this I realised that there must be a relationship between the two numbers for this equation to work. To carry on my investigation I implied the same tactic to the previous examples, in that both numbers I will choose will give a product (when multiplied) of 30.
Example 5
) ?(5 x 6)
?30 = 8
2) ?5 x ?6 answers are same =
= 4 x 2 = 8
Example 6
) ?(3 x 10)
?30 = 8
2) ?3 x ?10 answers are same =
=2 x 4 = 8
Example 7
) ?(2 x 15)
?30 = 8
2) ?2 x ?15 answers are same =
=1 x 8 = 8
In these last three cases the rule ? (n x m) = ?n x ?m has been proven correct. Then I looked at all the examples, which show that theory works and notices something vital towards figuring out in which cases this rule works in.
I noticed that the numbers which replaced n and m in the formula, had to be co-prime to each other. This is shown below
Example 1
The numbers 7 and 4 are co-prime to each other, as they share no common factor other than 1, and this worked.
Example 4
The numbers 3 and 4 are co-prime to each other, as they share no common factor other than 1, and this worked.
Example 5
The numbers 6 and 5 are co-prime to each other, as they share no common factor other than 1, and this worked.
Example 6
The numbers 3 and 10 are co-prime to each other, as they share no common factor other than 1, and this worked.
Example 7
The numbers 2 and 15 are co-prime to each other, as they share no common factor other than 1, and this worked.
Compared with...
Example 2
The numbers 4 and 6 are not co-prime as they share a common factor of 2. So therefore they did not work.
Example 3
The numbers 6 and 2 again are not co-prime as they share a common factor of 2.
So to sum this all up I can say that for this algebraic equation to work, you need two numbers, which are co-prime (no common factors)
Following this, to develop this study, I was asked to investigate, when p is a
Prime number; obtain a general rule for...
?p ?p ?p
To begin with we already know that the Phi of a prime number is simply p-1.
So
?(p ) = ?(p) x ?(p).
? (p) = (p-1)
?p = (p-1)
?2 = (2-1) = 1 x 2 =
?2 = (2-1) = 1 x 4 = 1 x 2
?2 = (2-1) = 1 x 8 = 1 x 2
?2 = (2-1) = 1 x 2
?(3) = 2
?(9) ?(3 ) = 2 x 3
?(27) ?(3 ) = 2 x 3
?(81) ?(3 ) = 2 x 3
?(3 ) = 2 x 3
So finally,
?p = (p-1)
?p = (p-1) x p
So the formula is (p-1) x p . However I feel we should still check this with a few randomly picked numbers.
So
? 5
= ? 25 = 20
Use of formula
? 5 = (5-1) x 5
4 x 5 = 20
This shows the formula does work.
The final task I was asked to investigate on this project was...
When p is prime obtain a general result for
? (p q )
And then to investigate ?(36)
?(200)
?(19600)
For this final part of my investigation I already know the formula for p . So q is going to the same as p because the numbers I intend to investigate will have to be split into to co-prime numbers which (when multiplied) give a product of the number I had to start with. For example I intend to investigate 36. However to do this I will need two co-prime numbers, which make 36 when multiplied. Which could be 9 and 4. Then I will have to use the formula for p , for both of the numbers. So to not get confused I would use p , for 9 and q , for 4. Finally after all that I would multiply the two remaining numbers together.
So I believe that for a general result ?(p q ) is ((p-1)p ) x ((q-1)q )
However for larger numbers I may have to split it up into more than two co-prime numbers. So the formula would then look like this...
((p-1)p ) x ((q-1)q ) x((r-1)r ).
Investigating 36.
? (36) = ?(9) x ?(4)
?3 x ? 2
(p-1)p x (q-1)q
Investigating 200
Investigating 19600.
Conclusion
My conclusion is that the rule for p works for everything. However, you need to adapt the formula for larger numbers to ensure that when you use it more than once in the same equation, you don't get confused, lost, or just come out with the wrong answer.
