Results 1 to 4 of 4

Math Help - Congruences

  1. #1
    Newbie
    Joined
    Apr 2009
    Posts
    2

    Congruences

    Hi, I'm looking for any help towards showing the following:

    given a and m are coprime, prove that ax \equiv b (mod m) has a unique solution mod m.

    Any help would be much appreciated, and thank you for your time.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Gamma's Avatar
    Joined
    Dec 2008
    From
    Iowa City, IA
    Posts
    517
    Lemma:
    If gcd(a,m)=1, then there is a unique inverse to a mod m. That is there is a unique solution to:
    ax\equiv 1 (mod m)

    Proof
    By the Euclidean Algorithm, you know there exist integers x and y such that

    ax + my=1

    Reduce mod m and we see
    ax\equiv 1 (mod m)
    as desired.

    Uniqueness of this solution mod m comes from solving this diophantine equation. There are an infinite number of solutions to this equation ax +my = 1 if (a,m)=1 but they should all be congruent mod m. Alternatively if you know what a group is this is just the multiplicative group of units for the integers modulo m and as we all know inverses in a group are uniqe.

    To solve your question, simply take the unique inverse that I found above and multiply it by b, multiplication is well defined, so this is the unique answer to the equation
    ax \equiv b (mod m)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Behold, the power of SARDINES!
    TheEmptySet's Avatar
    Joined
    Feb 2008
    From
    Yuma, AZ, USA
    Posts
    3,764
    Thanks
    78
    Quote Originally Posted by ShootTheBullet View Post
    Hi, I'm looking for any help towards showing the following:

    given a and m are coprime, prove that ax \equiv b (mod m) has a unique solution mod m.

    Any help would be much appreciated, and thank you for your time.
    Since a,m are coprime there exists integers r,s such that

    sa+rm=1 \iff sa=1-rm

    and we know (by definition) that

    ax-b=mq_1 for some q_1 \in \mathbb{Z}

    Multiply this by s to get

    sax-sb=msq_1 Now sub in the above result to get

    (1-rm)x-sb=msq_1 \iff x-srm-sb=msq_1

    x-sb=srm+msq_1 \iff x-sb=m(sr+sq_1)

    Since the integers are closed under ops we get

    x-sb =mq_2 \iff x=sb \mod(m)

    so it has a solution
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member TheAbstractionist's Avatar
    Joined
    Apr 2009
    Posts
    328
    Thanks
    1
    Quote Originally Posted by ShootTheBullet View Post
    Hi, I'm looking for any help towards showing the following:

    given a and m are coprime, prove that ax \equiv b (mod m) has a unique solution mod m.

    Any help would be much appreciated, and thank you for your time.
    Hi ShootTheBullet.

    Letís put together Gammaís solution and TheEmptySetís solution.

    So you know that there are integers r,s such that rm+sa=1. Substituting x=sb in the congruence equation gives asb=b-brm\equiv b\pmod m so x=sb is a solution.

    Suppose x' is another solution, so ax'\equiv b\pmod m. Thus a(x-x')\equiv0\pmod m\ \implies\ m divides a(x-x')\ \implies\ m divides x-x' since \gcd(m,a)=1\ \implies\ x'\equiv x\pmod m. Hence the solution to ax\equiv b\pmod m is unique up to congruence modulo m.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Congruences
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: March 11th 2010, 01:52 PM
  2. Congruences
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 18th 2009, 06:12 AM
  3. More congruences
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 17th 2009, 11:40 PM
  4. Congruences
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 6th 2008, 07:18 PM
  5. Congruences
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 29th 2008, 10:49 AM

Search Tags


/mathhelpforum @mathhelpforum