Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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$ –  anon Oct 8 '12 at 19:28
    
I'm confused. Could you give me a concrete example? You don't have to do ones I've listed. –  Chloe Williams Oct 8 '12 at 19:32
    
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! –  anon Oct 8 '12 at 19:36
    
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. –  Chloe Williams Oct 8 '12 at 19:49
    
Yes and yes. ${}{}$ –  anon Oct 8 '12 at 19:50

1 Answer 1

up vote 3 down vote accepted

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

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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