yda Posted November 13, 2004 Share Posted November 13, 2004 I need to prove that if a,b, a is not 0, in Zp than there is n that b = na how should I start proving that ? Link to comment Share on other sites More sharing options...
matt grime Posted November 13, 2004 Share Posted November 13, 2004 Firstly, this isn't true unless p is a prime, if it is a prime then say so. The answer as always follows from the hint: all you know (if p is a prime), is that a and p are coprime. Hence all you can do is use the single result at your disposal, ie Euclid's Algorithm. Let us know where that gets you Link to comment Share on other sites More sharing options...
yda Posted November 13, 2004 Author Share Posted November 13, 2004 well, the prime is not mention in my question but after what u said I agree that its must be. still I dont know where to start proving that and how can I use Euclid's Algorithm for the solution Link to comment Share on other sites More sharing options...
matt grime Posted November 13, 2004 Share Posted November 13, 2004 What does Euclid tell us? That given a and p coprime, there are integers x and y with ax+py=1 can you now see how to express b as "a" times something plus something congruent to zero mod p? Note that if all we require is that a is not zero then p must be a prime, but it suffices just for a and p to be coprime. Link to comment Share on other sites More sharing options...
yda Posted November 14, 2004 Author Share Posted November 14, 2004 Its clear for me now, thanks 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