Results 1 to 3 of 3

Math Help - proof on inverse modulo

  1. #1
    Member
    Joined
    Nov 2005
    Posts
    111

    proof on inverse modulo

    Hi,
    I need help with this problem.

    Show that if a and m are relatively prime positive integers, then the inverse of a modulo m is unique modulo m.
    [hint: assume that there are 2 solutions b and c of the congruence ax==1(mod m). No need to prove that b==c (mod m) ]

    I can fin the solution by starting with the fact that gcd(a,m)=1
    --> S*a+ T*m=1 --> S*a+ T*m=1 (mod m) and so on....
    But this way of showing this..I don't get it.

    I tried something like:

    a*b==1(mod m) and c*a==1(mod m)-->a*b==c*a(mod m)
    -->b==c (mod m)
    then I dont know how to continue..
    Can I have some help please?
    B
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by braddy View Post
    Hi,
    I need help with this problem.

    Show that if a and m are relatively prime positive integers, then the inverse of a modulo m is unique modulo m.
    [hint: assume that there are 2 solutions b and c of the congruence ax==1(mod m). No need to prove that b==c (mod m) ]

    I can fin the solution by starting with the fact that gcd(a,m)=1
    --> S*a+ T*m=1 --> S*a+ T*m=1 (mod m) and so on....
    But this way of showing this..I don't get it.

    I tried something like:

    a*b==1(mod m) and c*a==1(mod m)-->a*b==c*a(mod m)
    -->b==c (mod m)
    then I dont know how to continue..
    Can I have some help please?
    B

    For n>1 consider the set,
    G_n={gcd(x,n)=1|1<=x<=n}
    It can be shown from group theory this is a group under multiplication mudolo n.

    Proof:

    Closure: We have gcd(a,n)=1 and gcd(b,n)=1 then gcd(ab,n)=1.

    AssociativityTrivial. Since G_n is a proper algebraic binary structuce of Z_n.

    IdentityTrivial, 1 is in G_n.

    Existence of inverse.
    Let,
    a_1,a_2,...,a_k
    Be all the elements in G_n
    Let a be in G_n
    Form the numbers,
    aa_1,aa_2,...,aa_k
    Note if,
    aa_i=aa_j (mod n)
    Then since gcd(a,n)=1 we have,
    a_i=a_j
    But that is not possible for 1<=a_i,a_j<=n
    Thus, all,
    aa_1,aa_2,...,aa_k
    Are distinct.
    By Dirichlet's Pigeonhole Principle
    It consits of,
    a_1,a_2,...a_k
    In which one is 1 (identity)
    Q.E.D.

    Now the equation,
    ax=1(mod n)
    For gcd(a,n)=1
    Is asking to solve this linear equation in the group G_n
    Which we know always have a unique solution.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Nov 2005
    Posts
    111
    Quote Originally Posted by ThePerfectHacker View Post
    For n>1 consider the set,
    G_n={gcd(x,n)=1|1<=x<=n}
    It can be shown from group theory this is a group under multiplication mudolo n.

    Proof:

    Closure: We have gcd(a,n)=1 and gcd(b,n)=1 then gcd(ab,n)=1.

    AssociativityTrivial. Since G_n is a proper algebraic binary structuce of Z_n.

    IdentityTrivial, 1 is in G_n.

    Existence of inverse.
    Let,
    a_1,a_2,...,a_k
    Be all the elements in G_n
    Let a be in G_n
    Form the numbers,
    aa_1,aa_2,...,aa_k
    Note if,
    aa_i=aa_j (mod n)
    Then since gcd(a,n)=1 we have,
    a_i=a_j
    But that is not possible for 1<=a_i,a_j<=n
    Thus, all,
    aa_1,aa_2,...,aa_k
    Are distinct.
    By Dirichlet's Pigeonhole Principle
    It consits of,
    a_1,a_2,...a_k
    In which one is 1 (identity)
    Q.E.D.

    Now the equation,
    ax=1(mod n)
    For gcd(a,n)=1
    Is asking to solve this linear equation in the group G_n
    Which we know always have a unique solution.
    OK!! thanks ThePerfectHacker
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] modulo inverse
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: June 16th 2011, 09:52 AM
  2. inverse of 4 modulo 9
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 17th 2009, 06:40 AM
  3. inverse of modulo
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: June 22nd 2009, 07:03 PM
  4. (n) inverse modulo m
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 21st 2009, 10:49 AM
  5. inverse modulo
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: September 15th 2008, 01:31 PM

Search Tags


/mathhelpforum @mathhelpforum