Jump to content



Recommended Posts

What you mean is not what you wrote.


If (a,b)=1 , i.e. they are relatively prime to each other,

b^d = 1 (mod a)

where 1=< d < a-1 , how do you prove it?


what is your question here then? Prove what?



Do you know any elementary group theory?

Link to comment
Share on other sites

Suppose 3^4=1 ( mod 5 )



why would I suppose it? 3^4=81==1 mod 5 (in fact any number prime to 5 raised to the 4th power is 1 mod 5).


Because (3,5)=1

so we have 3^h=1 (mod 25)

where 4 l h

are the steps correct?


I still have no idea what it is you're trying to do. Please try to repost with *more words* in complete sentences explaining what it is you want to do.


after all 4 divides 4 but 3^4=81 =/=1 mod 5, so what is it you're trying to say? I think words like 'if' and 'then' are missing from your sentences.

Link to comment
Share on other sites

Now 3^6=1 (mod7), let

3^a=1 (mod 49) What can you think about a?

In my mind, it is that a= 6t, where t is an integer.

so I tried to put the multiple of 6t with the last being 48.

and found that a=42.

I tried many other cases, and with the premise which is put in the bold,

found the solution.

I don't know how to prove the premise, can you suggest one method?

Link to comment
Share on other sites

  • 1 month later...

I believe he means that o(a mod b)|h for all a^h = 1 (mod b)

o means order of a mod b - that is, the lowest number o>0 such that a^o = 1 (mod b)

It's a simple proof: Assume we have an h such that o(a mod b) does not divide h. Then by division algorithm, we have an r: d = r + xh, 0 <= r < h. a^d = a^r*a^xh = a^r * (a^h)^x = a^r*1^x = a^r, so a^r = 1. But then, as r < h, that means r must be 0. Therefore, d = xh, so h|d.


Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.