Results 1 to 4 of 4

Math Help - showing the identity in multiplication mod n only exists with gcd =1

  1. #1
    Junior Member
    Joined
    Oct 2009
    Posts
    66

    showing the identity in multiplication mod n only exists with gcd =1

    Ok so we defined multiplication mod n and the question is, Let a element of Zn there exists b element Zn such that a * b = 1 iff gcd(a,n) = 1. I know i gotta go both ways but im not sure where to start to attack this thing
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    241
    Quote Originally Posted by ChrisBickle View Post
    Ok so we defined multiplication mod n and the question is, Let a element of Zn there exists b element Zn such that a * b = 1 iff gcd(a,n) = 1. I know i gotta go both ways but im not sure where to start to attack this thing
    What you've written doesn't really make sense. However I will try to help.

    I suppose you are saying a,b \epsilon Z. Then if a*b = 1, a and b would both have to be 1 or -1 since no other intergers multiplied together = 1.

    If a is 1 or -1 then gcd(a,n) is obviously 1.

    converse: Assume gcd(a,n) not = 1, then a cannot be 1 or -1.

    Therefore b cannot be an integer such that a * b = 1. Proof by contrapositive.

    If this is not what you are saying, please restate.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2009
    Posts
    66
    ya it didnt make much sense the way i wrote it i figured it out today, if you assume b exists then ab is congruent to 1modn and use definitions to get to ab - nh = 1 then the gcd is 1 and turn it around to go the other way. Thanks for trying sorry i wrote it so confusing.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by ChrisBickle View Post
    Ok so we defined multiplication mod n and the question is, Let a element of Zn there exists b element Zn such that a * b = 1 iff gcd(a,n) = 1. I know i gotta go both ways but im not sure where to start to attack this thing
    I assume you meant there ab\equiv1\text{ mod }n?

    Problem: Prove that (a,n)=1\Leftrightarrow ab\equiv1\text{ mod }n for some b\in\mathbb{Z}_n.

    Lemma: For a,b\in\mathbb{Z} the linear Diophantine equation ax+by=1 is only solvable if (a,b)=1

    Proof: Suppose that (a,b)=c>1 but \exists x,y\in\mathbb{Z} such that ax+by=1. Then clearly c|ax and c|by so c|ax+by=1 which is a contradiction. \blacksquare

    This proves the leftward facing arrow. I'm tired, so I'l leave the other half to you.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Showing that a C-infinity function exists
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: April 11th 2011, 02:14 PM
  2. Showing that a limit exists
    Posted in the Differential Geometry Forum
    Replies: 5
    Last Post: January 16th 2011, 05:07 AM
  3. Showing that the directional derivative exists at a point.
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: September 20th 2010, 09:47 PM
  4. showing identity help..
    Posted in the Trigonometry Forum
    Replies: 4
    Last Post: March 14th 2009, 05:11 AM
  5. showing that the limit exists
    Posted in the Calculus Forum
    Replies: 11
    Last Post: September 25th 2007, 10:01 AM

Search Tags


/mathhelpforum @mathhelpforum