Maths Coursework
The totient function ?(n), also called Euler's totient function, is defined as the number of positive integers <= n which are relatively prime to (i.e., do not contain any factor in common with) n, where 1 is counted as being relatively prime to all numbers. Since a number less than or equal to and relatively prime to a given number is called a totative, the totient function ? (n) can be simply defined as the number of totatives of n. For example, there are eight totatives of 24 (1, 5, 7, 11, 13, 17, 19, and 23), so ?24=8. The totient function is implemented in Mathematics as EulerPhi [n]. In this part of the coursework will be investigating the phi function of:
) ?(p)
2) ?(m x n) = ?(m) x ?(n)
3) ?(pn)
4) Other methods of calculating the Phi values of an integer that I found from the net.
Find the value of:
(i) ?(3): = 2
3 = 1,2
The number 3 only has 2 positive co-prime integers they are the numbers 1 and 2.
(ii) ?(8): = 4
8 = 1,3,5,7
There are 4 positive co-prime integers for the number 8
(iii) ?(11): = 10
1 = 1,2,3,4,5,6,7,8,9,10
The number 11 has 10 positive co-prime integers, and they are shown above.
(iv) ?(24): = 8
24 = 1,5,7,11,13,17,19,23
The number 24 has 8 positive co-prime integers, and they are shown above.
Part 1
In this part I will try to investigate on ?(n). But before we can start we need to experiment on certain numbers. The experiment is shown below:
Even
? Of Number
2
4
20
42
84
2
8
2
24
Odd
? Of Number
3
7
23
51
79
2
6
22
32
78
Prime
? Of Number
3
7
37
61
419
2
6
36
60
418
Observations: -
) As you can see from the experiment on the above all the phi values of the numbers are all even except for the numbers, 1 and 2 which is shown on my tables. This is a good way of checking if your Phi answer is wrong or not. Even for even numbers the Phi value increases but this is not applicable to the even numbers that are the factors of 3 and 5. The Phi value also increases for odd numbers as the number increases but this does not include odd numbers.
2) Another common sequence that I found was that for all the Phi values of the prime numbers, the Phi value was one less than that number.
Eg: ?7= 6
This means that we can say:
?Prime (n) = n - 1
This formula is true for prime numbers because they have only 1 as a common factor, therefore all the numbers less that (n) will be co-prime to it. Check: -
?(3) = 2
?(5) =4
?(23) =22
3) By looking at the different Phi values I've seen that there are formulas for calculating all types of numbers. For odd numbers I've seen that if you take any number and multiply it by two, then find the Phi value of hat answer you can find the Phi value that you desire. The formula is shown below-
?(n) = ?(2 x n)
Check: -
?(9)= 6
(My formula) 9 x 2= 18, ?18=6 (proved)
4) As mentioned above a formula also applies for even numbers as well. By using the same formula above all I did now was just divide the whole equation by two. That is-
?(n) = ?(2 x n) / 2
Check: -
?10 = 4
(My formula) ?10 = 10 x 2= 20, ?20=8, 8 / 2= 4 (proved)
5) By looking at my formulas I also discovered that all my formulas need the Phi values of other numbers at some point or another. This means that there is no certain formula to find the Phi value of a number without using the Phi values of other numbers.
As a further proof that the phi values don't increase as the number increases I drew a chart. As you can see the line keeps going up and down proving that as the number increases its phi value does not necessarily have to increase.
Part 2
In part one I discovered that the only definite answer for an integer was for prime numbers, by using the formula ?(p) = p - 1. Now another attribute that I would like to investigate is the ?(pn). To further prove that my calculations and theory about prime numbers are right I planned a table for the values of (n) and (n)² and their factors beginning with "n". the following is the table I made.
(n)
(n) ²
?(n) ²
Factors
2
4
2
2 x 1
3
9
6
3 x 2
4
6
8
4 x 2
5
25
20
5 x 4
6
36
2
6 x 2
7
49
42
7 x 6
8
64
32
8 x 4
9
81
54
9 x 6
0
00
40
0 ...
This is a preview of the whole essay
(n)
(n) ²
?(n) ²
Factors
2
4
2
2 x 1
3
9
6
3 x 2
4
6
8
4 x 2
5
25
20
5 x 4
6
36
2
6 x 2
7
49
42
7 x 6
8
64
32
8 x 4
9
81
54
9 x 6
0
00
40
0 x 4
As I was looking at this table I found a relative relation that was obvious fro prime numbers. It is not very clear so I will show the relation in another table that I made below. Since again I found a relationship concerning prime numbers I will continue my investigation using prime numbers as well.
?(p²)
P
P²
?(P²)
P x (P-1)
2
4
2
2 x 1
3
9
6
3 x 2
5
25
20
5 x 4
7
49
42
7 x 6
As you can see there is a pattern for ?n². They all follow a multiplying pattern of 1*2, 2*3, 3*4, 4*5, etc. This however is not applicable to other numbers like even numbers. For this reason I will continue my investigation using prime numbers to see if my theory figures out.
To find the formula I used simultaneous equations in the form of y=ax²+bx+c.
First take the numbers p and ?(p²) from the table. I took three small numbers so that they are not difficult to calculate.
x, y
(2,2)
(3,6)
(5,20)
y=ax²+bx+c
2=4a+2b+c .......A
6=9a+3b+c .......B
20=25a+5b+c ....C
2=4a+2b+c .......D
6=9a+3b+c ......E
2=4a+2b (*3)
6=9a+3b (*2)
6=12a+6b
2=18a+6b
-6=-6a
Therefore a=1
Substitute a=1 in equation E
6=9+3b
-3=3b
b= -1
Substitute a=1, b= -1 in equation A
2=4-2+c
Therefore c=0
So y= x²-x
?p= p²-p
We rearrange it ?(p)² = p(p - 1) (Proved)
As you can see from above I have found a formula that is applicable to all of ?(p²).
Check:
All the Phi values below are compared to the table that I found from the Internet, which is shown in Part 1.
Eg 1) ?(23²) = 23(23 - 1) = 506
?(529) = 506 (true)
Eg 2) ?(2)² = 2(2 - 1)
?(4) = 2 (true)
Eg 3) ?(11)² = 11(11 - 1) = 110
?(121) = 110 (true)
I will also try to do this with other power values as well, as shown below.
?(p³)
All the Phi values below are compared to the table that I found from the Internet, which is shown in Part 1.
(p)
(p)³
?(p)³
Factors
2
8
4
2 x 2
3
27
8
3 x 6
5
25
00
5 x 20
7
343
294
7 x 42
Once again there only seems to be a factor relationship with prim numbers only. For this reason I will continue my investigation using prime numbers to see if my theory figures out
I wasn't sure but I came up using the previous formula and it worked. I only changed its order by adding another (p).
?(p)³ = p x ?(p)²
That is ?(p)³ = p x p(p - 1)
This could also be proved logically as the cube of a prime number will only have factors divisible by the prime number itself. Therefore we can say that: ?(p)³ = p³ - p² which is equivalent to p x p(p - 1)
Check: -
Eg 1) ?(3)³ = 3 x 3(3 - 1) = 18
?(27) = 18
Eg 2) ?(5)³ = 5 x 5(5 - 1) = 100
?(125) = 100
Now I'll investigate on ?(p4).
All the Phi values below are compared to the table that I found from the Internet, which is shown in Part 1.
(p)
(p) 4
?(p)4
Factors
2
6
8
2 x 4
3
81
54
3 x 18
5
625
500
5 x 100
Here I came up with the formula ?(p) 4 = p x ?(p)³ i.e. ?(p) 4 = p x p x p(p -1).
This is equivalent to ?(p) 4 = p4 - p³.
Logically the prime number to the power of four will be only divisible by the multiples of the prime number itself. This is applicable to all prime numbers in fact. Thus the Phi value of the prime number to the power of four will be equal to the prime number to the power of four minus the prime number to the power of 4 divided by the prime number itself.
That is p4 minus p³.
Check: -
Eg 1) ?(2) 4 =2 x 2 x 2(2 - 1) = 8
?(16) = 8
?(2) 4 = 2 x 2 x 2(2 - 1) (true)
Eg 2) ?(5) 4 =5 x 5 x 5(5 - 1) = 500
?(625) = 500 (true)
After investigating and proving the ?(p), ?(p)², ?(p)³ and ?(p)4 the following are the found observations and my conclusion to this section:
?(p) = (p - 1)
?(p)² = p (p - 1)
?(p)³ = p² (p - 1)
?(p) 4 = p³ (p - 1)
Thus I come to a final conclusion for all these formulas that:
?(p) n = p n - 1 ( ?(p) )
That is ?(p) n = p n - 1 (p - 1)
Part 2
Check That:
) ?(7 x 4) = ?(7) x ?(4)
Ans) ?(28) = 12
?(7) = 6
?(4) = 2
6 x 2 = 12
Therefore ?(7 x 4) = ?(7) x ?(4)
2) ?(6 x 4) = ?(6) x ?(4)
Ans) ?(24) = 8
?(6) = 2
?(4) = 2
2 x 2 = 4
Therefore ?(6 x 4) = ?(6) x ?(4)
As you can see from the equations form above there is another relationship that applies to the Phi function. The equation ?(m x n) = ?(m) x ?(n) tells us that when two numbers "m, n" are multiplied together and the phi value is found-will get you the same answer as finding the Phi value of "m" and "n" separately and then multiplying. Now what I am going to investigate is to see that this formula agrees with all the numbers. And if it doesn't explain why it cannot be so. Earlier I saw that there is a particular relationship with prime numbers and its Phi values. As I said earlier this function might also be related somehow to prime numbers.
The next few pages I will be performing certain investigation with a combination of numbers that will show me if my theory is right or wrong. I tend to make use of the following combinations to investigate: -
) Even, Even
2) Odd, Odd
3) Even, Odd
4) Even, Prime
5) Prime, Prime
6) Odd, Prime
For each of these combinations I will give three examples that will show me the answers to the questions: -
Q1: Why doesn't this formula work with all numbers?
Q2: Does it apply to prime numbers?
Q3: Are there any other relations?
Even, Even
?(2 x 4) = ?(2) x ?(4)
Ans)?(8) = 4
?(2) = 1
?(4) = 2
2 x 1 = 2
Therefore ?(2 x 4) = ?(2) x ?(4) (False)
?(10 x 20) = ?(10) x ?(20)
Ans)?(200) = 80
?(10) = 4
?(20) = 8
4 x 8 = 32
Therefore ?(10 x 20) = ?(10) x ?(20) (False)
?(40 x 2) = ?(40) x ?(2)
Ans)?(80) = 32
?(40) = 16
?(2) = 1
16 x 1 = 16
Therefore ?(40 x 2) = ?(40) x ?(2) (False)
As you can see there are absolutely no relations whatsoever with two even numbers, big or small.
Even, Prime
?(2 x 3) = ?(2) x ?(3)
Ans)?(6) = 2
?(2) = 1
?(3) = 2
2 x 1 = 2
Therefore ?(2 x 3) = ?(2) x ?(3) (True)
?(10 x 7) = ?(10) x ?(7)
Ans)?(70) = 24
?(10) = 4
?(7) = 6
6 x 4 = 24
Therefore ?(10 x 7) = ?(10) x ?(7) (True)
?(42 x 13) = ?(42) x ?(13)
Ans)?(546) = 144
?(42) = 12
?(13) = 12
12 x 12 = 144
Therefore ?(42 x 13) = ?(42) x ?(13) (True)
The equation seems to apply to Prime and Even numbers fully.
Even, Odd
?(2 x 3) = ?(2) x ?(3)
Ans)?(6) = 2
?(2) = 1
?(3) = 2
2 x 1 = 2
Therefore ?(2 x 3) = ?(2) x ?(3) (True)
?(20 x 21) = ?(20) x ?(21)
Ans)?(420) = 96
?(20) = 8
?(21) = 12
12 x 8 = 96
Therefore ?(20 x 21) = ?(20) x ?(21) (True)
?(10 x 15) = ?(10) x ?(15)
Ans)?(150) = 40
?(10) = 4
?(15) = 8
8 x 4 = 32
Therefore ?(10 x 15) = ?(10) x ?(15) (False)
One thing that I have noticed with Even and Odd numbers is that if you take two consecutive numbers like 2,3 or 4,5 or 100,101, etc. the ?(m x n) = ?(m) x ?(n). But if we take random numbers like 10, 15 then ?(m x n) = ?(m) x ?(n).
Odd, Odd
?(3 x 7) = ?(3) x ?(7)
Ans)?(21) = 12
?(3) = 2
?(7) = 6
6 x 2 = 12
Therefore ?(3 x 7) = ?(3) x ?(7) (True)
?(15 x 3) = ?(15) x ?(3)
Ans)?(45) = 24
?(15) = 8
?(3) = 2
8 x 2 = 16
Therefore ?(15 x 3) = ?(15) x ?(3) (False)
?(9 x 9) = ?(9) x ?(9)
Ans) ?(81) = 54
?(9) = 6
?(9) = 6
6 x 6 = 36
Therefore ?(9 x 9) = ?(9) x ?(9) (False)
For Odd, Odd this formula does not apply.
Odd, Prime
?(3 x 7) = ?(3) x ?(7)
Ans)?(21) = 12
?(3) = 2
?(7) = 6
6 x 2 = 12
Therefore ?(3 x 7) = ?(3) x ?(7) (True)
?(9 x 13) = ?(9) x ?(13)
Ans)?(117) = 72
?(9) = 6
?(13) = 12
6 x 12 = 72
Therefore ?(9 x 13) = ?(9) x ?(13) (True)
?(15 x 19) = ?(15) x ?(19)
Ans)?(285) = 144
?(15) = 8
?(19) = 18
8 x 18 = 144
Therefore ?(15 x 19) = ?(15) x ?(19) (True)
The rule as you can see applies to Even, Odd
Prime, Prime
?(3 x 7) = ?(3) x ?(7)
Ans)?(21) = 12
?(3) = 2
?(7) = 6
6 x 2 = 12
Therefore ?(3 x 7) = ?(3) x ?(7) (True)
?(11 x 23) = ?(11) x ?(23)
Ans)?(253) = 220
?(11) = 10
?(23) = 22
22 x 10 = 220
Therefore ?(11 x 23) = ?(11) x ?(23) (True)
?(7 x 7) = ?(7) x ?(7)
Ans)?(49) = 42
?(7) = 6
?(7) = 6
6 x 6 = 36
Therefore ?(7 x 7) =?(7) x ?(7) (False)
After investigating the situations I had some surprises when I came to my conclusion. Prime, Prime combinations will always be true, that is ?(m x n) = ?(m) x ?(n), provided that the prime numbers are not the same. The formula also applied to a Prime, Even and Prime, Odd combinations also but the numbers had to be different. For example "2" is both an even and prime, but it won't apply to the formula if it is used to apply for both "m" and "n". Therefore I come to the conclusion that ?(m x n) = ?(m) x ?(n): -
) Only for the combinations "Even, Prime" and "Prime, Prime"
2) If the same number is not used to replace both "m and n"
Observations: -
The following are the summary of results that I found in this part of my investigation.
The Formula
Combinations
True or False
Is ?(m x n) = ?(m) x ?(n)
Is ?(m x n) = ?(m) x ?(n)
Is ?(m x n) = ?(m) x ?(n)
Is ?(m x n) = ?(m) x ?(n)
Is ?(m x n) = ?(m) x ?(n)
Is ?(m x n) = ?(m) x ?(n)
m, n (Even, Even)
m, n (Odd, Odd)
m, n (Even, Odd)
m, n (Even, Prime)
m, n (Prime, Prime)
m, n (Odd, Prime)
False
False
False
True
True
True
Part 3
Now that I have found two methods of achieving the Phi of a prime number, I will try to combine these two formulas together to find a new one, which will be used to find the Phi value of any number by breaking it up into its prime factors.
In part one I found that:
?(p) n = p n - 1 (p - 1) where "p" represents any prime integer, and "n' is any positive integer.
In the second part of my coursework I found that:
?(n x m) = ?(n) x ?(m) where n, m are positive, co prime integers.
As an extension to the result, which I got, I will try now to find the phi of the following:
?( p m x q n x r o )
We can then write down the following general formula:
?(pn) = pn-1(p-1)
?(qm) = qm-1(q-1)
?(ro) = ro-1(r-1)
Therefore ?( p n x q m ) = p n - 1 (p - 1) x ? qm-1( q - 1 )
Check: -
?(100) = ( 2² x 5²)
4 x 25 = 100 (true)
?(72) = (2³ x 3²)
8 x 9 = 72 (true)
From the previous results, we can solve ?(p) m and ?(q) n and ?(r) o by using the results which I have obtained in part one. ?(p) n = p n - 1 (p - 1), and since "p, q and r" are co-prime because they are prime numbers- p ? q ? r. Therefore I come to the conclusion that: ?(p x q x r) = ?(p) x ?(q) x ?(r). To justify this formula I will use the rectangle method.
We color a number red if it is co prime with "m" and blue if it is co prime with "n". The color will be purple if the number is co prime with m and also with n, equivalently co prime with "mn". There will be ?(m) red columns. Why this always happens is because when you divide the numbers in the row by "m", each row contains the remainders 1, 2, ..., (m-1), 0 in this order, so you get ?(m) red columns. If "m" and "n" are co prime each column will contain exactly ?(n) blue numbers so there will be ?(m) x ?(n) colored purple. Again this happens because when you divide the numbers by "n" you see that each column contains all the possible remainders. These remainders however do not occur in the same order in each column so we will not get entirely blue rows. If "m" and "n" are not co prime then the number of blue numbers in a column will not be ?(n) so the result is not true. To prove this I used an example:
m = 5
n = 2
Example ?(5?2)
2 3 4 5
6 7 8 9 10
As you can see there are "4" numbers that are co prime with "m", "2" numbers that are co prime with "n", and "4" numbers that are co prime with both "m &n". Since:
? (abc) = ? (a) x ? (b) x ? (c), therefore
? (10) = 4 Proved
We can extend the formula as stated previously, provided all the numbers are co-prime to each other, ? (a x b x c x d...) = ? (a) x ? (b) x ? (c) x ? (d)...
Eg:
?(8x7x5x3) = ?(840) = 192
?(8) = 4
?(7) = 6
?(5) = 4
?(3) = 2
?(8) x ?(7) x ?(5) x ?(3) x = 4x6x4x2 =192
So now we know that I have understood the concept and proved that
? (a x b x c x d...) = ? (a) x ? (b) x ? (c) x ? (d)... we can go further in our investigation and show the result for:
?( p m x q n x r o )
?( p n ) = p n - 1 ( p - 1 )
? (q m) = q m - 1 ( q - 1)
? ( r o ) = r o - 1 ( r - 1)
Therefore ?(p n x q m x r o ) = p n - 1 (p - 1) x qm - 1( q - 1 ) x r o - 1( r - 1)
So we can say that it is shown that if n has prime factorization into distinct primes n = p 1 a . . .
p k r , then ?(n) = p 1 a - 1 ( p 1 - 1 ) . . . .p k r - 1 ( p k - 1 )
Further Investigation
Now that I had understood Euler's Phi function I tried to search the net to come up with other alternatives to finding the Phi value of a number.
First express the number N in its prime factors in the form:
n = ap bq cr ... 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:
How this formula is achieved is pretty obvious. Lets take the example of ?(200)
Listing 200 in the form of its prime numbers we get:
23? 52
2 200
2 100
2 50
5 25
5 5
1
By dividing 200 by 2 we get 100
By diving 100 by 200 we get1/2
This tells us that half the numbers from 1 to 200 will have numbers that go by 2 and 200 together.
When we divide 200 by 5 we get 40
Dividing 40 by 200 we get 1/5
This again tells us that 1/5 of the numbers are common to both 200 and 5.
Therefore to find the remaining numbers that do not go by 2 or 5 we minus 1 from 1/2 and 1 from 1/5 and multiply by 200 to find the remaining numbers that are co-prime to 200. So the formula we arrive at is:
To check the formula I will try out a sum:
?(n) = n(1-1/a)(1-1/b)....
?(2442) = 2442(1-1/2)(1-1/3)(1-1/11)(1-1/37)
= 2442(0.5)(0.6)(0.90)(0.972)
?(2442) = 720
?(a) = ?(n) x ?(m) x ?(p) x ?(q)
?(2442) = ?(2) x ?(3) x ?(11) x ?(37)
=1 x 2 x 10 x 36 = 720 Proved
Mathematical Induction
Another way of finding the Phi value of any number is Fermat's Little Theorem. Euler published a surprisingly elementary proof, in 1736, simply using mathematical induction on the natural number a. This formula I found in a website. The address is shown below:
www.mathworld.wolfram.com
Fermat's Little Theorem
ap = a x modp
Proof
For a positive integer "n", Euler defined ?(n) to be the number of integers 1 and "n". For example ?4 = 2. Clearly, if "p" is a prime then ?p = p - 1, and it can be proved that
,
Where p1, p2, pr are the distinct prime factors of n. Using this result, Euler generalized Fermat's Little Theorem by proving that if "a " and "m" are relative prime where "p" is a prime number and "a" a natural number. Then "m" divides x?m - 1.
That is, if (a, m) = 1 then
x?m =(mod m) This is now known as Euler's Theorem
This fails to work for all n composite because the binomial expansion of (x+1)m does not have inner terms that always divide n.
Eg 1) 27 = 3³ (1 x 3, 2 x 3, 3 x 3 ....9 x 3) = 33-1 x 3
Eg 2) 16 = 24 (1 x 2, 2 x 2, 3 x 2...8 x 2) = 24-1 x 2
