[SOLVED] Number Theory:Euler phi function proofs

**Willie_Trombone** · February 19th 2009, 08:23 PM

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** · February 19th 2009, 09:27 PM

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

**Jhevon** · February 19th 2009, 10:11 PM

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

**Willie_Trombone** · February 19th 2009, 11:21 PM

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

**tah** · February 19th 2009, 11:34 PM

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.

**Willie_Trombone** · February 19th 2009, 11:56 PM

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

**tah** · February 20th 2009, 12:17 AM

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$

**Willie_Trombone** · February 20th 2009, 12:37 AM

thanks so much, I got it now.

**tah** · February 20th 2009, 12:39 AM

Originally Posted by Willie_Trombone

thanks so much, I got it now.

good to know it helped

Thread: [SOLVED] Number Theory:Euler phi function proofs

LinkBack

Thread Tools

Display

[SOLVED] Number Theory:Euler phi function proofs

Similar Math Help Forum Discussions

Euler's Φ Function Proofs

Graph Theory - To Euler or not to Euler? With attempted working.

σ number theory proofs?

Number theory integer proofs

[SOLVED] GCD Proof: Elem. Number Theory

Search Tags