1

as far as I can see, Lagrange says:

IF
$p$ = prime, $p-1 = 2*q$, $q$ = prime
THEN
$g^q \mod p = 1 \implies \text{order}(g) = q$
$g^q \mod p \neq 1 \implies \text{order}(g) = p-1$

However if i try to calculate the order of $6 \mod 7$:
$p = 7 \implies p-1 = 6 = 2 \cdot 3 \implies q=3$, $6^3 \mod 7 = 6 \neq 1 \implies \text{order}(6)$ should be $6$.

But doing it by hand i get the following:
$6^1 \mod 7 = 6$

$6^2 \mod 7 = 1$

$6^3 \mod 7 = 6$

$6^4 \mod 7 = 1$ ...
so order should be $2$ instead of $6$ right? What am I missing, i really don't get it :(

user128779
  • 452
Maximosaic
  • 113

1 Answers1

0

The only divisors of $2q$ are $1$, $2$, $q$, and $2q$. Thus they are the only candidates for the order of $g$.

If $g^q\equiv 1\pmod{p}$, then $g$ has order $1$ or $q$.

If $g^q\not\equiv 1\pmod{p}$, then $g$ has order $2$ or $2q$.

André Nicolas
  • 507,029
  • I see, thanks. so if i figure out that g^q != 1, I still have to calculate the g^1 , g^2, g^3 mod p, to double check that the order is not 2 if i am looking for prime roots? – Maximosaic Jul 06 '14 at 19:57
  • If $g^q\not\equiv 1$, you need to check only $g^2$. If you are interested in primitive roots, all quadratic non-residues are primitive roots except (in the case $q$ odd) the non-residue $-1$. – André Nicolas Jul 06 '14 at 20:04
  • and if g^2 == 1 the order must be 2. that makes sense, thanks a lot!! – Maximosaic Jul 06 '14 at 20:07