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

**tarheelborn** · March 24th 2010, 10:02 AM

(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.

**tonio** · March 24th 2010, 10:32 AM

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.

Tonio

Tonio

**tarheelborn** · March 24th 2010, 11:06 AM

I know that a^phi(n)==1(mod n), but I am not sure how to explain the rest of it.

**tarheelborn** · March 24th 2010, 11:18 AM

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?

**tarheelborn** · March 24th 2010, 12:56 PM

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

**tonio** · March 24th 2010, 01:11 PM

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

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

LinkBack

Thread Tools

Display

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

Similar Math Help Forum Discussions

sophie germain prime primitive root

Order of integers and primitive roots

Primitive Root of odd prime p

primitive root of a prime

Primitive pth root of unity of a prime p

Search Tags