# Primitive roots

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

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

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

So the congruency to look at is $\displaystyle (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.
• Jul 10th 2011, 12:21 PM
Opalg
Re: Primitive roots
Quote:

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

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

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

So the congruency to look at is $\displaystyle (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 $\displaystyle \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 $\displaystyle 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 $\displaystyle \equiv 1\pmod m.$ So the product of all the elements of the group is $\displaystyle \equiv-1\pmod m.$
• Jul 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!