Euler function (Phi) Problem

How to Solve:

if n is prime then number of relative prime from 1 upto n is n-1.

This is represented as phi function.

if n and m relatively prime then phi(mn)=phi(n)*phi(m). (proof given bellow as matrix representation of the 1 from mn)

The problem was solved by taking the number of relatively prime numbers as n.

Then dividing by the prime numbers (if divisible) n and subtracting the numbre of divisible numbers from result. (this removes all

the conjugated numbers from n)

Finally if there is any prime numbers left(that was checked in line if(n>1))

the divisible numbers were subtracted from result.

Related Theory:

1 The Euler Phi Function
This lecture is dedicated to the study of another multiplicative functions, the Euler phi
De nition 1.1. Let n  1 be an integer. Then we de ne the Euler phi function  by
(n) =the number of positive integers less than n that are relatively prime to n.
So let us do some examples.
Example 1.2. (1) = 1; (2) = 1; (3) = 2; (4) = 2; (5) = 4; (6) = 2; (15) = 8
The rst observation is how (n) behaves on the primes.
Observation 1. (n) = n


Proof. (n) = n


Leave a Reply

Your email address will not be published. Required fields are marked *