Results 1 to 5 of 5

Math Help - stuck on congruence proof

  1. #1
    Newbie
    Joined
    May 2008
    Posts
    23

    stuck on congruence proof

    Hey guys (and gals),

    I was wondering if you could help me out. I am stuck on this proof I know a bunch of the basic steps but can't put them together properly. If I could get your help it would be great the question is:

    Prove that for every  a,m \epsilon Z such that gcd(a,m)=1, with  m>1 there is a  b \epsilon Z such that ab \equiv 1 (\bmod m). Show therefore, that we can "divide" by a by multiplying the congruence by the corresponding b:

     ax \equiv c (\bmod m) \Leftrightarrow x \equiv bc (\bmod m)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hello,

    Quote Originally Posted by SaxyTimmy View Post
    Hey guys (and gals),

    I was wondering if you could help me out. I am stuck on this proof I know a bunch of the basic steps but can't put them together properly. If I could get your help it would be great the question is:

    Prove that for every  a,m \epsilon Z such that gcd(a,m)=1, with  m>1 there is a  b \epsilon Z such that ab \equiv 1 (\bmod m).
    This has to do with Bézout's theorem (I don't know if you are allowed to use it).


    Bézout's identity :
    Let d=gcd(x,y). There exist u~,~v~\in \mathbb{Z} such that :

    u \cdot x+v \cdot y=d.

    Bézout's theorem/lemma :
    gcd(x,y)=1 \Longleftrightarrow \exists u~,~v~\in \mathbb{Z} \text{ such that } u \cdot x+v \cdot y=1.

    --------------------------
    Going back to the problem :

    gcd(a,m)=1 \implies \exists u~,~v~\in \mathbb{Z} \text{ such that } u \cdot a+v \cdot m=1 \quad (1)

    Rewriting (1) :

    au=1-{\color{red}m}v \equiv 1 (\bmod {\color{red}m})

    \boxed{u=b}


    Show therefore, that we can "divide" by a by multiplying the congruence by the corresponding b:

     ax \equiv c (\bmod m) \Leftrightarrow x \equiv bc (\bmod m)
    ax \equiv c (\bmod m)

    Multiplying by b each side :

    abx \equiv {\color{blue}bc} (\bmod m)

    But we know that ab \equiv 1 (\bmod m)

    Therefore abx \equiv {\color{blue}x} (\bmod m)


    --> x \equiv bc (\bmod m)

    You can do the reverse implication exactly the same way.


    Whew!
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2008
    Posts
    23
    Thanks Moo, you are my hero. You make the things that I get stuck on look so trivial. I was almost there, but missed the one thing that made it all come together into a cohesive proof. You are my HERO!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    You're welcome You know, I'm happy that you understand !


    Another point I forgot to mention...
    b is called the "inverse" of a modulo m, in (\mathbb{Z}/m \mathbb{Z},+).

    This means that [maht]ab \equiv 1 (\bmod m)[/tex].



    So basically, you can "divide" the stuff by b because it has an inverse. Whereas if you had, for example :
    46 \equiv 6 (\bmod 10), 6 has no inverse... because it's not coprime with 10.

    To simplify the thing, you can do it :

    2 \cdot 23 \equiv 2 \cdot 3 (\bmod 2 \cdot 5)

    There you can divide by 2, but don't forget to divide the modulo too !!

    23 \equiv 3 (\bmod 5)

    Justification :
    46 \equiv 6 (\bmod 10) \longleftrightarrow 46=6+10k
    --> 23=3+5k \longleftrightarrow 23 \equiv 3 (\bmod 5)


    If you had 46 \equiv 6 (\bmod 5), you can see that 2 and 5 are coprime. Therefore, there exists b such that 2b \equiv 1(\bmod 5)

    Multiplying by b :
    --> 23 \cdot (2 \cdot b) \equiv 3 \cdot 2 \cdot b (\bmod 5)

    23 \equiv 3 (\bmod 5)


    So you can see that if you want to divide by a number :
    - if it is coprime with the modulus, it doesn't affect it
    - if it isn't coprime with the modulus, it affects it


    This was just some extra
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    May 2008
    Posts
    23
    hmmm... thats pretty interesting. Our prof was like this is true just believe me... but seeing the justification behind it is always nice. thanks for the info Moo.

    The definition of the congruence you used is also nice (the 23=3+5k or something like that) also nice to see things like that. The definition we were taught is slightly different, but seeing it that way makes things look much better for certain instances.

    Anyways, I would have "thanked" you for that useful post moo but it won't let me . So, thanks a ton for all your help again.

    Edit: Now for some reason it will let me thank you
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. A Congruence Proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 22nd 2010, 03:50 PM
  2. Congruence Proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: January 20th 2010, 01:30 PM
  3. Congruence Proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 15th 2009, 07:12 AM
  4. Congruence proof
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: March 24th 2008, 08:16 AM
  5. Proof congruence
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: November 19th 2007, 10:13 AM

Search Tags


/mathhelpforum @mathhelpforum