Modern (abstract) Algebra: Prove that the Euler phi equation is always divisible by 2

  • Thread starter math_nerd
  • Start date
  • #1
math_nerd
22
0
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.
 

Answers and Replies

  • #2
Dick
Science Advisor
Homework Helper
26,263
620


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?
 
  • #3
math_nerd
22
0


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,..?
 
  • #4
Dick
Science Advisor
Homework Helper
26,263
620


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.
 
  • #5
math_nerd
22
0


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?
 
Last edited:
  • #6
Unit
182
0


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 p1 through pr with exponents k1 through kr, you should be aware that [itex]\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}[/itex]. What can you say about the parity of this number?
 
Last edited:

Suggested for: Modern (abstract) Algebra: Prove that the Euler phi equation is always divisible by 2

Replies
4
Views
416
Replies
20
Views
425
Replies
16
Views
572
Replies
18
Views
434
Replies
12
Views
600
Top