# modulo

## Recommended Posts

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?

Also the following is my guess.

IF b^h= 1 (mod a^2)

Then d l h, does it make sense?

##### Share on other sites

No. Just try some examples to see why this is wrong. How can b to all powers be congruent to 1 mod a? Just take d=1.

##### Share on other sites

I mean if the power exists, then it is divisible by d, where d is the minimum power that satisfies.

##### Share on other sites

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?

##### Share on other sites

Suppose 3^4=1 ( mod 5 )

Because (3,5)=1

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

where 4 l h

are the steps correct?

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

##### 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?

##### Share on other sites

The premise is false (t=1).

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

=Uncool=

## Create an account

Register a new account