Results 1 to 9 of 9

Math Help - Coprimes and modulus problem

  1. #1
    Newbie
    Joined
    Nov 2011
    Posts
    5

    Coprimes and modulus problem

    I have the following problem:

    Prove: If GCD(a,n)=1, then there exists an integer b such that GCD(b, n)=1, and ab {is congruent to} 1 (mod n)

    Yes its my math homework, but ive been staring at it for three hours, and i even talked to my professor about it and just cant seem to get anywhere. Im limited to certain thechniques and theorems, which i think excludes the euclidean algorithm. She suggested i start with the theorem that states that if GCD(a,n)=b, then b=as+nt, with n and t being integers, and b being he smallest number that can be expressed this way, but i just cant seem to get any useful information out of that knowledge.

    Can anyone help me in any way? hints? somewhere to start?
    Last edited by martinosorio; December 1st 2011 at 12:17 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: Coprimes and modulus problem

    use the fact that gcd(a,n) = 1 means there are integers r,s such that ar + ns = 1. what happens if you take this equation modulo n?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2011
    Posts
    5

    Re: Coprimes and modulus problem

    Quote Originally Posted by Deveno View Post
    use the fact that gcd(a,n) = 1 means there are integers r,s such that ar + ns = 1. what happens if you take this equation modulo n?
    do you get that
    ar mod n = 1 and thus n|ar-1

    i can see how this relates to the second conclusion, but i still dont see where im going to get that b from
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: Coprimes and modulus problem

    what does that tell you about r (mod n)?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Nov 2011
    Posts
    5

    Re: Coprimes and modulus problem

    Quote Originally Posted by Deveno View Post
    what does that tell you about r (mod n)?
    hmmm...
    lets see i know n does not divide a, so a mod n = a...
    does that mean r equals kn+1? for some integer k?
    so n|r-1
    so r mod n = 1?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Nov 2011
    Posts
    5

    Re: Coprimes and modulus problem

    and thus would mean gcd(r, n) =1?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: Coprimes and modulus problem

    no, you're barking up the wrong tree.

    if ar + ns = 1, then

    ar (mod n) + ns (mod n) = 1 (mod n).

    now, what is ns (mod n)?

    is it true that ar (mod n) = (a mod n)(r mod n)?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Nov 2011
    Posts
    5

    Re: Coprimes and modulus problem

    Quote Originally Posted by Deveno View Post
    now, what is ns (mod n)?

    is it true that ar (mod n) = (a mod n)(r mod n)?
    I thought ns (mod) n = 0, so it cancels out.

    and i thought it was true.

    so going back ar mod n = 1

    (a mod n) + (r mod n) = 1

    since n does not divide a, a mod n = a

    a + (r mod n) = 1?

    ...so r mod n = 1 - a?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: Coprimes and modulus problem

    why are you adding (a mod n) and (r mod n) rather than multiplying them?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: December 5th 2011, 11:47 PM
  2. Modulus
    Posted in the Algebra Forum
    Replies: 2
    Last Post: June 22nd 2011, 07:11 AM
  3. Proof with coprimes
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: October 15th 2009, 12:06 PM
  4. Coefficient of friction, modulus of elasticity problem?
    Posted in the Advanced Applied Math Forum
    Replies: 1
    Last Post: June 21st 2009, 12:28 AM
  5. Replies: 7
    Last Post: April 13th 2009, 04:57 AM

Search Tags


/mathhelpforum @mathhelpforum