As we know the equation 𝑎x≡1 (𝑚od 𝑛) can be solve if and only if (𝑎,𝑛) =1, so 𝑎 and 𝑛 are relatively prime. So, knowing the elements relatively prime to another is somewhat important. Let us call 𝜙(𝑛) the number of positive elements less than 𝑛 that are relatively prime with 𝑛.Prove the next claims about 𝜙.

Question

As we know the equation 𝑎x≡1 (𝑚od 𝑛) can be solve if and only if (𝑎,𝑛) =1, so 𝑎 and 𝑛 are relatively prime. So, knowing the elements relatively prime to another is somewhat important. Let us call 𝜙(𝑛) the number of positive elements less than 𝑛 that are relatively prime with 𝑛.Prove the next claims about 𝜙. 
a.If p is prime, what is𝜙(𝑝)?
 b.If p is prime, what is 𝜙(𝑝^𝑛)? 
c.If p and q are prime, what is 𝜙(𝑝q)?

oobleck · Answer

if you google Euler's phi function, you can read about the properties of 𝜙(n)