Proving the Euler Phi Equation Divisible by 2: A Step-by-Step Guide

[math_nerd]

Prove that the Euler phi equation is always divisible by 2. If n > 2.?
I don't understand how this proof works:

I think I need to show that the inverse of a and a are both generated by the same group. Therefore, there are at least 2 elements that generate all other elements in the group. I'm stumped.

Please give a thorough explanation of steps.

 

[Dick]

You don't need to generate any groups. Just look at the definition of the phi function. If a is coprime to n, what about n-a?

 

[math_nerd]

You don't need to generate any groups. Just look at the definition of the phi function. If a is coprime to n, what about n-a?

Yes, this statement works. But I don't understand what it means by gcd(a,n-a)=1 is also coprime...does this show that there are two numbers within the same set of number that are coprime,..?

 

[Dick]

Yes, this statement works. But I don't understand what it means by gcd(a,n-a)=1 is also coprime...does this show that there are two numbers within the same set of number that are coprime,..?

n-a doesn't have to be coprime to a. It's coprime to n if a is. The point is that coprimes to n come in pairs.

 

[math_nerd]

I see. Once I show that coprimes come in pairs, the Euler phi function for n>2:

a = n-a
So 2a = n
a = n/2
Which shows that two numbers are coprime to n. But does this adequately prove that this holds for n>2?

 

[Unit]

If p is a prime > 2, then φ(p) = p-1. Since p > 2, p is odd, and p-1 is even, thus φ(p) is divisible by 2.

Now supposing n is the product of some prime powers p₁ through p_r with exponents k₁ through k_r, you should be aware that $\varphi(n)=(p_1-1)p_1^{k_1-1} \times (p_2-1)p_2^{k_2-1} \cdots \times(p_r-1)p_r^{k_r-1}$. What can you say about the parity of this number?