(1) Show that if n is an integer which has primitive roots, then the product of the integers less than or equal to n and relatively prime to n == -1(mod n).

(2) Show that (1) is not true if n does not have a primitive root.

- Mar 24th 2010, 11:02 AMtarheelbornPrimitive Roots - product of integers <= n and rel prime to n
(1) Show that if n is an integer which has primitive roots, then the product of the integers less than or equal to n and relatively prime to n == -1(mod n).

(2) Show that (1) is not true if n does not have a primitive root. - Mar 24th 2010, 11:32 AMtonio
- Mar 24th 2010, 12:06 PMtarheelborn
I know that a^phi(n)==1(mod n), but I am not sure how to explain the rest of it.

- Mar 24th 2010, 12:18 PMtarheelborn
OK, I think this may be it. Since g^phi(n)==1(mod n) and g^(phi(n)-1)/2==-1(mod n), then their product would be -1(mod n). Done. Right?

- Mar 24th 2010, 01:56 PMtarheelborn
Also, I need to show that this is not true if n does not have a primitive root.

- Mar 24th 2010, 02:11 PMtonio

The demonstration is an if and only if one, so both directions are already contained in it....what part you didn't get? That there's a primitive root w of n means that all the units in , i.e. the elements of , i.e. all the integers modulo n which are coprime to n, are a power of w <==> the group is cyclic of order ...in the last equality I used that is even for any ...

Tonio