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.

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

Homework Equations

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

So to finish can I just say that because a^p-1 \equiv1 (mod p) and a^n-1 \equiv1 (mod p) this implies that a^{p-1^some integer}=a^n-1, and so (p-1)/(n-1)?


Any help would be greatly appreciated. Thanks guys.

 

[c.francis]

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, a^p-1\equiv1 (mod p), and by definition a^n-1\equiv1 (mod n). Then because p/n, a^n-1\equiv1 (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 isn't 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]

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.