# [SOLVED] Number Theory:Euler phi function proofs

• Feb 19th 2009, 09:23 PM
Willie_Trombone
[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.
• Feb 19th 2009, 10:27 PM
tah
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}$
• Feb 19th 2009, 11:11 PM
Jhevon
Quote:

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
• Feb 20th 2009, 12:21 AM
Willie_Trombone
okay I got the first one but the second is still giving me trouble.
• Feb 20th 2009, 12:34 AM
tah
Quote:

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.
• Feb 20th 2009, 12:56 AM
Willie_Trombone
can $\phi(m/gcd(m,n))$ be expressed as $\phi(m)/\phi(gcd(m,n))$?
• Feb 20th 2009, 01:17 AM
tah
Quote:

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$
• Feb 20th 2009, 01:37 AM
Willie_Trombone
thanks so much, I got it now.
• Feb 20th 2009, 01:39 AM
tah
Quote:

Originally Posted by Willie_Trombone
thanks so much, I got it now.

good to know it helped ;)