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

  • Thread starter math_nerd
  • Start date
  • #1
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,260
619


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
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,260
619


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

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

Replies
3
Views
1K
Replies
7
Views
3K
Replies
4
Views
897
Replies
6
Views
4K
  • Last Post
Replies
19
Views
13K
Replies
8
Views
3K
  • Last Post
Replies
7
Views
1K
  • Last Post
Replies
6
Views
3K
Replies
3
Views
17K
  • Last Post
Replies
5
Views
3K
Top