• Join over 1.2 million students every month
  • Accelerate your learning by 29%
  • Unlimited access from just £6.99 per month
Page
  1. 1
    1
  2. 2
    2
  3. 3
    3
  4. 4
    4
  5. 5
    5
  6. 6
    6
  7. 7
    7
  8. 8
    8
  9. 9
    9
  10. 10
    10
  11. 11
    11
  12. 12
    12
  13. 13
    13
  14. 14
    14
  15. 15
    15
  16. 16
    16
  17. 17
    17
  18. 18
    18
  19. 19
    19
  20. 20
    20
  21. 21
    21
  22. 22
    22
  • Level: GCSE
  • Subject: Maths
  • Word count: 3982

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

See related essaysSee related essays

Related GCSE Phi Function essays

  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. Investigating the Phi function

    I also noticed that these phi numbers are powers of 2 [ 2 = 21, 4 = 22, 8 = 23, 16 = 24, 32 = 25] Example: (9) = 6 (15) = 8 (171) = 108 x2 x2 x2 (18)

  1. The Phi Function

    The table below is similar to the one above, but is for the phi function of 11. Integers Factors Does it fit into expression? Yes or No 1 1 yes 2 1,2 Yes 3 1,3 Yes 4 1,2,4 Yes 5 1,5 Yes 6 1,2,3,6 Yes 7 1,7 Yes 8 1,2,4,8

  2. 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.

  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. The phi function.

    (27) = 18 I noticed that the Phi of 3, 5, and 11, which are all prime numbers is themselves minus one. So when n is a prime number ? (n) = n - 1 PART 2. A) Check that: 1- ?

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

    Aristotle wrote about the different causes and about how different they are from each other, and without one no other cause can exist. This is another weakness. As it becomes clear that an efficient cause in one thing can also be the formal cause in another, so how I they are so different be the same thing?

  2. The Phi function.

    where n is any odd number. For example: ?(11) = 10. According to this rule the ?(22) should also be 10 and this is true. ?(13) = 12 and thus ?(26) is also 12. This has been proved. The next will be for even numbers. This is where n is an even number. Even (n) ?(n)

  • Over 160,000 pieces
    of student written work
  • Annotated by
    experienced teachers
  • Ideas and feedback to
    improve your own work