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 :)

  • 0
    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$2012-10-08
  • 0
    I'm confused. Could you give me a concrete example? You don't have to do ones I've listed.2012-10-08
  • 0
    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!2012-10-08
  • 0
    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.2012-10-08
  • 0
    Yes and yes. ${}{}$2012-10-08

1 Answers 1

3

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).

  • 0
    Thank you, and yes $(e)$ is extremely easy, now that I understand what's going on.2012-10-08
  • 0
    Im happy for you :)2012-10-08