• Join over 1.2 million students every month
• Accelerate your learning by 29%
• Unlimited access from just £6.99 per month   # The totient function.

Extracts from this document...

Introduction

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: 1) ?(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 11 = 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 1 2 8 12 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: - 1) 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. ...read more.

Middle

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) ...read more.

Conclusion

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 ...read more.

The above preview is unformatted text

This student written piece of work is one of many that can be found in our GCSE Phi Function section.

## Found what you're looking for?

• Start learning 29% faster today
• 150,000+ documents available
• Just £6.99 a month

Not the one? Search for your essay title...
• Join over 1.2 million students every month
• Accelerate your learning by 29%
• Unlimited access from just £6.99 per month

# Related GCSE Phi Function essays

1. ## Investigating the Phi function

P = prime number Part 2 Why the phi function of a product is not always equal to the product of the phi functions of its components?

2. ## In this coursework I was asked to investigate the Phi Function (f) of a ...

(20); 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19; =8 ? (21); 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20; =12 ?

1. ## Identify and explain the rules and equations associated with the Phi function.

Investigation From the Phi table shown previously we can see that some clear patterns emerged. For example I noticed that for all the prime numbers the Phi is one less than the prime number. ?2=1=1 ?11=1 2 3 4 5 6 7 8 9 10=10 ?3=1 2=2 ?13=1 2 3

2. ## The Phi Function

= 12, also that ?(7) = 6 and ?(4) = 2. This shows that phi 28 is equal to phi 7 times phi 4 because the phi function of 7, which is 6 multiplied by the phi function of 4, which is 2 gives you the phi function of 28, which is 12.

1. ## Investigate the strength of a snail's mucus on different surfaces

the snail couldn't grip onto it, but if it had a texture it could. On the first surface, plastic, all the snails held on until 150�. We concluded that this is because the surface was a little rough, so that the snail could grip it and hold on to it.

2. ## The phi function.

(27) = 22 ? (3) = 2,1 ? (3) = 2 ? (9) ? (9) = 8, 7, 5, 4, 2, 1. ? (9) = 6 ? (27) = ? (3) x ? (9) 22 = 2 x 6 As the answer gotten from ?

1. ## Millikan's theory.

Proper functions are characterized by their normative character, not by their causal power or dispositional relations, and this for three reasons: 1. An item can do (and in fact usually does) many things that are not their proper function: for instance, the heart's proper function is to pump blood, but it also makes a rhythmic noise.

2. ## Describe Aristotle's teachings about the differences between the final cause and the other sorts ...

Discuss the strengths and weaknesses of Aristotle's views on causality There are many strengths and weaknesses about the views in which Aristotle has about causality. There have been many strengths in which have helped Christian Theology and other people to understand the concept of the world etc. • Over 160,000 pieces
of student written work
• Annotated by
experienced teachers
• Ideas and feedback to 