# [SOLVED] Number Theory:Euler phi function proofs

#### 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.

#### 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}$$

Willie_Trombone

#### Jhevon

MHF Helper
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

Willie_Trombone

#### Willie_Trombone

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

#### tah

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.

Willie_Trombone

#### Willie_Trombone

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

#### tah

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$$

Willie_Trombone

#### Willie_Trombone

thanks so much, I got it now.

#### frenzy

let m=12 and n=18. gcd(12,18)=6

(12/6) and 18 are not r.p.

12 and (18/6) are not r.p.

so in general m/gcd(m,n) and n are not r.p.