smithna1
Apr30-07, 09:52 PM
1. The problem statement, all variables and given/known data
For a homework exercise I had to first prove Wilson's Theorem, which I have solved; however, the second part is giving me trouble. I am to suppose that n>1 is not prime and Z*n is a cyclic group. I have allowed a1, a2, ..., a(phi(n)) be the elements in Z*n. I have to prove that a1*a2* ...*a(ϕ(n)) ≡ -1(mod n)
I am just looking for a push in the right direction if anyone could help. I believe I am supposed to go back to Wilson's Theorem, but I can't see the connection with composite order.
2. Relevant equations
3. The attempt at a solution
I realize that if n is composite then n = ab where 1 < a < b < n. Also, ((n-1)!, n) > a > 1 since a|(n-1)!. If I can get (n-1)! ≡ -1 (mod p), then it is clear that (n-1)! does have a multiplicative inverse mod n, which is -1. My problem is that that is mod p... please help.
For a homework exercise I had to first prove Wilson's Theorem, which I have solved; however, the second part is giving me trouble. I am to suppose that n>1 is not prime and Z*n is a cyclic group. I have allowed a1, a2, ..., a(phi(n)) be the elements in Z*n. I have to prove that a1*a2* ...*a(ϕ(n)) ≡ -1(mod n)
I am just looking for a push in the right direction if anyone could help. I believe I am supposed to go back to Wilson's Theorem, but I can't see the connection with composite order.
2. Relevant equations
3. The attempt at a solution
I realize that if n is composite then n = ab where 1 < a < b < n. Also, ((n-1)!, n) > a > 1 since a|(n-1)!. If I can get (n-1)! ≡ -1 (mod p), then it is clear that (n-1)! does have a multiplicative inverse mod n, which is -1. My problem is that that is mod p... please help.