Question

[Number Theory] Primitive Roots, Orders

Answer 1

Given that 2 is a primitive root of 61, determine all least positive residues modulo 61
that have order 4.

Answer 2

I'm honestly just totally lost with this homework. Can someone help me develop a fundamental understanding of this so I can do problems?

Answer 3

what do you know about order of an integer modulo prime ?

Answer 4

Well if I understand it correctly the definition is that for some x, 4 is the smallest power such that x^4 = 1 mod 61?

Answer 5

I'm not quite sure how that relates to primitive roots though

Answer 6

the order of a primitive root modulo p is p-1

Answer 7

Because 2 is a primitive root of 61, any positive integers less tha 61 can be expressed as
\[2^k\]

yes ?

Answer 8

Right that comes from the definition of primitive root

Answer 9

Keeping in mind that the order of \(2\) is \(60\), what can you tell about the order of \(2^k\) ?

Answer 10

If the integer \(a\) has order \(u\), then the order of integer \(a^k\) is given by
\[\dfrac{u}{\gcd(u,k)}\]

seen that theorem before ?

Answer 11

One moment let me flip through some pages

Answer 12

Yeah, it's in the book, I didn't think to apply it though.

Answer 13

So since 2 has order 60, the order of a^k = 60/(60,k)

Answer 14

Right?

Answer 15

I don't think I'm following what I'm supposed to be doing here, I'm sorry <.>

Answer 16

You're right!

Answer 17

`So since 2 has order 60, the order of a^k = 60/(60,k)`

you're looking for all integers having order "4" :
\[\dfrac{60}{(60,k)}=4\]

find all \(k\) first

Answer 18

thats possible only if \((60,k) = 15\)
so find all such \(k\) first

Answer 19

Okay, this might be a really dumb question, but are there any such k?

Answer 20

Oh wait nevermind

Answer 21

Is it just 15 and 45?

Answer 22

Yep!

so 2^15 and 2^45 will have order 4 in modulo 61

Answer 23

reduce them

Answer 24

\[2^{15}\pmod{61}=?\\2^{45}\pmod{61}=?\]

Answer 25

Alright then

Answer 26

I've got it from there, thank you. I might call for your help again to reexplain a step here or maybe a future problem if I'm still struggling

Answer 27

Thanks a ton

Answer 28

yw!

Answer 29

just want you notice that we got "2" primitive roots with order "4",
and this number "2" is not a coincidence

Answer 30

there is an easy way to know how many integers will have an order "u" modulo p

Answer 31

number of integers with order \(u\) is given by \(\phi(u)\)

Answer 32

\(\phi(4) = 2\) in our case as expected