# Math Help - [SOLVED] Number Theory:Euler phi function proofs

1. ## [SOLVED] Number Theory:Euler phi function proofs

1) show that if d does not equal m and d is a divisor of m then phi(d) divides phi(m).

2)show that for any positive integer m and n, phi(m)*phi(n)=phi(gcd(m,n))*phi(lcm(m,n)).

I just don't know where to begin so a push in the right direction would be greatly appreciated.

2. For $n = \Pi_i p_i^{\alpha_i}$, with $p_i\neq p_j, if\ i\neq j$ and are prime numbers

$\varphi(n) = \Pi_i(p_i-1)p_i^{\alpha_i - 1}$

3. Originally Posted by Willie_Trombone
1) show that if d does not equal m and d is a divisor of m then phi(d) divides phi(m).

2)show that for any positive integer m and n, phi(m)*phi(n)=phi(gcd(m,n))*phi(lcm(m,n)).

I just don't know where to begin so a push in the right direction would be greatly appreciated.
have you considered the formulas for $\varphi (n)$ for some integer $n$? the idea for the proofs should be evident after that

4. okay I got the first one but the second is still giving me trouble.

5. Originally Posted by Willie_Trombone
okay I got the first one but the second is still giving me trouble.
Show first that for m,n relatively prime $\varphi(mn) = \varphi(m)\varphi(n)$

Now, notice $\frac{m}{\textrm{gcd}(m,n)}$ and $n$ are relatively prime for any m,n and use the first result and the relation between gcd and lcm.

6. can $\phi(m/gcd(m,n))$ be expressed as $\phi(m)/\phi(gcd(m,n))$?

7. Originally Posted by Willie_Trombone
can $\phi(m/gcd(m,n))$ be expressed as $\phi(m)/\phi(gcd(m,n))$?

Yes, the division is well defined by the question 1) and you can use the fact that $\frac{m}{\mathrm{gcd}(m,n)}$ and $gcd(m,n)$ are relatively prime and distribute $\varphi$

8. thanks so much, I got it now.

9. Originally Posted by Willie_Trombone
thanks so much, I got it now.
good to know it helped