[SOLVED] Number Theory:Euler phi function proofs

Feb 2009
7
0
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

Feb 2009
51
8
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}\)
 
  • Like
Reactions: Willie_Trombone

Jhevon

MHF Helper
Feb 2007
11,681
4,225
New York, USA
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
 
  • Like
Reactions: Willie_Trombone

tah

Feb 2009
51
8
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.
 
  • Like
Reactions: Willie_Trombone
Feb 2009
7
0
can \(\displaystyle \phi(m/gcd(m,n))\) be expressed as \(\displaystyle \phi(m)/\phi(gcd(m,n))\)?
 

tah

Feb 2009
51
8
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\)
 
  • Like
Reactions: Willie_Trombone
Mar 2007
59
21
Planet Express
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.