= Order verification from divisors
{title2=$a^r=1,\quad a^{r/q}\ne1\ (q\mid r\text{ prime})$}
Let $a$ be a <unit> <modulo> $N\geq2$ and let $r$ be a <positive integer>. To prove that $r$ is its <multiplicative order>, it is necessary and sufficient to check
$$
a^r\equiv1\pmod N,\qquad a^{r/q}\not\equiv1\pmod N\quad\text{for every prime divisor }q\mid r.
$$
The first check makes the true order $d$ a <divisor> of $r$. If $d<r$, choose a <prime divisor> $q$ of $r/d$; then $d\mid r/q$, contradicting the second check. Conversely, if $d=r$, no smaller positive exponent $r/q$ can return to one.
For example, $2^6\equiv1\pmod7$ alone does not prove order six: the divisor $q=2$ gives $2^3\equiv1$ and rejects it. The candidate three passes, since $2^3\equiv1$ but $2^1\not\equiv1$. Once the <prime factorization> of $r$ is supplied, this certificate needs one <modular exponentiation> per distinct <prime factor>, plus the return check. The factorization itself is separate work. The candidate $r=1$ has no prime divisors and is accepted exactly when $a\equiv1$.
Back to article page