# Primitive roots

• July 8th 2011, 01:35 PM
Zalren
Primitive roots
Show that if $m$ is a number having primitive roots, then the product of the positive integers less than or equal to $m$ and relatively prime to $m$ is congruent to $-1 (\mod{m})$.

$m$ has primitive roots means there is a least residue $a$ such that $a^{\phi(m)} \equiv 1 (\mod{m})$

Since $a$ is a primitive root of $m$, then the least residues $(\mod{m})$ of $a, a^2, ..., a^{\phi(m)}$ are a permutation of the $\phi(m)$ positive integers less than $m$ and relatively prime to $m$.

So the congruency to look at is $(a * a^2 * ... * a^{\phi(m)}) \equiv -1 (\mod{m})$ correct??? I have been looking at this congruency and failing to make it true.

Thanks for any help.
• July 10th 2011, 12:21 PM
Opalg
Re: Primitive roots
Quote:

Originally Posted by Zalren
Show that if $m$ is a number having primitive roots, then the product of the positive integers less than or equal to $m$ and relatively prime to $m$ is congruent to $-1 (\mod{m})$.

$m$ has primitive roots means there is a least residue $a$ such that $a^{\phi(m)} \equiv 1 (\mod{m})$

Since $a$ is a primitive root of $m$, then the least residues $(\mod{m})$ of $a, a^2, ..., a^{\phi(m)}$ are a permutation of the $\phi(m)$ positive integers less than $m$ and relatively prime to $m$.

So the congruency to look at is $(a * a^2 * ... * a^{\phi(m)}) \equiv -1 (\mod{m})$ correct??? I have been looking at this congruency and failing to make it true.

Thanks for any help.

If m has primitive roots then $\phi(m)$ is an even number. So the group of primitive roots has even order. Two of its elements are 1 and m–1 (and of course $m-1\equiv-1\pmod m$). The remaining elements can be paired off, each pair consisting of an element and its inverse. The product of each such pair is by definition $\equiv 1\pmod m.$ So the product of all the elements of the group is $\equiv-1\pmod m.$
• July 10th 2011, 05:15 PM
Zalren
Re: Primitive roots
Thanks! Now that you told me that, it was so simple. I have been wrestling with this all weekend. Thanks again!