# Multiplicative Order

• Mar 18th 2010, 02:55 PM
seven.j
Multiplicative Order
Hi all, just wondering what the method is to find an integer with order t mod m.

For example, find all integers that have order 11 (mod 45).

I know you can geuss and test, but I'm thinking there must be a faster way.

Thanks.
• Mar 18th 2010, 03:22 PM
chiph588@
Quote:

Originally Posted by seven.j
Hi all, just wondering what the method is to find an integer with order t mod m.

For example, find all integers that have order 11 (mod 45).

I know you can geuss and test, but I'm thinking there must be a faster way.

Thanks.

Well for starters, the order $t$ always divides $\phi(m)$.

Here, $\phi(45)=24$ and $11 \not| 24$ so no number exists with order $11$ modulo $45$.
• Mar 18th 2010, 03:30 PM
chiph588@
Quote:

Originally Posted by seven.j
Hi all, just wondering what the method is to find an integer with order t mod m.

For example, find all integers that have order 11 (mod 45).

I know you can geuss and test, but I'm thinking there must be a faster way.

Thanks.

Also, if $a\in G \leq \mathbb{Z}/m\mathbb{Z}$, then the order of $a$ divides $|G|$.
• Mar 18th 2010, 03:42 PM
chiph588@
One last thing:

If $a\in \mathbb{Z}/m\mathbb{Z}$ is a primitive root, then we know that $\mathbb{Z}/m\mathbb{Z} = $ i.e. $\forall \; b\in \mathbb{Z}/m\mathbb{Z}, \; b=a^k$ for some $k\in \mathbb{N}$.

So all one has to do to find $ord_m(b)$ for any $b\in \mathbb{Z}/m\mathbb{Z}$, is find $ord_m(a)$ and use the formula $ord_m(b) = ord_m(a^k)=\frac{ord_m(a)}{(ord_m(a),k)}$.

In summary, knowing the order of a primitive root gives you the order of every number in your group.