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

Investigation of the Phi Function

Extracts from this document...

Introduction

The Phi Function

Introduction

Also known as the totient function, the phi function Φ(n) is the number of positive integers smaller than n that are co-prime with n, where n is any positive integer. The term co-prime refers to numbers which do not share any common factors. In this case, it means all the positive integers smaller than n which do not have any of the same factors as n.

The number 1 is said to be co-prime with all positive integers because it is a prime number and is only divisible by itself.

One thing that needs to be understood before I start, however, is that to find out Φ(n), we need to know the factors of n, so that we can check if any of the positive integers smaller than it are divisible by those factors. However, even these factors of n must be divisible by its prime factors and larger numbers may have many factors but only a few prime factors. For example, the prime factor of 8 is 2 and all the factors of 8 (not including 1) i.e. 2, 4, and 8 are divisible by the prime factor 2. This means that it is easier to calculate Φ(n) by checking how many numbers less than n are divisible by its prime factors than by its factors.

Part 1

  1. The value of Φ(3) is 2.
...read more.

Middle

1 x 2 =2

No

Table showing values of Φ(mn) when m=2

m

n

Φ(mn)

Φ(m) x Φ(n)

Does Φ(mn)= Φ(m) x Φ(n)

3

2

Φ(6) = 2

2 x 1 =2

Yes

3

3

Φ(9) = 6

2 x 2 =4

No

3

4

Φ(12) = 4

2 x 2 =4

Yes

3

5

Φ(15) = 8

2 x 4 =8

Yes

3

6

Φ(18) = 6

2 x 2 =4

No

Table showing values of Φ(mn) when m=2

m

n

1

2

1

3

1

4

1

5

1

6

2

3

2

5

3

2

3

4

3

5

M

n

2

2

2

4

2

6

3

3

3

6

Since, the tables above do not show any clear link or pattern between m and n, I have now made two tables comparing the values of m and n that do work for the equation Φ(mn) = Φ(m) x Φ(n) on the right, and the values that don’t on the left. Maybe this will help me spot a relationship between them.

At a first look, it seems that for all the values of m and n that do work, one number is even and the other odd. However, there are some exceptions, which show that this cannot be the case. For example, 1 and 3, 1 and 5, and 3 and 5 are all combinations of m and n which are both odd and yet they fulfil the equation Φ(mn) = Φ(m) x Φ(n).

Another possible relationship between m and n is that one cannot be a multiple of another. This is because all the values of n in the table on the right are divisible by m, while none of the values of n in the table on the left are divisible by m. However, when I carried out some further investigation to prove this theory, I found various larger combinations where n is not divisible by m, so according to my theory, they should fulfil the equation Φ(mn) = Φ(m) x Φ(n),but they do not. Some of them are listed below:

m

n

Φ(mn)

Φ(m) x Φ(n)

Does Φ(mn)= Φ(m) x Φ(n)

4

6

Φ(24) = 8

2 x 2 =4

No

6

8

Φ(48) =16

2 x 4 =8

No

6

9

Φ(54) = 18

2 x 6 =6

No

...read more.

Conclusion

 pk-1, as is shown here:  

image01.png

In other words, m=, pk-1where m represents the number of multiples of p less than pk.

We know that pk-1 gives us m, which is the number of multiples of p smaller than then pk, because it represents the number of lots of p in pk. For example, 33 can also be written 3x3x3 which is 32 (9) lots of 3, so in other words, in 33 there are 33-1 or 32 multiples of 3.

Another thing we need to know, is the rule we learnt from Part 3, that Φ(xy) = Φ(x) x Φ(y), when x and y are co-prime. Applying this rule to Φ(pnqm) through substitution, if we say that x = pn and y = qm, then Φ(pnqm) = Φ(pn) x Φ(qm). The rule works because, as I explained earlier, the prime factors of pn and qm will be p and q respectively because they are both prime numbers, and so pn and qm will always be co-prime too, because they cannot have any common factors.

So we now know how to find Φ(pn) for any prime value of p by using the formula Φ(pn) = pn - pn-1 or Φ(qm) for any value of q using Φ(qm) = qm – qm-1. In this case, we must understand that n and m are used as constants instead of k, and that the meaning is one and the same. Using this information and the knowledge that Φ(pnqm) = Φ(pn) x Φ(qm), we can then find out Φ(pnqm) for any prime values of p and q.

...read more.

This student written piece of work is one of many that can be found in our AS and A Level Core & Pure Mathematics 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 AS and A Level Core & Pure Mathematics essays

  1. Marked by a teacher

    Estimate a consumption function for the UK economy explaining the economic theory and statistical ...

    3 star(s)

    Here R^2, the coefficient of determination, is the most commonly used of the quality of the fit of the equation to a data sample. The equation of R^2 is: R^2=(?(Y'i-Y*)2)/(?(Yi-Y*)^2), where Y'i are the predicted value from the derived equation, the Yi are the actually recorded values, Y* is the value of the mean.

  2. Sequences and series investigation

    3c = 26 n = 4 64a + 16b +4c = 64 = 16a + 4b + c = 16 4 To get rid of 'c' I will use this calculation; _16a + 4b + c = 16 4a + 2b + c = 4 12a + 2b = 12

  1. Maths - Investigate how many people can be carried in each type of vessel.

    (15X20-5X10)] We must then invert the corresponding signs of the integers using this shape: [ + - + ] [ - + - ] [ + - +] The final result is: [6 30 -120] [25 -40 -20 ] [-80 -40 250 ] We now know that A-1 is equal to the above result.

  2. Experimentally calculating the wavelength of an He-Ne laser by means of diffraction gratings

    6.86 x 10-7 � 2.57 x 10-9m 3rd Fringe x = 0.915 � 0.002m, uncertainty = 0.002/0.915 x 100 � 0.218% L = 4.410 � 0.002m, uncertainty = 0.002/4.410 x 100 � 0.045% 0.218% + 0.045% = 0.263% 0.263% of 6.92 x 10-7 � 1.82 x 10-9 6.92 x 10-7

  1. Mathematical Investigation

    Conjectures: (a) Transformations of the standard sine function y=sin (b�x) by different values of "b" stretches horizontally the original function y=sin (b�x)'s period by the inverse of the value "b". For instance in the function y=sin (2x), this graph's period per one complete cycle is shortened by inverse of 2, which is 1/2.

  2. Triminoes Investigation

    As the formula has 4 unknowns, I have to create 4 equations to find a, b, c, and d. f (1) = a x 1� + b x 1� + c x 1 + d = a + b + c + d = 4 - equation 1 f (2)

  1. Numerical Method (Maths Investigation)

    When x = 0.5 Table importing from Microsoft Excel: n Xn Xn+1 f(Xn) 1 0.50000 0.84090 1.75000 2 0.84090 0.92858 0.25473 3 0.92858 0.94755 -0.39294 4 0.94755 0.95150 -0.54719 5 0.95150 0.95232 -0.58000 6 0.95232 0.95249 -0.58682 7 0.95249 0.95253 -0.58823 8 0.95253 0.95253 -0.58852 9 0.95253 0.95254 -0.58858 10

  2. Fractals. In order to create a fractal, you will need to be acquainted ...

    As the Pascal’s triangle unfolds further down, it is found true that the resulting images will become the self-similar patterning characteristic of a fractal. There is, however, another way to make the SierpiÅksi Triangle by using the Lindenmayer System. Developed by biologist Aristied Lindenmayer in 1968, The L-system is a

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