# Thread: Euler's phi function proof

1. ## Euler's phi function proof

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

2. 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 $\displaystyle n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$.

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

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

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

$\displaystyle 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)

$\displaystyle \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
$\displaystyle \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

$\displaystyle \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