The Phi(ϕ) Function

Phi Function is define as the number of positive integers less than or equal to and coprime to the number. The other name is Euler’s Totient Function.

The application of this function is used to finding the remainders of large numbers, last digits of a large number, and more to be found.

Coprime numbers – these are pairs or set of numbers that don’t have a common divisor. Example are {3,5}, {2,3,7}, {12,7}. Pairs that is not coprime are {3,6}, {12,9}, {20,15}.

Formula:

Given n=a^xb^yc^x\ldots,   then

Phi(\varphi) n=n(1-\displaystyle\frac{1}{a})(1-\displaystyle\frac{1}{b})(1-\displaystyle\frac{1}{c})\ldots

 

n,a,b,c,x,y,z  are all positive intergers.

 

To test the formula, let’s try the obvious one.

Worked Problem 1:

How many positive integers less than or equal to and co-prime to 12?

Solution:

Listing all numbers that satisfy this condition we have 1,5,7,11. There are four positive integers less than or equal to and co-prime to 12.

Using the ϕ function we have,

12=2^2\cdot 3

\varphi n=n(1-\displaystyle\frac{1}{a})(1-\displaystyle\frac{1}{b})(1-\displaystyle\frac{1}{c})\ldots

\varphi 12=12(1-\displaystyle\frac{1}{2})((1-\displaystyle\frac{1}{3})

\varphi 12=12(\displaystyle\frac{1}{2})(\displaystyle\frac{2}{3})

\varphi 12=4

The formula satisfies the answer. This means that we can rely on this to calculate same problem with large numbers without exhausting our time to count them individually.

 

Worked Problem 2:

Find the number of positive integers less than or equal to and shares no common divisor with 2016.

Solution:

This problem is just exactly the same as the definition of ϕ function.

2016=2^5\cdot 3^2\cdot 7

Phi(\varphi) n=n(1-\displaystyle\frac{1}{a})(1-\displaystyle\frac{1}{b})(1-\displaystyle\frac{1}{c})\ldots

\varphi 2016=2016(1-\displaystyle\frac{1}{2})(1-\displaystyle\frac{1}{3})(1-\displaystyle\frac{1}{7})

Phi(\varphi) 2016=576

Worked Problem 3:

Find the number positive integers less than or equal to and co-prime to 390.

Solution:

390=2\cdot 3\cdot 5\cdot 13

\varphi 390=390(1-\displaystyle\frac{1}{2})(1-\displaystyle\frac{1}{3})(1-\displaystyle\frac{1}{5})(1-\displaystyle\frac{1}{3})

\varphi 390=96

You may also like...

Leave a Reply

Your email address will not be published.

Protected by WP Anti Spam