What is the proof for n|φ(a^n-1)?

  • Thread starter koukou
  • Start date
  • Tags
    Proof
In summary: For n=p1^k1 ... pr^kr-1, it is easy to see that φ(n)=φ(p1^k1)...φ(pr^kr). So φ(n)=φ(p1^k1)...φ(pr^kr+1). For n>p1^k1 ... pr^kr-1, let q=φ(n). Then q is a multiple of pi, and so φ(q)=φ(p1^k1)...φ(pr^kr+1). Therefore, φ(n)=φ(p1^k1)...φ(pr^kr+1).
  • #1
koukou
5
0
#1 a) If ex = x for some elements e,x belong to S, we say e is a left identity for x; similarly, if xe = x we say e is a right identity for x. Prove that an element is a left identity for one element of S if and only if it is a left identity for every element of S. Let S be a non-empty set with a binary operation which is associative and both left and right transitive

b) Prove that S has a unique identity element

c) Deduce that S is a group under the given binary operation



#2.Prove that n|φ(a^n-1) for every integer a≥2 and any positive integer n
 
Last edited:
Physics news on Phys.org
  • #2
How do you start? For (a), the second implication is immediate. Do you have other conditions for the operation? Is it associative? Do you have inverses? Is S the domain of a group?
 
  • #3
honestrosewater said:
How do you start? For (a), the second implication is immediate. Do you have other conditions for the operation? Is it associative? Do you have inverses? Is S the domain of a group?

there exists a such that and xs1=y s2x=y..
 
  • #4
koukou said:
there exists a such that and xs1=y s2x=y..
Part of your post got lost. Is this an axiom?

I missed your edit. What does it mean to be left and right transitive?
 
Last edited:
  • #5
honestrosewater said:
Part of your post got lost. Is this an axiom?

I missed your edit. What does it mean to be left and right transitive?

thank you
i have done this one

but still no idea to do this one


Prove that n|φ(a^n-1) for every integer a≥2 and any positive integer n
 
  • #6
koukou said:
Prove that n|φ(a^n-1) for every integer a≥2 and any positive integer n
What does that formula say? What do "|", "φ", and "φ(x)" mean?
 
  • #7
For 2, use the fact that:
φ(n)=(p1^k1-p1^(k1-1))...(pr^kr-pr^kr+1)
for n= p1^k1 ... pr^kr
for pi primes, and because a^n-1=(a-1)(a^n-1+...+1)
Now prove this theorem by induction.
 

1. How do I approach a math proof problem?

When approaching a math proof problem, it is important to carefully read and understand the given problem. Then, try to break the problem down into smaller, more manageable parts. Use any given information or known theorems to guide your steps in the proof. It is also helpful to work backwards from the desired conclusion to see what steps are needed to get there.

2. What are some common strategies for solving math proof problems?

Some common strategies for solving math proof problems include using counterexamples, proof by contradiction, proof by induction, and direct proof. Additionally, using diagrams or visual aids can often help in understanding and solving a proof.

3. How should I write up a math proof?

When writing up a math proof, it is important to clearly state the given information, the desired conclusion, and the steps taken to reach the conclusion. Use precise mathematical language and notation, and clearly label each step in the proof. It can also be helpful to include a diagram or visual aid to further explain the proof.

4. What should I do if I get stuck on a step in a math proof?

If you get stuck on a step in a math proof, try approaching the problem from a different angle or using a different strategy. It can also be helpful to take a break and come back to the problem with a fresh perspective. If needed, consult with a teacher or fellow mathematician for guidance.

5. How can I check if my math proof is correct?

To check if your math proof is correct, you can work backwards from the conclusion and make sure each step logically follows from the previous one. You can also double check any given information or known theorems used in the proof. It can also be helpful to have someone else review your proof for any errors or inconsistencies.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
Replies
0
Views
234
  • Set Theory, Logic, Probability, Statistics
Replies
9
Views
965
  • Calculus and Beyond Homework Help
Replies
1
Views
433
  • Calculus and Beyond Homework Help
Replies
1
Views
522
  • Set Theory, Logic, Probability, Statistics
Replies
20
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
996
  • Set Theory, Logic, Probability, Statistics
Replies
8
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
451
Back
Top