Multiplicative Order

If $d\mid k$, write $k=qd$. Then

Conversely, suppose $a^k\equiv1\pmod n$. By the division algorithm,

Therefore,

By the minimality of $d$, we must have $r=0$. Hence $d\mid k$.

Euler's theorem gives

By Theorem 1,

In particular, if $p$ is prime and $p\nmid a$,

Let $g=\gcd(d,k)$, and write

where $\gcd(d',k')=1$.

For any positive integer $t$,

Since $\gcd(d',k')=1$, this is equivalent to $d'\mid t$. Therefore, the smallest such $t$ is $d'$.

For every positive integer $k$,

Thus their smallest positive exponents are equal.

Let $L=\operatorname{lcm}(r,s)$. Since $r\mid L$ and $s\mid L$,

Therefore $\operatorname{ord}_n(ab)\mid L$.

Now suppose $\gcd(r,s)=1$, and write $t=\operatorname{ord}_n(ab)$. Then

Raising both sides to the power $s$,

Thus $r\mid ts$. Since $\gcd(r,s)=1$, we obtain $r\mid t$. Similarly, $s\mid t$.

Therefore $rs\mid t$. But $t\mid rs$, so $t=rs$.

By the Chinese Remainder Theorem,

if and only if

The smallest positive $k$ satisfying both conditions is the least common multiple of the two orders.

Let $d=\operatorname{ord}_{21}(2)$.

We need to check $1,2,3,4,6,12$.

So,

Let $d=\operatorname{ord}_p(2)$, so

If $d=1$,

So $d=11$.

By Fermat's Little Theorem,

Then

Let $d=\operatorname{ord}_{31}(3)$.

By Fermat's Little Theorem,

So

We need to check $1,2,3,5,6,10,15,30$.

So,

Let $t=\operatorname{ord}_{31}(3^{12})$.

Or by using the formula,

Since $\gcd(n,10)=1$, we also have $\gcd(9n,10)=1$.

By the definition of multiplicative order, the smallest positive integer $k$ satisfying

is

Let $k$ be the length of the repeating block in the decimal expansion of $1/n$.

Since $\gcd(n,10)=1$, the decimal expansion is purely periodic. Thus, for some positive integer $A$ with $k$ digits (allowing leading zeros),

Therefore,

so

Hence,

Conversely, let $d=\operatorname{ord}_n(10)$. Then

so $n\mid10^d-1$. Thus, for some positive integer $B$,

where $B$ is written with exactly $d$ digits, allowing leading zeros.

Therefore, the repeating block has length at most $d$, so $k\le d$.

Since $d\mid k$, we also have $d\le k$. Consequently,