Question

assume q is prime and b has order j modulo q. Show that if gcd(d,j) = 1, then b^d also has order j modulo q.

Answer 1

this is fermat's little theorem http://en.wikipedia.org/wiki/Fermat%27s_little_theorem
a special case of more general theorem http://en.wikipedia.org/wiki/Euler%27s_theorem

Answer 2

how would i prove it?

Answer 3

is Group theory allowed?

Answer 4

i doupt it, I have not taken it yet.

Answer 5

there are couple of proofs ... with Euler's theorem, it's very easy ... which is easy to prove using Group theory. however you can prove Euler theorem without Group theory too.
http://en.wikipedia.org/wiki/Proofs_of_Fermat%27s_little_theorem#Proofs_using_modular_arithmetic
also discussed here http://www.youtube.com/watch?v=w0ZQvZLx2KA

Answer 6

could you talk about why this is the same theorem as that? I dont see how they are the same thing.