# [SOLVED] Number Theory:Euler phi function proofs

• Feb 19th 2009, 08: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, 09:27 PM
tah
For $\displaystyle n = \Pi_i p_i^{\alpha_i}$, with $\displaystyle p_i\neq p_j, if\ i\neq j$ and are prime numbers

$\displaystyle \varphi(n) = \Pi_i(p_i-1)p_i^{\alpha_i - 1}$
• Feb 19th 2009, 10: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 $\displaystyle \varphi (n)$ for some integer $\displaystyle n$? the idea for the proofs should be evident after that
• Feb 19th 2009, 11:21 PM
Willie_Trombone
okay I got the first one but the second is still giving me trouble.
• Feb 19th 2009, 11:34 PM
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 $\displaystyle \varphi(mn) = \varphi(m)\varphi(n)$

Now, notice $\displaystyle \frac{m}{\textrm{gcd}(m,n)}$ and $\displaystyle n$ are relatively prime for any m,n and use the first result and the relation between gcd and lcm.
• Feb 19th 2009, 11:56 PM
Willie_Trombone
can $\displaystyle \phi(m/gcd(m,n))$ be expressed as $\displaystyle \phi(m)/\phi(gcd(m,n))$?
• Feb 20th 2009, 12:17 AM
tah
Quote:

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

Yes, the division is well defined by the question 1) and you can use the fact that $\displaystyle \frac{m}{\mathrm{gcd}(m,n)}$ and $\displaystyle gcd(m,n)$ are relatively prime and distribute $\displaystyle \varphi$
• Feb 20th 2009, 12:37 AM
Willie_Trombone
thanks so much, I got it now.
• Feb 20th 2009, 12:39 AM
tah
Quote:

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

good to know it helped ;)