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

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