Primarygun Posted July 29, 2006 Share Posted July 29, 2006 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? Link to comment Share on other sites More sharing options...
matt grime Posted July 29, 2006 Share Posted July 29, 2006 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. Link to comment Share on other sites More sharing options...
Primarygun Posted August 2, 2006 Author Share Posted August 2, 2006 I mean if the power exists, then it is divisible by d, where d is the minimum power that satisfies. Link to comment Share on other sites More sharing options...
matt grime Posted August 3, 2006 Share Posted August 3, 2006 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 More sharing options...
Primarygun Posted August 3, 2006 Author Share Posted August 3, 2006 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? Link to comment Share on other sites More sharing options...
matt grime Posted August 3, 2006 Share Posted August 3, 2006 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)=1so 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 More sharing options...
Primarygun Posted August 4, 2006 Author Share Posted August 4, 2006 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 More sharing options...
matt grime Posted August 4, 2006 Share Posted August 4, 2006 The premise is false (t=1). Link to comment Share on other sites More sharing options...
uncool Posted September 17, 2006 Share Posted September 17, 2006 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= Link to comment Share on other sites More sharing options...
Recommended Posts
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 accountSign in
Already have an account? Sign in here.
Sign In Now