Primitive roots

**Zalren** · July 8th 2011, 01:35 PM

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.

**Opalg** · July 10th 2011, 12:21 PM

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

**Zalren** · July 10th 2011, 05:15 PM

Thanks! Now that you told me that, it was so simple. I have been wrestling with this all weekend. Thanks again!

Thread: Primitive roots

LinkBack

Thread Tools

Display

Primitive roots

Re: Primitive roots

Re: Primitive roots

Similar Math Help Forum Discussions

Primitive Roots

primitive roots

Primitive roots

i need help in primitive roots

Help With primitive roots