# Easy (but not to me) Modern Algebra Proof

1. Mar 24, 2009

### c.francis

Hi everyone, I am hoping that someone can please give me some help with this homework problem.

1. The problem statement, all variables and given/known data
In n>2 is a Carmichael number and p/n is an odd prime, then show that gcd(p-1,n-1) >1

2. Relevant 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.

2. Mar 24, 2009

### c.francis

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.