# Thread: [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 $\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}$

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 $\displaystyle \varphi (n)$ for some integer $\displaystyle 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 $\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.

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

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

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

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

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.

,

,

,

,

,

,

,

,

,

,

# show phi(m)/phi(n) whenever m divides n

Click on a term to search for related topics.