The Phi Function Investigation
The Phi Function
For any positive integer n, the Phi Function ?(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.
Part 1 (a) Find the value of:
(I) ?(3) (ii) ?(8) (iii) ?(11) (iv) ?(24)
(b) Obtain the Phi-Function for at least 5 positive
integers of your own choice.
(a) (I) ?(3):
1
2 1,2
3 1,3
3 = 1,2
The number 3 only has 2 positive integers they are the numbers 1 and 2.
(ii) ?(8):
1
2 1,2
3 1,3
4 1,2,4
5 1,5
6 1,2,3,6
7 1,7
8 1,2,4,8
8 = 1,3,5,7
There are 4 positive integers for the number 8
(iii) ?(11):
1
2 1,2
3 1,3
4 1,2,4
5 1,5
6 1,2,3,6
7 1,7
8 1,2,4,8
9 1,3,9
0 1,2,5,10
1 1,11
1 = 1,2,3,4,5,6,7,8,9,10
The number 11 has 10 positive integers, they are shown above.
(iv) ?(24):
1
2 1,2
3 1,3
4 1,2,4
5 1,5
6 1,2,3,6
7 1,7
8 1,2,4,8
9 1,3,9
0 1,2,5,10
1 1,11
2 1,2,4,6,12
3 1,13
4 1,2,7,14
5 1,3,5,15
6 1,2,4,8,16
7 1,17
8 1,2,6,9,18
9 1,19
20 1,2,4,5,10,20
21 1,3,21
22 1,2,11,22
23 1,23
24 1,2,3,4,6,8,12,24
24 = 1,5,7,11,13,17,19,23
The number 24 has 8 positive integers, they are shown above.
(b) Obtain the Phi-Function for at least 5 positive integers of your own choice.
(I) ?(6):
1
2 1,2
3 1,3
4 1,2,4
5 1,5
6 1,2,3,6
6 = 1 and 5
The number 6 has 2 positive integers, they are shown above.
(ii) ?(10):
1
2 1,2
3 1,3
4 1,2,4
5 1,5
6 1,2,3,6
7 1,7
8 1,2,4,8
9 1,3,9
0 1,2,5,10
0 = 1,3,7,9
The number 10 has 4 positive integers, they are shown above.
(iii) ?(14):
1
2 1,2
3 1,3
4 1,2,4
5 1,5
6 1,2,3,6
7 7
8 1,2,4,8
9 1,3,9
0 1,2,5,10
1 1,11
2 1,2,3,4,6,12
3 1,13
4 1,2,7,14
4 = 1,3,5,9,11,13
The number 14 has 6 positive integers, they are shown above.
(iv) ?(16):
1
2 1,2
3 1,3
4 1,2,4
5 1,5
6 1,2,3,6
7 1,7
8 1,2,4,8
9 1,3,9
0 1,2,5,10
1 1,11
2 1,2,6,12
3 1,13
4 1,2,7,14
5 1,3,5,15
6 1,2,4,8,16
6 = 1,3,5,7,9,11,13,15
The number 16 has 8 positive integers, they are shown above.
(v) ?(28):
1
...
This is a preview of the whole essay
1 1,11
2 1,2,3,4,6,12
3 1,13
4 1,2,7,14
4 = 1,3,5,9,11,13
The number 14 has 6 positive integers, they are shown above.
(iv) ?(16):
1
2 1,2
3 1,3
4 1,2,4
5 1,5
6 1,2,3,6
7 1,7
8 1,2,4,8
9 1,3,9
0 1,2,5,10
1 1,11
2 1,2,6,12
3 1,13
4 1,2,7,14
5 1,3,5,15
6 1,2,4,8,16
6 = 1,3,5,7,9,11,13,15
The number 16 has 8 positive integers, they are shown above.
(v) ?(28):
1
2 1,2
3 1,3
4 1,2,4
5 1,5
6 1,2,3,6
7 1,7
8 1,2,4,8
9 1,3,9
0 1,2,5,10
1 1,11
2 1,2,6,12
3 1,13
4 1,2,7,14
5 1,3,5,15
6 1,2,4,8,16
7 1,17
8 1,2,3,6,9,18
9 1,19
20 1,2,4,5,10,20
21 1,3,7,21
22 1,2,11,22
23 1,23
24 1,2,3,4,6,8,12,24
25 1,5,25
26 1,2,13,26
27 1,3,27
28 1,2,4,7,14,28
28 = 1,3,5,9,11,13,15,17,19,23,25,27
The number 28 has 12 positive integers, they are shown above.
Part 2 (a) Check that
(I) ?(7 × 4) = ?(7) × ?(4)
?(28) = ?(7) × ?(4)
?(28):
1
2 1,2
3 1,3
4 1,2,4
5 1,5
6 1,2,3,6
7 1,7
8 1,2,4,8
9 1,3,9
0 1,2,5,10
1 1,11
2 1,2,6,12
3 1,13
4 1,2,7,14
5 1,3,5,15
6 1,2,4,8,16
7 1,17
8 1,2,6,9,18
9 1,19
20 1,2,5,10,20
21 1,3,7,21
22 1,2,11,22
23 1,23
24 1,2,3,4,6,8,12,24
25 1,5,25
26 1,2,13,26
27 1,3,27
28 1,2,4,7,14,28
28 = 1,3,5,9,11,13,15,17,19,23,25,27
The number 28 has 12 positive integers, they are shown above.
I have now shown that the number 28 has 12 positive integers so if the equation is correct when ?(7) and ?(4) are multiplied they should equal 12 positive integers.
?(7):
1
2 1,2
3 1,3
4 1,2,4
5 1,5
6 1,2,3,6
7 1,7
7 = 1,2,3,4,5,6
The number 7 has 6 positive integers, they are shown above.
?(4):
1
2 1,2
3 1,3
4 1,2,4
4 = 1 and 3
The number 4 only has 2 positive integers, they are shown above.
I have now found out that the number 28 has 12 integers. I have also found out that the number 7 has 6 integers and the number 4 has 2 integers. When these two numbers are multiplied they equal 12 as shown in the bow below.
(ii) Check that:
?(6 × 4) = ?(6) × ?(4)
?(24) = ?(6) × ?(4)
?(24):
1
2 1,2
3 1,3
4 1,2,4
5 1,5
6 1,2,3,6
7 1,7
8 1,2,4,8
9 1,3,9
0 1,2,5,10
1 1,11
2 1,2,6,12
3 1,13
4 1,2,7,14
5 1,3,5,15
6 1,2,4,8,16
7 1,17
8 1,2,6,9,18
9 1,19
20 1,2,4,5,10,20
21 1,3,21
22 1,2,11,22
23 1,23
24 1,2,3,4,6,8,12,24
24 = 1,5,7,11,13,17,19,23
The number 24 has 8 positive integers, they are shown above.
?(6):
1
2 1,2
3 1,3
4 1,2,4
5 1,5
6 1,2,3,6
6 = 1 and 5
The number 6 has 2 positive integers, they are shown above.
?(4):
1
2 1,2
3 1,3
4 1,2,4
4 = 1 and 3
The number 4 has 2 positive integers, they are shown above.
The number 24 has 8 positive integers and the numbers 6 and 4 each have 2 positive integers each. When they are multiplied together they equal 4. This does not equal 8 so the equation is correct as shown in the box below.
(b) Check whether or not ?(n × m) = ?(n) × ?(m) for at least two separate choices of n and m.
The first two choices I will use will consist of the number 3 for the letter n and the number 9 for the letter m.
?(3):
1
2 1,2
3 1,3
3 = 1 and 2
The number 3 has 2 positive integers, they are shown above.
?(9):
1
2 1,2
3 1,3
4 1,2,4
5 1,5
6 1,2,3,6
7 1,7
8 1,2,4,8
9 1,3,9
9 = 1,2,4,5,6,7
The number 9 has 6 positive integers, they are shown above.
?(27):
1
2 1,2
3 1,3
4 1,2,4
5 1,5
6 1,2,3,6
7 1,7
8 1,2,4,8
9 1,3,9
0 1,2,5,10
1 1,11
2 1,2,6,12
3 1,13
4 1,2,7,14
5 1,15
6 1,2,4,8,16
7 1,17
8 1,2,6,9,18
9 1,19
20 1,2,4,5,10,20
21 1,3,7,21
22 1,2,11,22
23 1,23
24 1,2,8,12,24
25 1,5,25
26 1,2,4,6,13,26
27 1,3,9,27
27 = 1,2,4,5,7,8,10,11,12,13,14,15,16,17,19,20,22,23,24,25,26,27
The number 27 has 22 positive integers, they are shown above.
The number 27 has 22 positive integers as shown on the previous page. The number 3 has 2 positive integers and the number 9 has 6 positive integers. These two numbers multiplied together do not equal 22 so this equation does not work.
Because the last two numbers that I tried in the equation shared common factors I will now try the opposite and use numbers that do not have common factors. I will use the numbers 3 and 7. I will use the number 3 for the letter n and the number 7 for the letter m as shown in the box below.
?(3):
1
2 1,2
3 1,3
3 = 1 and 2
The number 3 has 2 positive integers which are shown above.
?(7):
1
2 1,2
3 1,3
4 1,2,4
5 1,5
6 1,2,3,6
7 1,7
7 = 1,2,3,4,5,6
The number 7 has 6 positive integers they are shown above.
?(21):
1
2 1,2
3 1,3
4 1,2,4
5 1,5
6 1,2,3,6
7 1,7
8 1,2,4,8
9 1,9
0 1,2,5,10
1 1,11
2 1,2,3,6,12
3 1,13
4 1,2,7,14
5 1,15
6 1,2,8,16
7 1,17
8 1,2,3,6,9,18,27
9 1,19
20 1,2,4,5,10,20
21 1,3,7,21
21 = 1,2,4,5,8,10,11,13,16,17,19,20
The number 21 has 12 positive integers they are shown above.
The number 3 produced 2 positive integers and the number 7 produced 6 positive integers. When multiplied together this equalled the amount of positive integers the number 21 produced. (Which was coincidentally 12)
This shows that numbers that do not have common factors in common worked in the equation ?(n × m) = ?(n) × ?(m).
Part 3 In some cases
?(n × m) = ?(n) × ?(m) whilst in other cases this is not so.
Investigate this situation.
I found out in part 2 that the numbers that did not have common factors worked in the equation ?(n × m) = ?(n) × ?(m). I am now going to investigate this further showing some more examples of this theory. I will also look for any other patterns that may occur for this equation.
The two numbers I will use will be 4 for the letter n and 9 for the letter m. I have chose these two numbers as they do not have common factors.
?(4):
1
2 1,2
3 1,3
4 1,2,4
4 = 1 and 3
The number 4 has 2 positive integers, they are shown above.
?(4):
1
2 1,2
3 1,3
4 1,2,4
5 1,5
6 1,2,3,6
7 1,7
8 1,2,4,8
9 1,3,9
9 = 1,2,4,5,6,7,8
The number 9 has 7 positive integers, they are shown above.
?(36):
1
2 1,2
3 1,3
4 1,2,4
5 1,5
6 1,2,3,6
7 1,7
8 1,2,4,8
9 1,3,9
0 1,2,5,10
1 1,11
2 1,2,3,4,6,12
3 1,13
4 1,2,7,14,28
5 1,3,5,15
6 1,2,8,16
7 1,17
8 1,2,6,9,18
9 1,19
20 1,2,4,5,10,20
21 1,3,7,21
22 1,2,11,22
23 1,23
24 1,2,3,6,8,12,24
25 1,5,25
26 1,2,13,26
27 1,3,9,27
28 1,2,4,14,28
29 1,29
30 1,2,3,5,10,15,30
31 1,31
32 1,2,4,8,16,32
33 1,3,11,33
34 1,2,17,34
35 1,5,7,35
36 1,2,3,9,12,18,36
36 = 1,5,7,11,13,17,19,23,25,29,31,32,35,36
The number 36 has 14 positive integers, they are shown above.
The number 4 produced 2 positive integers and the number 9 produced 7 positive integers. When multiplied together this equalled the amount of positive integers the number 36 produced. (Which was coincidentally 14)
This is another example of the formula that states that:
"Numbers that do not have common factors work in the equation
?(n × m) = ?(n) × ?(m)"