# Primitive Roots - product of integers <= n and rel prime to n

• March 24th 2010, 10:02 AM
tarheelborn
Primitive 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.
• March 24th 2010, 10:32 AM
tonio
Quote:

Originally Posted by tarheelborn
(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.

The natural number $n$ has a primitive root $a$ iff $\left(\mathbb{Z}\slash n\mathbb{Z}\right)^{*} = \{a,a^2,\ldots,a^{\phi(n)}=1\}\Longleftrightarrow 1\cdot a\cdot a^2\cdot\ldots\cdot a^{\phi(n)-1}=a^{\sum^{\phi(n)-1}_{i=1}i}=a^{\frac{(\phi(n)-1)\phi(n)}{2}}=$ $\left(a^{\frac{\phi(n)}{2}}\right)^{\phi(n)-1}=-1$ ...

Explain the above, in particular the very last equality. (Wink)

Tonio

Tonio
• March 24th 2010, 11:06 AM
tarheelborn
I know that a^phi(n)==1(mod n), but I am not sure how to explain the rest of it.
• March 24th 2010, 11:18 AM
tarheelborn
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?
• March 24th 2010, 12:56 PM
tarheelborn
Also, I need to show that this is not true if n does not have a primitive root.
• March 24th 2010, 01:11 PM
tonio
Quote:

Originally Posted by tarheelborn
Also, I need to show that this is not true if n does not have a primitive root.

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 $\mathbb{Z}\slash n\mathbb{Z}$ , i.e. the elements of $\left(\mathbb{Z}\slash n\mathbb{Z}\right)^{*}$ , i.e. all the integers modulo n which are coprime to n, are a power of w <==> the group $\left(\mathbb{Z}\slash n\mathbb{Z}\right)^{*}$ is cyclic of order $\phi(n)$...in the last equality I used that $\phi(n)$ is even for any $n\geq 3$ ...

Tonio