2
$\begingroup$

Find the indicated orders below: $$(a) ord_{8}3$$ $$(b) ord_{11}3$$ $$(c)ord_{20}3$$ $$(d)ord_{20}19$$ $$(e)ord_{35}1$$

I'm not sure what this is asking for. If someone could either give me a hint, or possibly work out one or two to show me how I can finish the rest, it would be great.

Thanks,
Chloe :)

$\endgroup$
  • $\begingroup$ Do you know what "order" means? It looks like $\mathrm{ord}_ba$ means the order of $a$ in the group of units modulo $b$. I.e. the smallest positive integer $n$ such that $a^n\equiv1\bmod b$ $\endgroup$ – anon Oct 8 '12 at 19:28
  • $\begingroup$ I'm confused. Could you give me a concrete example? You don't have to do ones I've listed. $\endgroup$ – Chloe Williams Oct 8 '12 at 19:32
  • $\begingroup$ For instance, to compute $\mathrm{ord}_{10}3$, you would compute successive powers of three modulo ten: $3^1\equiv3$, $3^2\equiv9$, $3^3\equiv7$, $3^4\equiv1$ (all modulo ten), so $\mathrm{ord}_{10}3=4$. Note that $\mathrm{ord}_ba$ doesn't make sense if $a,b$ are not coprime. Do you have some sort of chapter, lecture notes, or reading assignment that explains what the order is? Surely you shouldn't be being asked questions involving concepts you haven't seen yet and aren't available in any class resources! $\endgroup$ – anon Oct 8 '12 at 19:36
  • $\begingroup$ Ok, so for example $(a)ord_{8}3=2$? If this is right, then I got the all of $(a)$ through $(d)$. Problem $(e)$ is giving me trouble since, $1^{anything}=1$. Does that men that $ord_{35}1=1$? Thanks for helping. $\endgroup$ – Chloe Williams Oct 8 '12 at 19:49
  • $\begingroup$ Yes and yes. ${}{}$ $\endgroup$ – anon Oct 8 '12 at 19:50
3
$\begingroup$

The number $\text{ord}_m(a)$ is the smallest positive integer $e$ (if it exists) such that $a^e\equiv 1\pmod{m}$.

If $a$ and $m$ are relatively prime, there are $k\gt 0$ such that $a^k\equiv 1\pmod{m}$, otherwise there are not.

In principle, to find the order of $a$, where $\gcd(a,m)=1$, we can try all $k\ge 1$ until we bump into the answer. For small $m$, it will not take terribly long, since the order of $a$ divides $\varphi(m)$, where $\varphi$ is the Euler $\varphi$-function.

In practice, we will want to take shortcuts. For example, consider the order of $99$ modulo $100$. Since $99$ is congruent to $-1$, we have $99^2 \equiv (-1)^2 \pmod{100}$, so the order of $99$ is $2$ or $1$, but it is obviously not $1$.

The fact that the order of $a$ modulo $m$ divides $\varphi(m)$ can be useful. For example, suppose we want to find the order of $7$ modulo $40$. Since $\varphi(40)=16$, the only candidates for the order of $7$ are $1$ (ridiculous), $2$ (clearly not), $4$, $8$, or $16$. It is relatively easy by repeated squaring to compute the appropriate powers modulo $40$.

There are a few other tricks. Your particular examples are computationally not hard. I will stay away from them, but mention a couple of related examples.

What is the order of $4$ modulo $15$? Certainly not $1$! But $4^2\equiv 1\pmod{15}$, so the order is $2$.

What is the order of $3$ modulo $13$? Note that $3^3\equiv 1\pmod{13}$, and no power smaller than the cube will work, so the order of $3$ modulo $13$ is $3$.

Of your questions, by far the easiest is (e).

$\endgroup$
  • $\begingroup$ Thank you, and yes $(e)$ is extremely easy, now that I understand what's going on. $\endgroup$ – Chloe Williams Oct 8 '12 at 20:15
  • $\begingroup$ Im happy for you :) $\endgroup$ – mick Oct 8 '12 at 21:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.