Euler's phi function proof

**jzellt** · April 7th 2010, 08:08 PM

I will denote Eulers' phi function by the symbol &.
For example, &(10) = 10(1-1/2)(1-1/5) = 4
So, there are 4 integers which are less than or equal to 10 that are relativley prime to 10...

Show that if n>2, then &(n) is even.

Thanks in advance for any help...

**chiph588@** · April 7th 2010, 08:37 PM

Originally Posted by jzellt

I will denote Eulers' phi function by the symbol &.
For example, &(10) = 10(1-1/2)(1-1/5) = 4
So, there are 4 integers which are less than or equal to 10 that are relativley prime to 10...

Show that if n>2, then &(n) is even.

Thanks in advance for any help...

Suppose $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$ .

Then $\phi(n) = \prod_{i=1}^k p_i^{\alpha_i-1}(p_i-1)$ .

Now we are guaranteed to have at least one $p_j>2$ , which means $p_j-1$ is even. So we're done.

**Amer** · April 7th 2010, 08:46 PM

Originally Posted by jzellt

I will denote Eulers' phi function by the symbol &.
For example, &(10) = 10(1-1/2)(1-1/5) = 4
So, there are 4 integers which are less than or equal to 10 that are relativley prime to 10...

Show that if n>2, then &(n) is even.

Thanks in advance for any help...

suppose

$n = p_1^{r_1} \cdot p_2^{r_2} \cdot \cdot \cdot p_t^{r_t}$

r_i are exponents (powers for the primes)

$\phi(n) =\phi(p_1^{r_1} \cdot p_2^{r_2} \cdot \cdot \cdot p_t^{r_t})$

as you know
if p >2
$\phi(p^s) = p^{s-1}(p-1)$ but p-1 is even since p is odd so phi(p^s) is even for all p>2

so

$\phi(n) =\phi(p_1^{r_1} \cdot p_2^{r_2} \cdot \cdot \cdot p_t^{r_t})=\phi(p_1^{r_1})\cdot \phi(p_2^{r_2})\cdot \cdot \cdot \phi(p_t^{r_t})$

it a multiple of even numbers so n is even
if any of p_i's equal 2 then phi of this is even or power of 2

Thread: Euler's phi function proof

LinkBack

Thread Tools

Display

Euler's phi function proof

Similar Math Help Forum Discussions

[SOLVED] Euler function proof

Euler's totient function Proof

Euler Function Proof

Proof about Euler's φ-function

Euler phi function proof

Search Tags