# Phi function help

Printable View

• July 27th 2008, 08:40 PM
Pn0yS0ld13r
Phi function help
The Euler Phi function http://www.texify.com/img/%5CLARGE%5...phi%28n%29.gif counts the number of positive integers less than or equal to n, which are relatively prime to n.

Prove that if n is odd, then http://www.texify.com/img/%5CLARGE%5...phi%28n%29.gif, and if n is even, then http://www.texify.com/img/%5CLARGE%5...phi%28n%29.gif. I don't really know how to begin.

Here's my attempt to prove the first part, if n is odd, http://www.texify.com/img/%5CLARGE%5...phi%28n%29.gif.

Let the prime decomposition of n be http://www.texify.com/img/%5CLARGE%5...Ba_k%7D%7D.gif.

So,

http://www.texify.com/img/%5CLARGE%5...%28n%29%7D.gif

But it seems like this would work for all n, not just odd n, so my above proof must be wrong. (Headbang)
• July 27th 2008, 10:25 PM
ThePerfectHacker
Who tells thou that among the prime decomposition the p_i's are different from 2?
Instead decompose n>1 as n=2^m*p1^(a1)*...*pk^ak where m>=0
• July 28th 2008, 03:47 AM
PaulRS
See result 2(b) here
• July 28th 2008, 02:22 PM
Pn0yS0ld13r
Thank you guys for the reply. I think I got it now. :)
• July 28th 2008, 05:57 PM
NonCommAlg
recall that $\varphi(ab)=\varphi(a)\varphi(b),$ whenever $\gcd(a,b)=1.$ now if $n$ is odd, then $\gcd(2,n)=1.$ so $\varphi(2n)=\varphi(2)\varphi(n)=\varphi(n).$

if $n$ is even, then $n=2^km,$ for some $m, k \geq 1,$ with $\gcd(2,m)=1.$ therefore: $\varphi(2n)=\varphi(2^{k+1} m)=\varphi(2^{k+1}) \varphi(m)=$

$(2^{k+1} - 2^k)\varphi(m)=2(2^k - 2^{k-1})\varphi(m)=2\varphi(2^k)\varphi(m)=2\varphi(2^k m)=2\varphi(n). \ \ \ \square$