• Support PF! Buy your school textbooks, materials and every day products via PF Here!

Easy (but not to me) Modern Algebra Proof

  • Thread starter c.francis
  • Start date
Hi everyone, I am hoping that someone can please give me some help with this homework problem.

1. Homework Statement
In n>2 is a Carmichael number and p/n is an odd prime, then show that gcd(p-1,n-1) >1


2. Homework Equations



3. The Attempt at a Solution
This is what I did, but I am not sure if its right:

Choose an a coprime to n and that does not divide p (2 will work because p is prime and carmichael numbers are odd).

Then ap-1 [tex]\equiv[/tex]1 (mod p) (by Fermats Little Theorem) and an-1 [tex]\equiv[/tex]1 (mod n) by definition. This implies that an-1 [tex]\equiv[/tex]1 (mod p) because p/n.

So to finish can I just say that because ap-1 [tex]\equiv[/tex]1 (mod p) and an-1 [tex]\equiv[/tex]1 (mod p) this implies that ap-1^some integer=an-1, and so (p-1)/(n-1)?


Any help would be greatly appreciated. Thanks guys.
 
How about this revised version, is this right?

Choose an a coprime to n and that does not divide p (2 will work because p is prime and carmichael numbers are odd).

Then by FLT, ap-1[tex]\equiv[/tex]1 (mod p), and by definition an-1[tex]\equiv[/tex]1 (mod n). Then because p/n, an-1[tex]\equiv[/tex]1 (mod p). Now this implies that the order of a mod p (which cannot be 1 because that would mean a is 1 and 1 isnt coprime to n and does divide p) divides both n-1 and p-1. Thus the gcd(n-1,p-1) is greater than 1.
 

Dick

Science Advisor
Homework Helper
26,258
618
I haven't really had a lot of time to think about this, but stop writing p/n instead of p|n. (i.e. p divides n). It confused me right off the bat, and may confuse other people. Who might know number theory a lot better than I do.
 

Related Threads for: Easy (but not to me) Modern Algebra Proof

Replies
5
Views
2K
  • Posted
Replies
4
Views
1K
Replies
22
Views
1K
Replies
5
Views
4K
  • Posted
Replies
3
Views
2K

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top