Results 1 to 4 of 4

Thread: 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 $\displaystyle \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:
    $\displaystyle 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
    $\displaystyle 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
    $\displaystyle 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 $\displaystyle \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

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

    and we know (by definition) that

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

    Multiply this by s to get

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

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

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

    Since the integers are closed under ops we get

    $\displaystyle 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 $\displaystyle \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 $\displaystyle r,s$ such that $\displaystyle rm+sa=1.$ Substituting $\displaystyle x=sb$ in the congruence equation gives $\displaystyle asb=b-brm\equiv b\pmod m$ so $\displaystyle x=sb$ is a solution.

    Suppose $\displaystyle x'$ is another solution, so $\displaystyle ax'\equiv b\pmod m.$ Thus $\displaystyle a(x-x')\equiv0\pmod m\ \implies\ m$ divides $\displaystyle a(x-x')\ \implies\ m$ divides $\displaystyle x-x'$ since $\displaystyle \gcd(m,a)=1\ \implies\ x'\equiv x\pmod m.$ Hence the solution to $\displaystyle ax\equiv b\pmod m$ is unique up to congruence modulo $\displaystyle 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: Mar 11th 2010, 12:52 PM
  2. Congruences
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Mar 18th 2009, 05:12 AM
  3. More congruences
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Mar 17th 2009, 10:40 PM
  4. Congruences
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Oct 6th 2008, 06:18 PM
  5. Congruences
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Sep 29th 2008, 09:49 AM

Search Tags


/mathhelpforum @mathhelpforum