# Easy (but not to me) Modern Algebra Proof

#### c.francis

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 $$\equiv$$1 (mod p) (by Fermats Little Theorem) and an-1 $$\equiv$$1 (mod n) by definition. This implies that an-1 $$\equiv$$1 (mod p) because p/n.

So to finish can I just say that because ap-1 $$\equiv$$1 (mod p) and an-1 $$\equiv$$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.

Related Calculus and Beyond Homework Help News on Phys.org

#### c.francis

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$$\equiv$$1 (mod p), and by definition an-1$$\equiv$$1 (mod n). Then because p/n, an-1$$\equiv$$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

Homework Helper
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.

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