Investigation of the Phi Function

Authors Avatar

The Phi Function


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. This is because 3 is a prime number, so its prime factor is naturally 3 and it cannot share a factor with any of the numbers smaller than it. In this case, 1 and 2 are the only numbers smaller than 3 and they are both co-prime with 3, so the value of Φ(3) is 2, because there are two numbers (1 and 2) that are co-prime with 3.

  1. The value of Φ(8) is 4, because the prime factor of 8 is 2 and1, 3, 5 and 7 are the only four positive integers less than 8 which do not have 2 as a factor.
Join now!

  1. Φ(11) = 10, because again, 11 is a prime number and, so, cannot be co-prime with any of the numbers smaller than it. This Φ(11) = 11-1 =10

  1. Φ(24) = 8. This is because the prime factors of 24 are 2 and 3, and there are 8 numbers i.e. 1, 5, 7, 11, 13, 17, 19 and 23, which are not divisible by 2 or 3, so all of them are co-prime with 24.

  1. Φ(18) = {1, 5, 7, 11, 13, 17} = 6
  2. Φ(41) = 40, because it is a ...

This is a preview of the whole essay