(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.
(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 $\displaystyle n$ has a primitive root $\displaystyle a$ iff $\displaystyle \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}}=$ $\displaystyle \left(a^{\frac{\phi(n)}{2}}\right)^{\phi(n)-1}=-1$ ...
Explain the above, in particular the very last equality.
Tonio
Tonio
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 $\displaystyle \mathbb{Z}\slash n\mathbb{Z}$ , i.e. the elements of $\displaystyle \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 $\displaystyle \left(\mathbb{Z}\slash n\mathbb{Z}\right)^{*}$ is cyclic of order $\displaystyle \phi(n)$...in the last equality I used that $\displaystyle \phi(n)$ is even for any $\displaystyle n\geq 3$ ...
Tonio